アルゴリズム論特論（塩田）　2017年度教材　第6回

  • 子供の知識の復習
    • 順列の数 nPk は何を数えているか
    • 二項係数 (n k) = 組合せの数 nCk は何を数えているか
    • nPk を階乗を用いて表す公式
    • nCk を階乗を用いて表す公式
    • nCk = n-1Ck-1 + n-1Ck が成り立つことの説明
    • nC0 + nC1 + … + nCn = ?
    • nC0 - nC1 + … + (-1)nnCn = ?
    • n×nCn + (n-1)×nCn-1 + … + 1×nC1 = ?

  • 授業内容
    • フェルマの小定理
      • ver.1 : p が素数ならば、全ての整数 a について ap ≡ a ( mod p) が成り立つ
      • ver.2 : p が素数ならば、p で割り切れない全ての整数 a について ap－1 ≡ 1 ( mod p) が成り立つ
    • フェルマの小定理の、二項係数と帰納法による証明

  • ツボ
    • ユークリッドのアルゴリズムとフェルマの小定理がわかれば、RSA暗号の設計が理解できるはず。

戻る