Ho bisogno di testare la primalità su intervalli tra numeri che sono veramente grandi (nell'intervallo di lungo), quindi ho bisogno di un algoritmo veloce per verificare se un numero è primo o meno. Si prega di suggerire le vostre idee.Algoritmo più veloce per il test di primalità
Mi è venuto in mente un algoritmo veramente buono, che è molto più veloce di controllare tutti i divisori - il che ovviamente mi consente anche di decifrare la crittografia a chiave pubblica.
Aspetta - ho solo bisogno di chiudere la finestra, ci sono tutti questi elicotteri neri in testa ........
(O guardare How can I test for primality?)
Il factoring dei numeri composti (che sarebbe necessario per decifrare RSA) è diverso dal semplice test se un numero è primo (che non richiede necessariamente di trovare fattori specifici). In effetti, l'implementazione di RSA richiede di trovare numeri primi con centinaia di cifre, il che sarebbe irrealizzabile con un semplice algoritmo "controlla tutti i potenziali divisori". – sth
Sì, ma se ci fosse un metodo più veloce per testare i numeri primi, non lo diresti a nessuno qui ;-) La questione era che, comunque, si chiudeva comunque. –
Un buon metodo è il Miller-Rabin test. Va notato tuttavia che questo è solo un test probabilistico.
Miller-Rabin può essere adattato per essere deterministico sotto l'ipotesi dell'ipotesi Generalizzata di Riemann. Dal momento che il GRH è ampiamente creduto vero, potrei immaginare uno scenario in cui stavi usando questo test come se fosse provato deterministico poiché è di gran lunga il più veloce. –
@Mark: e per l'intervallo di input specificato, non è necessario assumere che GRH sia vero, abbiamo solo bisogno di un presupposto più debole che la versione deterministica di M-R non abbia falsi positivi sotto LONGLONG_MAX. Questo è probabilmente più facile da dimostrare, anche se non mi piacerebbe ancora provarlo a farlo con un test completo. –
Il più veloce sarebbe probabilmente cercare in un elenco precompilato di numeri primi. Vedi here for example, hanno fino a 2^43112609-1 (il più grande primo noto).
Questo non funzionerebbe. Nessun computer ha mai avuto abbastanza spazio per contenere una lista così a lungo. L'elenco richiederebbe più di un miliardo di gigabyte di spazio di archiviazione senza compressione, basato su una stima approssimativa per 'pi (2^64)'. –
@Dietrich: Ma OP non ne ha bisogno. – UncleBens
Credo che il test di primalità asintoticamente più veloce (non probabilistico) della corrente sia il "Lens A/Pomerance migliorato AKS", che ha complessità che è essenzialmente O (n^6).
Tuttavia, l'intervallo di long long (presupponendo un sistema tipico in cui si tratta di un intero a 64 bit) non è davvero così grande. In particolare, ci sono solo ~ 200 milioni di numeri primi meno di 2^32, quindi usando un test probabilistico veloce, seguito da una divisione di prova con un elenco precompilato di numeri primi (o semplicemente guardando il numero in una lista di numeri primi, se ne hai uno) sarebbe dannatamente veloce in quella gamma, ed è probabilmente il modo giusto per farlo.
Non è necessario eseguire la divisione di prova dopo il test probabilistico. Se esegui il test del probabilista in iterazioni, la probabilità di una risposta errata è 1/2^n, quindi se n = 100 l'algoritmo sarebbe errato 1 in 10^30 volte. È meglio eseguire il test probabilistico più iterazioni rispetto alla divisione di prova. – theycallhimtom
In particolare, su hardware reale si raggiunge rapidamente il punto in cui la probabilità di fallimento del test probabilistico non è peggiore della possibilità di fallimento di un test deterministico a causa di valori di registro capovolti da raggi cosmici insolitamente energetici (o altri guasti hardware sporadici). –
Suggerisco lo GNU MP library che utilizza l'algoritmo Miller-Rabin. L'ho usato per alcuni mesi ed è molto veloce.
In particolare, la funzione mpz_probab_prime_p esegue questa operazione, è inoltre possibile utilizzare un'altra funzione mpz_nextprime per trovare il numero primo successivo maggiore di un numero. Posso pubblicare campioni di codice se lo desideri.
Cobbal e grokus hanno ragione. Il test Miller-Rabin è il più utile degli algoritmi disponibili. Sì, è probabilistico, ma in realtà non dovrebbe spaventarti. Il test è il più usato per scopi pratici.
Si noti che la probabilità di falsi positivi (non ci sono falsi negativi) può essere resa arbitrariamente piccola ripetendo il test.
Date un'occhiata alla mia risposta qui:
how to test a prime number 1000 digits long?
Il test è molto veloce. Se lavori in un intervallo di 64 bit o inferiore, puoi inserire un GCD con 30030 per risparmiare un po 'di tempo per la maggior parte dei numeri.
Se si desidera testare una primalità a lungo lungo, lo Baillie PSW primality test è una buona scelta. Questo test fa un test pseudoprimo forte e un test Lucas e quindi è molto veloce. Si prevede che esistano alcuni materiali compositi che superano questo test, ma finora nessuno è noto e non vi è certamente alcuna eccezione inferiore a 10 . Una variante di questo test è ad esempio utilizzata in Mathematica.
Il miglior algoritmo migliore del mio punto di vista è "ALI primality test".
Un test Miller-Rabin per le sette basi 2, 325, 9375, 28178, 450775, 9780504, 1795265022 è stato provato da Jim Sinclair per determinare in modo deterministico se un numero inferiore a 2^64 è primo. Vedi http://miller-rabin.appspot.com/.
Hai solo bisogno di verificare se è primo, o hai bisogno di trovare i suoi fattori primi? –
La fattorizzazione primaria è difficile. Questo è ciò su cui si basa la crittografia RSA. Anche se non hai risposto alla domanda di Stephen, presumo che tu voglia solo testare un numero per la primalità. – ldog
Dupe di http://stackoverflow.com/questions/627463/how-can-i-test-for-primality –