2019年8月13日火曜日

学習環境

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

439022 = 2 · 219511 126362 = 2 · 63181

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

219511 = 63181 · 34 + 2557 63181 = 2557 · 24 + 1813 2557 = 1813 · 1 + 744 1813 = 744 · 2 + 325 744 = 325 · 2 + 94 325 = 94 · 3 + 43 94 = 43 · 2 + 8 43 = 8 · 5 + 3 8 = 3 · 2 + 2 3 = 2 · 1 + 1 2 = 1 · 2 + 0

よって最大公約数は1。

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

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

219511 = 31 · 7081 = 31 · 73 · 97 63181 = 23 · 2747 = 23 · 41 · 67

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

439022 = 2 · 31 · 73 · 97 126362 = 2 · 23 · 41 · 67

暗号を解読。

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']
$ 

0 コメント:

コメントを投稿

関連コンテンツ