サマーウォーズのあの暗号を解こう!(その3)

こちらの続き。
秘密鍵N(=pq)がとある数字で割り切れた。大きな方の値(前の記事ではqとした)が素数なのかどうか、という件。

ミラー・ラビン素数判定法をググったらPythonの実装サンプルが見つかったのでありがたく使わせていただくことにする。

Miller–Rabin(ミラーラビン)素数判定法について理解したい
https://qiita.com/zu_rin/items/25521b5870389e0f85bf

実際に使ったコードは次の通り。

import random

def Miller_Rabin_test(num):
    if num == 2:
        return True
    if num > 2 and num & 1 == 0:
        return False

    s, t = 0, num-1
    while t & 1 == 0:
        s, t = s+1, t >> 1
    a = random.randint(1, num-1)
    if pow(a, t, num) == 1:
        return True
    for i in range(0, s):
        if pow(a, pow(2, i) * t, num) == num-1:
            return True
    return False

q=3885454702262117633619992283318623173800069752848918463273236826285671702913192528692500215814835208788392462503205261244629164777748703556368394875455672524253158289110397460875095153531143764067267831734225468098792818351352914356125033173267183429565346366225811908196062158094700190584990617017079840843932145108739359214562193636366580979523104478001604899993358153136383377724144733570895561761554399068601845008838864732548224437327119361708362721708239372674403254601596726581297316473179449042346981292259622088083932311041854995550884083819872356017835291954901610130262313105257265793774688961332062173986113088083155626026317575718551429276406935915815616835833281479965204239769610419051941709909274753561530823966067113539346809307828489043772723586620930059072393011239991183590987524625656112404336119094032606874413290098591134848048998094617290485457900819606930211478468091691533311003250422037184905444838707283369174442858945815402303727174235341981145333722463502655954580509910261201175877447429043221102350371693007224586927422640965916791687900671247328298095003114346271691195524046407686404181297651074285043

for i in range(0,20):
  print Miller_Rabin_test(q)

結果は

False
False
...
False

やっぱり素数じゃなさそうだ。うーん、残念。


ちなみにRSA-129の2つの整数

p = 3490529510847650949147849619903898133417764638493387843990820577
q = 32769132993266709549961988190834461413177642967992942539798288533

で試したところ、結果はもちろんTrueであった。すばらしい。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください