Teste de primalidade

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.[1] 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).[2] 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.[3]

Um dos primeiros testes de primalidade é o crivo de Eratóstenes.[4]

Referências

  1. ↑ Tereza, Danilo Machado (2017). A matemática dos testes de primalidade (PDF). Juiz de Fora, MG: Universidade Federal de Juiz de Fora. 3 páginas 
  2. ↑ Chagas, Amirton Bezerra (2009). Testes de Primalidade: Uma Visão Computacional (PDF). Recife, PE: Universidade Federal de Pernambuco. 46 páginas 
  3. ↑ «Calculadora online: Teste de primalidade de Miller–Rabin». pt.planetcalc.com. Consultado em 25 de julho de 2022 
  4. ↑ «Crivo de Eratóstenes - O Que é? - Como construir?». Matemática Genial. Consultado em 25 de julho de 2022 
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.