今回はハノイの塔を解くプログラムについてです。


解説動画はこちら

# ハノイの塔を攻略
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"{n}を{source}から{target}に移動")
        return
    hanoi(n-1, source, auxiliary, target)
    print(f"{n}を{source}から{target}に移動")
    hanoi(n-1, auxiliary, target, source)

n = 3
hanoi(n, 'A', 'C', 'B')

ハノイの塔を描画するコード

widgetsを使ってstepごとの画像を描画しています。

# ハノイの塔を描画する
import ipywidgets as widgets
import matplotlib.pyplot as plt
import numpy as np

data,img_data = [],[]

# ディスクの色リスト
colors = ['red', 'green', 'blue', 'purple', 'yellow', 'silver', 'orange', 'pink']

# 棒の位置
positions = {'A': 0, 'B': 1, 'C': 2}

# ハノイの塔を攻略
def hanoi(n, source, target, auxiliary):
    if n == 1:
        data.append([n,source,target])
        return
    hanoi(n-1, source, auxiliary, target)
    data.append([n,source,target])
    hanoi(n-1, auxiliary, target, source)

# ディスクを描画するための関数
def draw_towers(state, step):
    fig, ax = plt.subplots()
    ax.set_xlim(-1, 3)
    ax.set_ylim(0, 5)
    ax.set_xticks([0, 1, 2])
    ax.set_xticklabels(['A', 'B', 'C'])
    ax.set_yticks([])
    for tower in 'ABC':
        for j, disk in enumerate(state[tower]):
            color = colors[disk - 1]
            width = 0.2 * disk
            height = 0.5
            ax.bar(positions[tower], height, bottom=j * height, width=width, color=color, edgecolor='black')
    ax.set_title(f'Step {step}')
    fig.canvas.draw()
    img_data.append(np.array(fig.canvas.renderer.buffer_rgba()))
    plt.close(fig)

# 初期状態
n = 4  # ディスクの数
hanoi(n, 'A', 'C', 'B')
towers = {'A': list(range(n, 0, -1)), 'B': [], 'C': []}
draw_towers(towers, 0)

# 各ステップごとに状態を描画
for step, (disk, source, target) in enumerate(data):
    towers[target].append(towers[source].pop())
    draw_towers(towers, step+1)

# img_data に保存された画像を表示するためのウィジェット
def show_image(step):
    plt.imshow(img_data[step])
    plt.axis('off')
    plt.show()

slider = widgets.IntSlider(value=0, min=0, max=len(img_data)-1, step=1, description='Step:')
widgets.interactive(show_image, step=slider)

タグ ：

#Python

#プログラミング

#パズル

#ハノイの塔

#アルゴリズム

今回はRSA暗号について
考えてみることにしました。


解説動画はこちら


さてさて
RSAッて良く分からないので
Wikiで調べてみることにしました。


うん・・・・・








はい良くわかりませんです！！！


というわけで
サンプルコードを作ってみました。

# RSA暗号の例
import random
import fractions
import sympy
import warnings 
warnings.filterwarnings('ignore')

# 乱数生成
def _random():
    digit = 10
    return random.randrange(10**(digit - 1),10**digit)

# 最小公倍数
def _lcm(p , q):
    return (p * q) // fractions.gcd(p, q)

