フェルマーの小定理

ｐを素数、aを任意の整数とするとき

a^p-1-1=0 (modp)

例:　17は素数なので、1^16-1,2^16-1,3^16-1,・・・,16^16-1,18^16-1,・・・

はすべて17の倍数である。

たとえば、16^16-1=18446744073709551615を17で割ると、1085102571150095

17^16-1は17で割り切れない。17の倍数である17^16より1小さいため17の倍数ではありえない

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

オイラーの定理

(a,n)=1のとき、

a^φ(n)-1-1=0 (modｎ)

ｐ、ｑを素数,n=pqとするとφ(n)=(p-1)(q-1)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

RSA暗号

(1)２つの大きな素数p,qを見つける

(2)n=pq

(3)φ(n)=(p-1)(q-1)を計算して、それは秘密にする

(4)φ(n)と互いに素である数eを選ぶ

(5)de=1 (modφ(n))となるdを計算する

(6)eは公表しても構わない

(7)dは秘密にしておく(重要)

(8)平文をｒ、ｎを法とする

(9)ｒをr^e (mod　ｎ)に変換する（暗号化はe乗する、この規則も公表してかまわない）

(10)暗号文r^eを復号化するにはこれをｄ乗する（復号化はd乗する、ｄは秘密）

(11)ｒ^ed=r （オイラーの定理）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