「セキュア・パズル 第10章 フェルマーの小定理2 (2023/05/06)」
デジタル・セキュア・パズル
第10章 RSA暗号 フェルマーの小定理2



前回は、最大12ターン勢につき
m12 = 1 mod 13
m = 2,6,7,11
を証明しましたが。
その他の
m12 = 1 mod 13
m = 3,4,5,8,9,10
に関しては:
最大12ターンの「急行」として解釈できる。
急行は12/kで一周するので、
やっぱり
m1+12/k = m mod 13
m12/k = 1 mod 13
m12 = 1 mod 13
結局。全てのmにつき
m12 = 1 mod 13
が成立する。
これがフェルマーの小定理
mp-1 = 1 mod p
が成立する理由です。