アルゴリズム - 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章(ユークリッドさん、お母さんを助けて)の最大公約数、素因数分解(68ページ)の解答を求めてみる。

$\begin{array}{l}1615=1547·\; <!--\; middle\; dot\; -->1+68\\ 1547=68·\; <!--\; middle\; dot\; -->22+51\\ 68=51·\; <!--\; middle\; dot\; -->1+17\\ 51=17·\; <!--\; middle\; dot\; -->3+0\end{array}$

よって、最大公約数は17。

素因数分解はそれぞれ、

$\begin{array}{l}1615=5·\; <!--\; middle\; dot\; -->17·\; <!--\; middle\; dot\; -->19\\ 1547=7·\; <!--\; middle\; dot\; -->13·\; <!--\; middle\; dot\; -->17\end{array}$

コード

Python 3

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

ns = [1615, 1547]

for o in [gcd(*ns)] + [(n, primefactors(n)) for n in ns]:
    pprint(o)
    print()

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

$ ./sample1.py
17

(1615, [5, 17, 19])

(1547, [7, 13, 17])

$