# 拡張ユークリッド
def _euclid(x,y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
    return c0, a0, b0

# キー生成
def generate_key(p = 0,q = 0,e = 0,d = 0,n = 0,l = 0):
    if p == 0:
        while True:
            p = _random()
            if sympy.isprime(p):break
    _p = p
    if q == 0:
        while True:
            q = _random()
            if sympy.isprime(q) and p != q:break
    _q = q
    if n == 0:
        n = p * q
    _n = n
    if l == 0:
        l = _lcm(p - 1, q  - 1)
    _l = l
    if e == 0:
        while True:
            i = random.randint(2,l)
            if fractions.gcd(i, l) == 1:
                e = i
                break
    _e = e
    if d == 0:
        _c, a, _b = _euclid(e, l)
        d = a % l
    _d = d
    return _e,_d,_n,_p,_q,_l

# 暗号化
def encrypt(_e,_n,plaintext):
    st,ciphertext = "",[]
    for i in map((lambda x: pow(ord(x), _e,_n)),list(plaintext)):
        ciphertext.append(i)
        st += str(i)
    return st,ciphertext

# 復号化
def decrypt(_d,_n,ciphertext):
    cip , st = [] , ""
    for i in  list(ciphertext):
        tmp = chr(pow(i, _d,_n))
        cip.append(tmp)
        st += str(tmp)
    return st

使う際は平文として暗号化したい
文字列を定義しておきます。

plain_text = '文字列を入力'

早速使っていきましょう。
暗号化するところと
復号化するところのコードです。

# 初期化
ciphertext = []
_e = _d = _n = _p = _q = _l = 0

# キー生成
_e,_d,_n,_p,_q,_l = generate_key(0,0,65537)

# 暗号化
e_text , ciphertext = encrypt(_e,_n,plain_text)

# 復号化
d_text = decrypt(_d,_n,ciphertext)

print('素数 p : {0}'.format(_p))
print('素数 q : {0}'.format(_q))
print('l : {0}'.format(_l))
print('公開鍵 e : {0}'.format(_e))
print('公開鍵 n : {0}'.format(_n))
print('秘密鍵 d : {0}'.format(_d))
print()

print('暗号文(String) : {0}'.format(e_text))
print()
print('暗号文(List) : {0}'.format(ciphertext))

素数P,Qや
鍵N,Dは毎回変わってしまいます。

公開鍵Nと秘密鍵Dがあれば
暗号を解読することができます。

暇な方は上記の鍵と暗号文から
復号してみてくださいね。

人類を平和にする
「あいことば」を暗号にしてみましたよ

解読面倒な方は
動画見て下さいねーー


このサンプルコードでは
およそ20桁ほどの秘密鍵になりますんで
9千京回ほどブルートフォースすれば
暗号解読できるかもしれません！！！！

鼻血出せば解けるかもしれませんねえ
そんなアニメが有るとか無いとか

自分ならやらないっすねーー

今回はここまででーす
それでは。

タグ ：

#Python

#プログラミング

#暗号

#RSA

#アルゴリズム

最近どこかのブログで
素数を求めるコートが載っていました。

今回はいろんなコードで
素数を求めてみます。

コードによる計算回数の違いや
速度なんかが気になってしまいました。

解説動画はこちら



さて素数ですが知らない人は
ほとんどいないと思いますが

そんな素数を求めるコードを考えてみましょう。

まずは2からその素数まで愚直に割っていきます。
素数の候補は6桁の素数である999983です

これが素数かどうかを判定していきます。


1.愚直に割って求めるプログラム

def isPrime1(num):
    count = 0
    if num<2:
        return False
    for k in range(2,num):
        count+=1
        if num % k==0:
            return False
    #print(count)
    return True

%timeit -n1 isPrime1(999983)

Jupyter Notebookでは

%timeit -n回数 コード

と書いて実行すると
そのコードを何回か実行して
その計算時間を測ってくれます。

この場合の計算回数は999981回でした。
その素数の数と同じような計算回数ですね。
非常に時間がかかっています。

つぎは計算回数を減らしてみましょう。
割るのをその候補のルートを取った
数までにしてみます。

2.計算回数を減らしてみる

import math

def isPrime2(num):
    count = 0
    if num<2:
        return False
    for k in range(2, int(math.sqrt(num)) + 1):
        count+=1
        if num % k == 0:
            return False
    #print(count)
    return True

%timeit -n1 isPrime2(999983)

これで計算回数も大幅に減り
998回まで減りました。

実行速度の方もmsからμsまで減っています。
大幅な速度アップですね。

それでも割るのは無駄が多いです
2で割れたら素数では無いので
改めて偶数で割る必要は無いですよね。

偶数を抜いて割るのを奇数だけにしてみます。

3.割るのは奇数のみにしてみる

import math

def isPrime3(num):
    count = 0
    if num==2:
        return True
    if num<2 or num%2==0:
        return False
    for k in range(3, int(math.sqrt(num)) + 1,2):
        count+=1
        if num % k == 0:
            return False
    #print(count)
    return True

%timeit -n1 isPrime3(999983)

さて奇数で割るだけにしただけでも
かなり早くなりましたが、それでも
まだまだ無駄があります。

5で割り切れるなら改めて
15で割る必要は無いですよね。

割るのを奇数から
素数だけにしてみましょう。


4.あらかじめ素数を用意しておき
割るのを素数だけにする

def isPrime3_2(num):
    if num==2:
        return True
    if num<2 or num%2==0:
        return False
    for k in range(3, int(math.sqrt(num)) + 1,2):
        if num % k == 0:
            return False
    return True

prime_numbers = [i for i in range(2,999983+1) if isPrime3_2(i)]

あらかじめ沢山の素数を用意しておきます。
改めて素数だけで割ってみます。

def isPrime4(num):
    count = 0
    if num<2:
        return False
    elif num==2:
        return True

    m = math.floor(math.sqrt(num))
    for p in prime_numbers:
        count+=1
        if num % p == 0:
            return False
        if p > m:
            # 素数がnの平方根を超えたら終了
            break
    #print(count)
    return True

%timeit -n1 isPrime4(999983)

12.2 µs ± 1.35 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

計算回数も169回と大幅削減ですが
最初に素数を沢山用意しておくのがネックです

素数計算を沢山やる必要があるなら
プログラムとしては許せますが
桁が多くなったりすると対応しきれません。

そんな訳で最後の手です。

5. from sympy import isprimeを使ってみる

sympy はPythonで
記号計算を行うためのライブラリです。

その中には素数を求めるメソッドが
あらかじめ用意されています。

isprime

これを使ってみましょう。

from sympy import isprime

%timeit -n1 isprime(999983)

さて、計算回数は分かりませんが
実行時間は先ほどの素数をあらかじめ用意したものと
さほど変わりません。

であれば、Pythonでは
わざわざ素数を求めるような
関数とか作る必要が無いですねーーー

githubに関数のソースがあるようなので
みてみると良いかもしれないですね。
sympyのソース


ということでまとめです。
こういった素数を求める関数を作るような事を
車輪の再発明と言います。

勉強のためであれば
良いとは思いますが業務で行う場合は
時間の無駄になる事がほとんどです。

こういった課題というのは時折
コードを書かせる試験などで
用いられるようですが

入社後はあまり役には
立たないかもしれませんね。

システム開発の際は
車輪の再発明にならないように
色々と調査をしておくと
無駄が少なく工数を節約できる
こともあるので日々の情報収集は
大事ですね。

今回はこれまでです
それでは。

タグ ：

#Python

#プログラミング

#素数

#アルゴリズム