第1回 四則演算の計算量 (4.16)

• 授業内容
  • 慣用記号
  • 自然数 n のビット長 = O(log n)
  • 2進数の計算問題 exercise01.pdf をやってみよう。
  • Wikipedia で 加算器の構造 を見てみよう。
  • 四則演算の計算時間を計測する Python プログラム operations.py
  
  
• ツボ
  • y = log x のグラフの真の姿
  • log の関数値は極めて小さい
  • n 以下の２つの正整数の四則演算の計算量は
    • 加法, 減法： O(log n)
    • 乗法, 除法： O(log²n)

第2回 最大公約数 (4.23)

• 授業内容
  • てんびんクイズ
    • 問：十分大きな天秤と、a グラムと b グラムの分銅がたくさんあるとき、測ることのできる最小の重さはいくらか？
    • 予想：a と b の最大公約数
  • 最大公約数 gcd, 最小公倍数 lcm
    • a, b の任意の公倍数は lcm(a, b) の倍数
    • a, b の任意の公約数は gcd(a, b) の約数
    • gcd, lcm は「単なる大小関係」で定義したのに整除関係を導く
• ツボ
  • 2つの自然数 a, b に対して次の2つの集合は一致する：
    • a x + b y ( x, y は整数 ) の形で書ける整数全体の集合
    • gcd(a, b) の倍数全体の集合
  • 特に、a, b を与えたとき、gcd(a, b) = a x + b y を満たす x, y が必ず存在する。

第3回 ユークリッドのアルゴリズム (5.14)

• 授業内容
  • 素因数分解がわかっているときの gcd, lcm
  • ユークリッドのアルゴリズム
    • gcd のみ求めるアルゴリズム
    • gcd(a, b) = a x + b y を満たす x, y も求めるアルゴリズム
• ツボ
  • RSA暗号の計算には gcd や上記の x が必要。
  • RSA暗号は素因数分解の困難さに基づくので、gcd を素因数分解で求めるのはナンセンス。
  • そこでユークリッドのアルゴリズムが必要になる。

第4回 ユークリッドのアルゴリズムの計算量・再帰 ver. (5.21)

• 授業内容
  • ユークリッドのアルゴリズムの計算量
  • ユークリッドのアルゴリズムの再帰 version
    • サンプルプログラム
    • 課題
• ツボ
  • ユークリッドのアルゴリズムの入力を a, b ( a > b > 0 ) とするとき、その計算量は O(log²a)

第5回 法演算、九去法 (5.28)

• 授業内容
  • 合同式の定義
  • 法演算
  • 九去法
  • フェルマの小定理
• ツボ
  • 加法・減法・乗法・べき乗に関して、合同式はイコール感覚で使える

第6回 法 n での除算 (6.4)

• 授業内容
  • 割り算と除算の違い
  • mod n での逆数
• ツボ
  • mod n で 1/b が存在 ⇔ gcd(b, n) = 1

第7回 剰余類、オイラーの定理、べき乗による変換 (6.11)

• 授業内容
  • 剰余類、既約剰余類
  • オイラー関数　φ(n) = ( 法 n の既約剰余類の個数 )
  • オイラーの定理　gcd(a, n) = 1 ⇒ 法 n で a ^φ(n) = 1
  • 命題　 p が素数で、e, d が ed ≡ 1 ( mod (p-1) ) を満たす自然数ならば、
    任意の整数 x に対して  x^ed ≡ x ( mod p )
• 宿題
  • 次の暗号は公開鍵暗号になり得るか？
    • 平文集合　 P = {0, 1, ..., p-1}
    • 暗号文集合 C = {0, 1, ..., p-1}
    • 暗号化関数 E(x) = x^e % p
    • 復号化関数 D(y) = y^d % p
• ツボ
  • フェルマの小定理は、オイラーの定理で n が素数の場合
  • オイラーの定理は群論的に証明される

第8回 RSA 暗号の設計、高速べき乗法(6.18)

• 宿題の答え
  • 答えは否。暗号化に必要な暗号化指数 e と法 p は公開しなければならないが、 e と p-1 を拡張ユークリッドアルゴリズムに入力することによって復号化指数 d が高速に求められるので。
• 授業内容
  • RSA暗号
  • 高速べき乗法（反復2乗法）
  • 破られ易い鍵
  • p, q がほとんど同じビット数のもの(フェルマ法, H28年度、田中の卒業論文)
  • p と, q の簡単な有理数倍がほとんど同じビット数のもの(拡張フェルマ法, H29年度、池内の卒業論文)
  • p-1 が小さな素因数しか持たないもの(p-1法)
  • p+1 が小さな素因数しか持たないもの(p+1法, H27年度、寺本の卒業論文)
  • 有名な素数を用いたもの etc.
• ツボ
  • RSA暗号の解読は、素因数分解と同程度に困難である。
  • 暗号設計に必須な x^e % n の計算は、2乗を巧みに使って高速化できる。
  • RSA暗号と言えども、不用意に鍵を作ると危ない。

第9回 素数生成 (6.25)

• 授業内容
  • 擬素数
  • フェルマ・テストによる素数判定
  • 素数定理
  • カーマイケル数
• ツボ
  • 素数判定・素数生成も、高速べき乗法の応用で実装できる。
  • フェルマ・テストによる素数生成の計算量は O(log⁴n)
• 宿題
  • RSA暗号の鍵 p, q, n, e, d を、p が 510ビット、q が 520ビット程度になるように生成し、 公開鍵 n, e を塩田に送信せよ。秘密鍵は各自保管しておくこと。
  • 折り返し塩田から暗号文を返送するので復号せよ。 正しく復号できれば復号文は８桁の数字になり、西暦４桁＋月２桁＋日２桁である著名人の誕生日を表している。 その著名人を答えよ。

第10回 mod p の乗法構造 (7.2)

• 授業内容
  
  • 元の生成する部分群
  • 元の位数
  • mod p の原始根
  • 離散対数問題
  • プリント

第11回 Diffie-Hellman 鍵交換システム (7.9)

• 授業内容
  
  • Diffie-Hellman 鍵交換システム
  • 原始根の作り方