５×５×５×５×５×５×５×５×５×５×５×５×５×
５×５×５ は 152587890625
2
掛け算: 4 回
掛け算: 15 回
算法（アルゴリズム）の工夫で，掛け算の回数を削減できる場合がある
同じ
結果
算法（アルゴリズム）の例
次の２つのプログラムは，同じ答えが出る．
a = 5 * 5
b = a * a
c = b * b
d = c * c
print(d)
print(5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5)
3
次の２つのプログラムは，同じ答えが出る
a = 10 * 10
b = a * a
c = b * b
print(c)
print(10*10*10*10*10*10*10*10)
4
暗号を作成する Python プログラム
参考ウェブページ
http://nbviewer.jupyter.org/github/yoavram/CS1001.py/blob/master/recitation4.ipynb
5
Diffie-Hellman法で暗号化（Pythonを使用）
暗号を解読する Python プログラム
参考ウェブページ
http://nbviewer.jupyter.org/github/yoavram/CS1001.py/blob/master/recitation4.ipynb
6
Diffie-Hellman法の暗号を解読するプログラム
暗号作成より，暗号解読の方が手間がかかる
• 暗号解読の算法（アルゴリズム）は発見済み ということが多い
→ プログラムを作成可能
• しかし，プログラムが答えを出すまでに時間がかかる場合がある
すでに，2012 年に，このようなレポートが．
（https://www.dit.co.jp/service/security/report/03.html）
英大小文字+数字+記号を組み合わせた ZIP のパスワード
６桁の解読時間： ２分２４秒 ＝ 超危険
８桁の解読時間： １４日 ＝ 危険
１０桁の解読時間： ３４１年
7
「計算可能性」
• 算法（アルゴリズム）の作成が不可能という問
題は，すでに発見済みである
人間にもコンピュータにも解けない問題
チューリングマシンの停止判定
8
全体まとめ
• 算法（アルゴリズム）
※ コンピュータは，ある定まった手順により問題を解く
プログラムの見通しの良さ，性能向上，バグの防止に役立つ
• 算法（アルゴリズム）を駆使しても， 解くのに時間がかかり
すぎるため難しいという問題がある
このことは，暗号の基礎として役立つ
9
