大きい（512ビット+）素数を生成するPython 3.6

Question

私は、過去1週間半の間、RSA暗号化のためにPythonで大きな素数を生成しようとしていました。フェルマーの素数性テストは512ビットのスケールでは実行不可能であり、私はMiller-Rabinの周りを頭で覆うことはできません。 （私は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を参照してください。