[color=#0000ff]まずは数学的「モデル」としてフェルマーの小定理を調べてみよう。[/color]
RSA暗号
ＲＳＡ暗号のしくみを探っていると、初等整数論にたどり着く。 そのポイントは「フェルマーの小定理」。 「フェルマーの小定理」は剰余類を探っていると体験的につかめる。 次は素数でない場合はどうなるのかと拡張したくなる。 実際に拡張した人がオイラーでこの定理を「オイラーの（小）定理」という。 さらにオイラー関数も導ける。 そして、この「オイラーの小定理」から、ＲＳＡ暗号を簡単に導くことができる。
Table of Contents
- フェルマーの小定理
- フェルマーの小定理
- フェルマーの小定理 表計算
- フェルマーの小定理の確かめ
- フェルマーの小定理 証明
- 百五減算と合同式の使い方
- P元体
- オイラーの小定理
- フェルマーの小定理の拡張
- フェルマーの小定理を拡張してみよう
- 素因数分解
- Eulersche Phi Funktion (Euler's Totient Function) のコピー
- ＲＳＡ暗号
- フェルマーの小定理からRSA暗号をどうつくるか
- RSA暗号のしくみ
フェルマーの小定理
「知ることは作ること」 RSA暗号を理解するためには実際に作ってみるのが一番いい。
フェルマーの小定理。これは、例えば「８を１０乗した数は１１で割ると１あまる」ということを一般化したもの。数値を入れて確かめると、条件がみえてくる。
フェルマーの小定理の拡張
人間は演繹では理解できない。帰納することでしか先へ進めない。訂正「対称化」⇒「対象化」
[br]
法を素数以外にしたときに、同じことが言えないか？
オイラーの小定理を導く
素数の場合はｐ－１個の積が一緒になったけど、[br]この場合のように９を法とすると、３や６の時は０（と３と６）が出てくる。[br]でも、それ以外は同じ値が繰り返されている。[br]とすると、３や６を除いた数の積は同じ値だ。[br][br]つまり、フェルマーの小定理（の拡張）を導くことができる。[br]オイラーはこうやって計算しながら表をつくり、法則を見つけていったのだろう。[br][br]９と互いに素な数の剰余の積は同じ値になる。[br] ↓ つまり[br]１・２・４・５・７・８≡１ｍ・２ｍ・４ｍ・５ｍ・７ｍ・８ｍ (mod 9)[br]１・２・４・５・７・８≡ｍ[sup]６[/sup]・１・２・４・５・７・８ (mod 9)[br]１≡ｍ[sup]６[/sup] (mod 9)[br]この６は９と互いに素な数の個数（９以下の）。[br]それをφ（ｎ）［オイラー関数］とすると、[br]ｍ[sup]φ（ｎ）[/sup]≡１ (mod ｎ)[br]が言えそう。[br][br]
フェルマーの小定理からRSA暗号をどうつくるか
p×ｑを法とする
m[sup]p-1[/sup]≡1 (mod p) ⇒ m[sup]p-1[/sup]-1は pで割り切れる[br]m[sup]q-1[/sup]≡1 (mod q) ⇒ m[sup]q-1[/sup]-1は qで割り切れる[br]では、mod (p·q)にするにはどうしたら良いか？[br] つまりpでもqでも割り切れる数は？[br][br]m[sup](p-1)(q-1)[/sup]-1を考えてみると、[br](m[sup](p-1)[/sup])[sup](q-1)[/sup]-1は qで割り切れる。[br](m[sup](q-1)[/sup])[sup](p-1)[/sup]-1は pで割り切れる。[br]よってm[sup](p-1)(q-1)[/sup]-1は p·qで割り切れる。（p·q=nとおく）⇒ m[sup](p-1)(q-1)[/sup]≡1 (mod n)[br]ここで、（ ）≡m にするために、両辺にmをかける。[br]m[sup](p-1)(q-1)[/sup]·m≡m (mod n)[br]m[sup](p-1)(q-1)+1[/sup]≡m (mod n)[br]この時、(p-1)(q-1)+1＝e·dとすると、(m[sup]e[/sup])[sup]d[/sup]≡m (mod n)となる。[br][br]