Teste de primalidade

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto.
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

Um teste de primalidade é um algoritmo para determinar se um dado número inteiro é primo. Este tipo de teste é usado em áreas da matemática como a criptografia. Diferentemente da fatoração de inteiros, os testes de primalidade geralmente não fornecem os fatores primos, indicando apenas se o número fornecido é ou não primo. O problema da fatoração é computacionalmente difícil, enquanto que os testes de primalidade são comparativamente mais fáceis (o tempo de execução é polinomial no tamanho dos dados de entrada). Alguns testes de primalidade provam que um número é primo, enquanto que outros, como o teste de Miller-Rabin provam que um número é composto.

Um dos primeiros testes de primalidade é o crivo de Eratóstenes. Existem outros métodos, como o teste de primalidade AKS, capaz de provar se um número é primo em tempo polinomial.

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.