こちらの続き。
秘密鍵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であった。すばらしい。

関連記事

RSAで遊ぼう
RSA-129を解こう！
サマーウォーズのあの暗号を解こう！
サマーウォーズのあの暗号を解こう！（その2）
サマーウォーズのあの暗号を解こう！（その3）
サマーウォーズのあの暗号を解こう！（その4）
サマーウォーズのあの暗号を解こう！（その5）
RSA暗号と中国の剰余定理と冪剰余計算の高速化