アルゴリズム論特論(塩田) 2016年度教材 第4回

  • 授業内容
  • ツボ
    • 加法・減法・乗法に関して、合同式はイコール感覚で使える

  • 問題
    • 下記の素数 p たちについて、a = 2 の場合のフェルマの小定理
            2p - 1 ≡ 1 ( mod p )
      を確かめてみよ。 (無理な場合は潔く諦めよう。)
    • (1)  p = 607 ( 10-bit )
      (2)  p = 552259 ( 20-bit )
      (3)  p = 900949267 ( 30-bit )
      (4)  p = 660768960311 ( 40-bit )
      (5)  p = 661425977735249 ( 50-bit )

戻る