生成大的（512位+）素數python 3.6

Question

我一直在試圖用過去一週半的時間，沒有運氣的情況下用Python生成大質數來進行RSA加密。費馬原理性測試在512比特的尺度下是不可行的，我無法將我的頭圍繞米勒 - 拉賓。 （我13歲）所有在線腳本似乎都可以在我使用的Python版本下工作。我應該怎麼做才能生成大量素數？ （是的，概率素數都很好。）

Answer 1

這裏是我的米勒 - 拉賓總理檢查：

def isPrime(n, k=5): # miller-rabin 
    from random import randint 
    if n < 2: return False 
    for p in [2,3,5,7,11,13,17,19,23,29]: 
     if n % p == 0: return n == p 
    s, d = 0, n-1 
    while d % 2 == 0: 
     s, d = s+1, d/2 
    for i in range(k): 
     x = pow(randint(2, n-1), d, n) 
     if x == 1 or x == n-1: continue 
     for r in range(1, s): 
      x = (x * x) % n 
      if x == 1: return False 
      if x == n-1: break 
     else: return False 
    return True 

如果你想保證黃金（不是可能的素數），這不是很更難安排。有關Pocklington的方法，請參見my blog。