Números primos e algoritmos – Parte II

Nesta segunda parte vamos mostrar testes que rapidamente dizem se um numero é provavelmente primo, provavelmente porque como veremos abaixo eles checam rapidamente se não é primo, mas quando dizem que é primo … Aí tem alta probabilidade de ser primo e se você quiser ter certeza precisa usar um algoritmo mais lento.

Este que vou mostrar se baseia no Pequeno Teorema de Fermat. Este teorema é bem simples de enunciar:

Se um número p é primo então para todos os números a entre 1 e p-1 a equação abaixo tem que ser respeitada (em notação C++):

pow (a,p-1) % p = 1

Assim fazemos o teste para alguns números a entre 1 e p-1 e caso a equação seja verdadeira para eles podemos dizer que é provavelmente primo. Se falhar para algum número não é primo com certeza.

#define NUMTESTES 10 // vamos testar 10 vezes, pode ser um número maior ...
 
int isPrimo (int n) {
   if (n==1)
       return 0; // dica de um leitor da semana passada
   if (n<4)
       return 1;
   for (int i=0; i<NUMTESTES; i++) {
       if (i+1 > n-1)
            break;
       // aqui estou supondo que há uma biblioteca 
       // de precisão arbitrária como a mathX
       // ou usando uma técnica de obter modulo 
       // em exponenciação como a 
       // Fast Modular Exponentiation
       if (pow(i+1,n-1)%p != 1)  
            return 0;
   }
   return 1;
}

Caso o resultado seja 0 você pode estar certo de que não é primo, se for 1, você pode ter uma enorme probabilidade de ser primo.

Para algumas aplicações é preciso ter certeza que o número é primo e como existem os números de Carmichael que se comportam como primos nestes testes probabilísticos vamos ver na próxima parte como testar rapidamente e com certeza (já adianto que é bem complicado do ponto de vista matemático…)

Pierre Fermat ajuda você a encontrar números primos

Como sempre, se houver erros favor apontar nos comentários.

Comments on this entry are closed.