５×５×５×５×５×５×５×５×５×５×５×５×５×
５×５×５ は 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法の暗号を解読するプログラム
「計算可能性」
•算法（アルゴリズム）の作成が不可能という問
題は，すでに発見済みである
人間にもコンピュータにも解けない問題
チューリングマシンの停止判定
8
全体まとめ
•算法（アルゴリズム）
※ コンピュータは，ある定まった手順により問題を解く
プログラムの見通しの良さ，性能向上，バグの防止に役立つ
•算法（アルゴリズム）を駆使しても， 解くのに時間がかかり
すぎるため難しいという問題がある
このことは，暗号の基礎として役立つ
9
