Teste de primalidade de Adleman – Pomerance – Rumely - Adleman–Pomerance–Rumely primality test
Na teoria dos números computacionais , o teste de primalidade de Adleman-Pomerance-Rumely é um algoritmo para determinar se um número é primo . Ao contrário de outros algoritmos mais eficientes para esse fim, evita o uso de números aleatórios, por isso é um teste de primalidade determinístico . Recebeu o nome de seus descobridores, Leonard Adleman , Carl Pomerance e Robert Rumely . O teste envolve aritmética em campos ciclotômicos .
Posteriormente, foi melhorado por Henri Cohen e Hendrik Willem Lenstra , comumente referido como APR-CL . Ele pode testar a primalidade de um número inteiro n no tempo:
Implementações de software
- UBASIC fornece uma implementação sob o nome APRT-CLE (APR Test CL extendido)
- Um miniaplicativo de fatoração que usa APR-CL em certas condições (código-fonte incluído)
- Pari / GP usa APR-CL condicionalmente em sua implementação de isprime ().
- mpz_aprcl é uma implementação de código aberto usando C e GMP.
- O LLR de Jean Penné usa APR-CL em certos tipos de testes principais como uma opção alternativa.
Referências
- Adleman, Leonard M .; Pomerance, Carl ; Rumely, Robert S. (1983). "Sobre a distinção de números primos de números compostos". Annals of Mathematics . 117 (1): 173–206. doi : 10.2307 / 2006975 . JSTOR 2006975 .
- Cohen, Henri ; Lenstra, Hendrik W., Jr. (1984). "Teste de primazia e somas de Jacobi" . Matemática da Computação . 42 (165): 297–330. doi : 10.2307 / 2007581 . JSTOR 2007581 .
- Riesel, Hans (1994). Números Primos e Métodos de Computador para Fatoração . Birkhäuser. pp. 131 –136. ISBN 978-0-8176-3743-9.
- APR e APR-CL
 |
Este artigo relacionado a algoritmos ou estruturas de dados é um esboço . Você pode ajudar a Wikipedia expandindo-a . |
 |
Este artigo relacionado à teoria dos números é um esboço . Você pode ajudar a Wikipedia expandindo-a . |