Dimostrando la primalità di forti numeri primi probabili

Utilizzando la versione probabilistica del test di Miller-Rabin, ho generato un elenco di medio-grande (200-300 cifre) numeri primi probabili. Ma probabilmente non è abbastanza buono! Ho bisogno di conoscere questi numeri sono primi. Esiste una libreria - preferibilmente avvolta o wrappable in Python - che implementa uno degli algoritmi di dimostrazione della primalità più efficienti?Dimostrando la primalità di forti numeri primi probabili

In alternativa, qualcuno sa dove posso trovare un chiara, dettagliata, e completa descrizione della ECPP (o un algoritmo simile veloce) che non assume una grande quantità di conoscenze precedenti?

Aggiornamento: ho trovato un Java implementation di un altro test, APRT-CLE, che dimostra in modo conclusivo la primalità. Ha verificato un candidato principale di 291 cifre in meno di 10 minuti su un processore atom. Sperando ancora in qualcosa di più veloce, ma questo sembra un inizio promettente.

fonte

2011-01-20 senderle

Quali descrizioni di ECPP Hai letto che non sono chiare, dettagliate, o completa o assumere troppa conoscenza preventiva? Non abbiamo idea di quale potrebbe essere il tuo standard per "conoscenza pregressa". Per favore fornisci qualche informazione su ciò che hai provato finora. –

Vedo che desidera una libreria Python, ma hai considerato check-out il metodo Java http://download.oracle.com/javase/1.4.2/docs/api/java/math/BigInteger.html#isProbablePrime(int) ? Penso che implementino anche l'algoritmo Miller-Rabin e dalla mia esperienza personale per numeri fino a 500 cifre è abbastanza preciso. –

In realtà, ho già implementato l'algoritmo Miller-Rabin in python, facile e veloce, e sorprendentemente veloce. Ma voglio solo un po 'più di sicurezza. (O infinitamente di più, a seconda di come lo guardi.) – senderle

Come un algoritmo che fornisce un affidabile test di primalità polinomiale, considerano AKS. C'è un older SO article referencing implementazioni e presentazioni dell'algoritmo.

fonte

2011-01-20 20:58:09

Interessante, darò un'occhiata a quello. La mia comprensione è che non è il test più veloce, ma forse è abbastanza veloce per i numeri nella mia gamma di dimensioni. Grazie! – senderle

@senderle: è anche mia comprensione che questo è l'unico test che è completamente affidabile, nel senso che non è un'approssimazione e che non si basa su ipotesi non provate ma ampiamente credute (come l'ipotesi di Riemann). –

@Martin v. Löwis: Non per essere polemico, ma [wikipedia sembra non essere d'accordo] (http://en.wikipedia.org/wiki/AKS_primality_test): "ECPP e APR dimostrano o smentiscono in modo conclusivo che un dato numero è primo, ma non si sa che abbia limiti di tempo polinomiali per tutti gli input. " Tuttavia, wikipedia è stato conosciuto per essere sbagliato. – senderle

ho trovato che la biblioteca e la lingua uso Pari/GP APR-CL per dimostrare primalità, che è in realtà l'algoritmo preferito per i numeri in questo intervallo di grandezza, come si scopre. GP dimostra un candidato primo di 291 cifre in meno di 20 secondi su un processore atomico, che è sufficiente per le mie esigenze, e viene fornito con una libreria c alla quale posso accedere usando i tipi.

import ctypes 

def pari_isprime(self, n): 
    try: pari = ctypes.cdll.LoadLibrary("libpari.so") 
    except OSError: 
     print "pari_isprime: couldn't load libpari!" 
     exit() 
    int(n) 
    pari.pari_init(4000000, 2) 
    ret = bool(pari.isprime(pari.gp_read_str(str(n)))) 
    pari.pari_close() 
    return ret

Potrei anche utilizzare il modulo instant. Ecco una semplice funzione di c che esegue una stringa attraverso parser di Pari e restituisce il risultato come una stringa:

from instant import inline 

runpari_code = """ 
PyObject* runpari(PyObject *args) { 
    pari_init(40000000, 2); 
    char *pari_code; 
    char *outstr; 

    if (!PyArg_Parse(args, "s", &pari_code)) { return NULL; } // instant uses old-style args; for a module, use PyArg_ParseTuple 
    outstr = GENtostr(gp_read_str(pari_code)); 
    pari_close(); 
    return Py_BuildValue("s", outstr); 
} 
""" 
runpari = inline(runpari_code, system_headers=['pari/pari.h'], libraries=['pari'])

È possibile che questo può essere utilizzato anche come base di una vera e propria estensione CPython.

fonte

2011-01-22 22:11:22 senderle

Dimostrando la primalità di forti numeri primi probabili

risposta

Problemi correlati