Algorithm - Python - 暗号の歴史あれこれ - ユークリッドさん、お母さんを助けて - 素因数分解暗号

中学数学からはじめる暗号入門
~現代の暗号はどのようにして作られたのか~
楽天ブックス Yahoo!

学習環境

• Surface、Surface ペン(端末)
• Windows 10 Pro (OS)
• Nebo(Windows アプリ)
• iPad Pro 10.5 + Apple Pencil
• MyScript Nebo - MyScript(iPad アプリ(iOS))
• 参考書籍
  • Pythonからはじめる数学入門 (楽天ブックス Yahoo!)
  • JavaScriptリファレンス 第6版 (楽天ブックス Yahoo!)
  • インタラクティブ・データビジュアライゼーション (楽天ブックス Yahoo!)

中学数学からはじめる暗号入門 ~現代の暗号はどのようにして作られたのか~ (知りたい!サイエンス 141) (関根 章道(著)、技術評論社))の前編(暗号の歴史あれこれ)、第5章(ユークリッドさん、お母さんを助けて)の暗号を作って解いてみよう - Part 6(素因数分解暗号)の解答を求めてみる。

$\begin{array}{l}439022\\ =2·\; <!--\; middle\; dot\; -->219511\\ 126362\\ =2·\; <!--\; middle\; dot\; -->63181\end{array}$

219511と 63181 の最大公約数を求める。

$\begin{array}{l}219511=63181·\; <!--\; middle\; dot\; -->34+2557\\ 63181=2557·\; <!--\; middle\; dot\; -->24+1813\\ 2557=1813·\; <!--\; middle\; dot\; -->1+744\\ 1813=744·\; <!--\; middle\; dot\; -->2+325\\ 744=325·\; <!--\; middle\; dot\; -->2+94\\ 325=94·\; <!--\; middle\; dot\; -->3+43\\ 94=43·\; <!--\; middle\; dot\; -->2+8\\ 43=8·\; <!--\; middle\; dot\; -->5+3\\ 8=3·\; <!--\; middle\; dot\; -->2+2\\ 3=2·\; <!--\; middle\; dot\; -->1+1\\ 2=1·\; <!--\; middle\; dot\; -->2+0\end{array}$

よって最大公約数は1。

ゆえに、439022と126362の最大公約数は2。

それぞれを2で割った数を素因数分解。

$\begin{array}{l}219511\\ =31·\; <!--\; middle\; dot\; -->7081\\ =31·\; <!--\; middle\; dot\; -->73·\; <!--\; middle\; dot\; -->97\\ 63181\\ =23·\; <!--\; middle\; dot\; -->2747\\ =23·\; <!--\; middle\; dot\; -->41·\; <!--\; middle\; dot\; -->67\end{array}$

よって問題の2つの数の素因数分解は、

$\begin{array}{l}439022=2·\; <!--\; middle\; dot\; -->31·\; <!--\; middle\; dot\; -->73·\; <!--\; middle\; dot\; -->97\\ 126362=2·\; <!--\; middle\; dot\; -->23·\; <!--\; middle\; dot\; -->41·\; <!--\; middle\; dot\; -->67\end{array}$

暗号を解読。

akuy、 aims。

並べ替え。 （アナグラム）

yakusima、屋久島。

コード

Python 3

#!/usr/bin/env python3
from sympy import pprint, primerange, primefactors

a = 439022
b = 126362
d = {p: chr(ord("a") + i) for i, p in enumerate(primerange(2, 102))}

anagram = []

for t in [a, b]:
    anagram += [d[p] for p in primefactors(t)]

print(anagram)

入出力結果(Bash、cmd.exe(コマンドプロンプト)、Terminal、Jupyter(IPython))

$ ./sample2.py
['a', 'k', 'u', 'y', 'a', 'i', 'm', 's']
$