Algoritmos de primalidade

Algoritmos de Primalidade

Divisão por Tentativa:

É o método mais trivial para determinar se um número é primo ou não. É possível realizálo com complexidade O(). Isso torna inviável usálo com números muito grandes, porém sua simplicidade o torne uma boa opção para testar a primalidade de números relativamente pequenos.

Teste de Miller-Rabin: O alforitmo consiste em, dado um inteiro ímpar n a ser testado, primeiramente escreve-se n-1 na forma de .d, sendo s um inteiro qualquer e d um inteiro ímpar. Por exemplo, para n = 345, n – 1 seria escrito como = 344.Com esses dois valores s e d, esconde-se um inteiro a < n aleatoriamente. Executam-se então os testes:

e para i variando de 0 a s -1

Caso algum dos testes seja verdadeiro, n é considerado pseudoprimo. Caso os 2 testes falharem n é com certeza composto. Usando Transformada Rápida de Fourier para realizar as multiplicações, seu custo é de O(k.log²n).

Teste de Baillie-PSW (B-PSW) Este teste, proposto por Baillie e melhorado por Pomerance, é simplesmente a execução dois testes probabilísticos de primalidade em sequência. Primeiramente, é usado um teste de primalidade probabilístico forte. O teste usado na proposta é o teste de Miller-Rabin, com a base a = 2. Caso o número sendo testado passe neste teste, é realizado um teste forte de Lucas, que em resumo, utiliza o Símbolo de Jacobi e Sequências de Lucas para verificar a primalidade de um dado número. Se o número n passar para este teste também, declara-se que n é provável primo. Nunca foi encontrado um contra-exemplo desse teste até agora.

Elliptic Curve Primality Proving (ECPP) O teste ECPP, como o próprio nome já diz, utiliza Curvas Elípticas para efetuar o teste de primalidade. Em 1985, Lenstra iniciou o uso destas estruturas para o problema da fatoração. Em
1986, Goldwasser e Killian publicaram um teste de primalidade baseado em Curvas Elípticas, cuja prova é dependente da conjectura de Cramer e da Hipótese