Criptografia : números primos
Os conceitos envolvendo números primos,são peças importantes no projeto dos algoritmos criptográficos.Estes números são inteiros p maior do que 1, que tem como seus únicos divisores ±1 e ±p. O conjunto {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,71,73,79,83,89,97} são os primos
até 100. A cada intervalo de 100 números até 2000, encontramos em média 12 primos.
Em processos criptográficos é necessário a presença de números primos de valor elevado, e não dispomos de uma fórmula matemática para obte-los. Em função deste fato, é necessário então, após obter um número primo aleatório com muitos dígitos,determinar, se este número é de fato primo.
Um teste muito usado é o método desenvolvido por RABIN-MILLE. Este método pode ser descrito por um algoritmo, o qual esta embasado nos seguintes resultados da teoria dos números :
1) Dado n inteiro positivo impar maior ou igual a 3, então : n - 1 = 2kq, para k inteiro positivo e q impar
2) Se p é primo e a < p é um inteiro positivo, então a2 mod p = 1, se e só se a mod p = 1 ou
a mod p= -1 mod p = p - 1.
3) Considere p > 2 um número primo, temos : p - 1 = 2kq, como k > 0 e q impar.
Se a é qualquer inteiro com intervalo 1 <>
(i) aq mod p = 1
(ii) Um dos números aq , a2q , a4q,...,a2k-1q é congruente a -1 mod p, isto é, existe algum número j
para 1 ≤ j ≤ k, tal que :
a2q mod p = -1 mod p = p - 1
As demonstrações destes resultados passam pelas propriedades da aritmética modular e o teorema de Fermat. Na demonstração deste último resultado que é feita de forma construtiva, permite afirmar que :
Na seqüência : aq mod p , a2q mod p , a4q mod p,...,a2kqmod p, a2k-1q mod p ,uma das seguintes afirmação é verdadeira:
(i) O primeiro número na lista, e conseqüentemente todos os números subseqüentes na lista é igual a 1;
(ii) Algum elemento na seqüência não é igual a 1, mas seu quadrado mod p é igual a 1.
Combinando a propriedade 2), temos que o único número que satisfaz essa condição é p - 1. Assim, nestas condições, a seqüência contém um elemento igual a p - 1.
Resumindo, temos :
Se n é primo, então os primeiros elemento da seqüência aq , a2q , a4q,...,a2k-1q, a2kq é igual a 1, ou algum elemento na seqüência é igual a n -1 . Caso contrário, n é composto, isto é não é primo.
Por outro lado, se a condição for atendida, não necessariamente n é primo( a condição não é suficiente). De fato, escolhendo n = 23 x 89 = 2047, temos :
n -1 = 2 x 1023;
21023 mod 2047 =1,
de forma que, este número satisfaz a condição, mas não é primo.
Vamos, então escrever um algoritmo para decidir se um número inteiro impar n é composto ou com grande possibilidades de ser primo.
O Algoritmo :
1º passo : Entre com o número n impar;
2º passo : Encontre inteiro k e q impar, tal que: p - 1 = 2kq;
3º passo : Selecione um inteiro a , como 1 <>
4º passo : Calcule aq mod n;
5º passo : Se aq mod n = 1, escreva como possibilidade e encerre. Caso contrário vá para o próximo passo;
6º passo : Para j = 0; 1; 2; ...; k-1. Calcule a2jq mod n
7º passo : Construa a seqüência (aq mod n , a2q mod n, a4q mod n,...,a2k-1q mod n)
8º passo : Se algum termo na seqüência é n -1, isto é, existe j tal que, a2jq mod n = n-1 escreva como possibilidade e encerre. Caso contrário escreva composto e encerre.
Em resumo, o algoritmo, entra com um inteiro impar n e retorna( como saída) o resultado composto, se n não for primo, e com possibilidade se n tem chance de ser primo.
A pergunta natural é, se a saída é com possibilidade e assumirmos que n é primo, como que grau de confiança fazemos esta suposição ?
A resposta :
A literatura mostra que, dado n impar não primo e um inteiro a escolhido aleatoriamente, como 1 <>, ou seja, que deixe de detectar que não é primo é menor do que 1/4. Assim, para t valores diferentes de a forem escolhidos a probabilidade de que, todos passam pelo algoritmo com a mensagem com possibilidade é menor que (1/4)t (independentes). Logo, para um valor suficientemente grande de t, podemos confiar que n é primo se o algoritmo retornar com possibilidade.
Como comentário final, se tomarmos t = 10, a probabilidade de não detectar que não é primo, é menor que (1/4)10 > 10-6, isto é, a chance é 1 em um milhão.
