「セキュア・パズル 第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
が成立する理由です。