暗号理論第1回―数論基礎 合同式・ユークリッドの互除法・オイラーの定理

整数論の序論は暗号理論にとって大切である。今回は特に古典的整数論によって、ユークリッドの互除法を証明するあたりから、オイラーの定理を簡潔に解説し概論としてこれを会得してもらう。余裕があれば、オイラーの定理の証明まで行い、身に着けることを強く推奨する。

まず、合同式の定義だが、ここは変数をつかって説明する。まず、二つの整数を考える。自然数とは0を含まない正の整数のことを言う。例えば1、2、3、4、5、6、7、8、9・・・というようにである。これは集合として表せば…

{1,2,3,4・・・}

として表される。おさらいだな。他方、整数とは0を含めた0から次々に+1・・・や-1・・・を施した数字のことを言う。要するに整数とは集合にしてみれば….

{0,1,-1,2,-2,3,-3,4,-4,・・・}

として表される。そして合同式とはこのように定義できる。

a≡r(mod b)

ここで、ある世界を考える。この世界では定義が決まっており、a=bq+rのときで、すなわちaをbで割ったとき、商がqであって、余りがrのときのことである。教科書によっては厳密に余りの定義(0≦r≦b-1)もされているが、感覚的な理解ではこれでよい。別な解釈を言えば、a-rが自然数bで割り切れるときのこの式のことを合同式というのである。後者の解釈でいえば複雑な商と余りの定義を持ち込む必要はなくなるから、このように簡潔に書いている教科書もある。

簡単に覚えよう。要するに合同とはそれほど難しいものではく、定義の厳密化である。これは最初にドイツの数学者ガウス(Carolus Fridericus Gauss)によって考えられたそうである。で、覚え方。この=を合同の定義としてはみないで、mod b、というように自然数bでaを割ったとき、余りがrになる定義である。要するにaの割り算の余りをa≡rであると考えれば簡単に覚えられる。これが合同のありかただ。

ユークリッド互除法とは、

あるふたつの整数aとbがあり、
aをbで割ったなら、r(a>b>0かつr≧0)が余り
になるとき…
GCD(a,b)=GCD(b,r)

この証明ははっきりいって面倒だ。だが触れておこう。この問題は実はその定義に帰ることになる。互除法とは互いに演算することで差し引き会うものになっているからだ。この語源がそのまま互除法という言葉になっている。一番簡潔な証明はこうだ。

a=qb+r・・・(1)
(1)より、
r=a-qb・・・(2)
(ここで先ほどの合同式の定義を思い出してほしい…感覚的に頭の中であれを行う…)
GCD(a,b)=m ・・・(3) GCD(b,r)=n・・・(4)とすると、
(1)(3)(4)よりa=qb+r=q(An)+(Qn)となる互いに素であるA・Qを用いて、
a=n(An+Q)となるので、nはaの約数となる。さらに、GCD(a,b)=mだからm≧nとなる。・・・(5)
(2)(3)(4)よりr=a-qb=(Bm)-q(Rm)となる互いに素であるB・Rを用いて、
r=m(B-Rm)となるので、mはrの約数となる。さらに、GCD(b,r)=nだから、n≧mとなる。・・・(6)
(5)(6)よりm=n[証明終]

ここまでくれば、なぜ互除法と呼ばれるのか、また、この証明がなぜ幾何学的な観点から導かれた、ユークリッドの展開的な数学なのかがわかるはず。これほど古代の数学者たちは偉大だったのだ。次はユークリッドの互除法展開から行こうか。ここは定義だけおさえる。これを、ユークリッド互除法の拡張・拡張ユークリッドの互除法などという。

「整数m,nのGCD(m,n)のとき、mx+ny=GCD(m,n)となるような整数xとyとの組みが見つかる」

オイラーの定理はφとか使って、素の数を表していくから、面倒だが、こういう証明はある。
http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Euler.html
これは合同から証明を表したもので、Wikipediaの数論の証明項目にもちょうど同じ物が記載されている。ぜひ参照されたし。ネットの情報をつかうのもそれなりに重要だ…。オイラー関数φと同じくして覚えよ。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA