Generieren Sie große (512 Bit +) Primzahl Python 3,6

Question

Ich habe versucht, große Primzahlen mit Python für RSA-Verschlüsselung für die letzten eineinhalb Wochen, ohne Glück zu generieren. Der Fermat-Primalitätstest ist im Maßstab von 512 Bit unmöglich, und ich kann meinen Kopf nicht ganz um Miller-Rabin wickeln. (Ich bin 13) Alle Online-Skripte scheinen mit Versionen von Python zu funktionieren, die unter denen liegen, die ich verwende. Was soll ich tun, um massive Primzahlen zu generieren? (Ja, probabilistische Primzahlen sind in Ordnung.)

Answer 1

Hier ist mein Miller-Rabin-prime-Checker:

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 

Wenn Sie eine garantierte prime wollen (kein wahrscheinlich prime), das ist nicht sehr viel schwieriger zu gestalten. Eine Methode wegen Pocklington siehe my blog.