Loading AI tools
Da Wikipédia, a enciclopédia livre
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.