Algoritmo mais rápido para teste de primalidade

Eu preciso testar primality em intervalos entre números que são realmente grandes (no intervalo de longo tempo), então eu preciso de algum algoritmo rápido para verificar se um número é primo ou não. Por favor, sugira suas ideias.

Um bom método é o teste de Miller-Rabin . Deve-se notar, no entanto, que este é apenas um teste probabilístico.

Um teste de Miller-Rabin para as sete bases 2, 325, 9375, 28178, 450775, 9780504, 1795265022 foi provado por Jim Sinclair para testar deterministicamente se um número inferior a 2 ^ 64 é primo. Veja http://miller-rabin.appspot.com/ .

Acredito que o teste de primalidade assintoticamente mais rápido (não probabilístico) é o “Lenstra / Pomerance improved AKS”, que tem complexidade que é essencialmente O (n ^ 6).

No entanto, o intervalo de long long (assumindo um sistema típico em que é um inteiro de 64 bits) não é tão grande assim. Em particular, existem apenas ~ 200 milhões de primos menores que 2 ^ 32, então usando um teste probabilístico rápido, seguido por divisão de avaliação com uma lista pré-calculada de primos (ou apenas procurando o número em uma lista de primos, se você tiver um ) seria muito rápido nesse intervalo, e é provavelmente o caminho certo para fazê-lo.

Eu criei um algoritmo muito bom, que é muito mais rápido do que verificar todos os divisores – o que, é claro, também me permite quebrar a criptografia da chave pública.

Espere – eu só preciso fechar a janela, tem todos esses helicópteros pretos no alto ……..

(Ou olhe para Como posso testar a primalidade? )

Eu sugeriria a biblioteca GNU MP que usa o algoritmo de Miller-Rabin . Eu usei por alguns meses e é muito rápido.

Especificamente, a function mpz_probab_prime_p faz isso, você também pode usar outra function mpz_nextprime para encontrar o próximo número primo maior que um número. Eu posso postar amostras de código, se você quiser.

Se você quiser testar um longo tempo para primality, então o teste de primalidade Baillie PSW é uma boa escolha. Este teste faz um forte teste de pseudoprimo e um teste de Lucas e, portanto, é muito rápido. Espera-se que existam alguns compostos que passam neste teste, mas até agora nenhum é conhecido, e certamente não há exceção abaixo de 10 15 . Uma variante desse teste é usada, por exemplo, no Mathematica.

Cobbal e grokus estão certos. O teste de Miller-Rabin é o mais útil dos algoritmos disponíveis. Sim, é probabilístico, mas realmente não deveria assustá-lo. O teste é o mais amplamente utilizado para fins práticos.

Note que a probabilidade de falsos positivos (não há falsos negativos) pode ser arbitrariamente pequena repetindo o teste.

Dê uma olhada na minha resposta aqui:

como testar um número primo de 1000 dígitos?

O teste é muito rápido. Se você estiver trabalhando no intervalo de 64 bits ou menor, é possível adicionar um GCD com 30030 para economizar um pouco de tempo para a maioria dos números.

O melhor algoritmo da minha opinião é o “teste de primalidade ALI”.

O mais rápido provavelmente seria procurá-lo em uma lista pré-computada de primos. Veja aqui por exemplo , eles têm até 2 ^ 43112609-1 (maior prime conhecido).