合同式について - 小西研究室@電脳工房ＭＳＣ

第2章．RSA暗号入門

定義．

整数 $a,b$ に対して， $b\ne0$ であり，かつ，ある整数 $q$ により
　　 $a=qb$
と表されるとき， $a$ は $b$ で割り切れる，そして， $b$ は $a$ を整除するという．
また， $a$ を $b$ の倍数，そして， $b$ を $a$ の約数（または因数）という．

命題（割り算）

整数 $a$ と自然数 $b$ に対して， $a=qb+r,0 \le r<b$ 　を満たす整数 $q,r$ がただ一組存在する。

定義．

命題１の $q$ を， $a$ の $b$ による割り算の商，または，整商といい， $r$ をその余りという．

定義．

整数 $a,b$ に対して， $a\ne0$ または $b\ne0$ のとき，それらの共通の約数のうちで最大のものを最大公約数といい， $(a,b)$ と書き表わす．

定義．

整数 $a,b$ の最大公約数が１である，すなわち $(a,b)=1$ のとき， $a$ と $b$ は互いに素であるという．

命題（ユークリッドの互除法）

自然数 $a,b$ に対して，次の操作を考える：
（Step1）　 $a$ の $b$ による割り算の余りを $r_1$ とする
（Step2）　 $b$ の $r_1$ による割り算の余りを $r_2$ とする
（Step3）　 $r_1$ の $r_2$ による割り算の余りを $r_3$ とする
　　　 $\vdots$ 　　　　　
　以下、同様にして、 $r_{i-1}\ne0$ である限り
（Stepi）　 $r_{i-2}$ の $r_{i-1}$ による割り算の余りを $r_i$ とする
を、 $i$ の値を１ずつ増やしながら繰り返す。
このとき、次が成り立つ：
(1)　ある有限回目のStepにおいて、余り $r_i$ は必ず０となる．
(2) $r_{n+1}=0$ とすると、 $(a,b)=r_n$ 、すなわち、 $r_n$ は $a,b$ の最大公約数となる．

これを式で書き下すと、
　　　 $a\div b=q_1 \dots r_1,\\\\\\\ r_1<b \Longleftrightarrow a=q_1b+r_1$

b÷r1＝q2…r2,   	r2<r1 			b=q2r1+r2  
r1÷r2＝q3…r3,   	r3<r2 			r1=q3r2+r3  

rn-2÷rn-1＝qn…rn,  rn<rn-1 		rn-2=qnrn-1+rn  
rn-1÷rn＝qn+1,  	rn+1=0			rn-1=rn+1rn

と余りが０になった時点でのrnが、aとbの最大公約数になるのである。

定義（合同式）

自然数nと整数a、ｂに対して、差a-bがnの倍数であるとき、aとbとはnを法として合同であるといい、

	a≡b　 (mod n)

とかく。つまり、nで割り算して余りが等しいとき、そして、その時に限り、nを法として合同であるという。

例．　条件　x≡3 (mod 5) , 14≦ｘ≦19　を満たす整数xを求める。

x≡3 (mod 5)とは、x－3が５の倍数、ということだから、
　　x＝3+5k、（kは整数）
と表わされる。したがって、
　　14≦3+5k≦19
を満たすkを求めればよい。これは、k＝3となり、ｘ＝１８となる。

命題（合同式の加減算）

自然数nと整数a, a’, b, b’ に対して、a≡a’, b≡b’ (mod n) ならば、

a + b≡a’ + b’ ,  a – b≡a’ – b’ ,  ab≡a’b’  (mod n)

命題の系（べき）

自然数nと整数a, a’ に対して、a≡a’ (mod n) ならば、任意の自然数mに対して、

am ≡a’m   (mod n)

命題（除）

自然数nと整数a, b, c に対して、(c, n)=1 ならば、

ac≡bc  (mod n)  ⇒　a≡b  (mod n)

「合同式について」をウィキ内検索

最終更新：2010年11月30日 14:48