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 = 2^kq, para k inteiro positivo e q impar

2) Se p é primo e a < p é um inteiro positivo, então a² 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 = 2^kq, como k > 0 e q impar.

Se a é qualquer inteiro com intervalo 1 <>

(i) a^q mod p = 1

(ii) Um dos números a^q , a^2q , a^4q,...,a^2k-1q é congruente a -1 mod p, isto é, existe algum número j
para 1 ≤ j ≤ k, tal que :

a^2q 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 : a^q mod p , a^2q mod p , a^4q mod p,...,a^2kqmod p, a^2k-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 a^q , a^2q , a^4q,...,a^2k-1q, a^2kq é 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;

2¹⁰²³ 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 = 2^kq;

3º passo : Selecione um inteiro a , como 1 <>

4º passo : Calcule a^q mod n;

5º passo : Se a^q 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 a^2jq mod n

7º passo : Construa a seqüência (a^q mod n , a^2q mod n, a^4q mod n,...,a^2k-1q mod n)

8º passo : Se algum termo na seqüência é n -1, isto é, existe j tal que, a^2jq 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^-6, isto é, a chance é 1 em um milhão.