Saudação aos cidadãos de Habrovsk! Hoje continuamos a compartilhar material útil, cuja tradução foi preparada especificamente para os alunos do curso "Algoritmos para desenvolvedores" .
Dado algum número
n , como entender que esse número é primo? Suponha que
n inicialmente estranho, porque, caso contrário, a tarefa é bastante simples.
A idéia mais óbvia seria procurar todos os divisores de
n ; no entanto, até agora o principal problema é encontrar um algoritmo eficiente.
Teste de Fazenda
Pelo
Teorema de Fermat , se
n é primo, então para qualquer um a seguinte igualdade é válida:
a n−1 =1 (mod n) . A partir daqui, podemos derivar a regra do teste de Fermat para verificar a simplicidade de um número: pegue um
a ∈ {1, ..., n−1} aleatório e verifique se a igualdade
a n−1 =1 (mod n) é válida. Se a igualdade não for respeitada, o mais provável é que
n seja composto.
No entanto, a condição de igualdade pode ser atendida mesmo que
n não seja simples. Por exemplo, considere
n = 561 = 3 × 11 × 17 . De acordo com o
teorema chinês
restante :
Z 561 = Z 3 × Z 11 × Z 17, em que cada um ∈ Z
∗ 561 corresponde ao seguinte:
(x,y,z) ∈ Z ∗ 3 ×Z ∗ 11 11×Z ∗ 17 .Pelo teorema de Fermat,
x 2 =1 ,
y 10 =1 z 16 =1 . Como 2, 10 e 16 são todos 560 divisores, isso significa que
(x,y,z) 560 = (1, 1, 1) , em outras palavras,
a 560 = 1 para qualquer
a ∈ Z ∗ 561 .
Não importa qual a que escolhemos, o 561 sempre passará no teste de Fermat, apesar de ser composto, desde que a seja coprime com
n . Esses números são chamados de números Carmichael e verifica-se que há um número infinito deles.
Se
a não
a coprime com
n , ele não passa no teste de Fermat, mas, neste caso, podemos recusar os testes e continuar procurando os divisores de
n , calculando o MDC (
a, n ).
Teste de Miller-Rabin
Podemos melhorar o teste dizendo que
n é primo se e somente se as soluções
x 2 = 1 (mod n) forem x = ±1 .
Assim, se n passa no teste de Fermat, ou seja,
a n−1 = 1 , também verificamos que
a (n−1)/2 = ±1 ,
a (n−1)/2 vez que
a (n−1)/2 é a raiz quadrada de 1.
Infelizmente, números como, por exemplo, 1729 - o terceiro número de Carmichael ainda podem enganar esse teste aprimorado. E se iterarmos? Ou seja, embora seja possível, reduziremos o expoente pela metade, até atingirmos um número diferente de 1. Se, no final, chegarmos a algo diferente de -1,
n será composto.
Mais formalmente, seja 2
S a maior potência de 2, divisível por n-1, ou seja,
n−1=2 S q para algum número ímpar
q . Cada número da sequência
a n−1 = a (2^S)q ,
a (2^S-1)q , ...,
aq .
Essa é a raiz quadrada do membro anterior da sequência.
Então, se
n é um número primo, a sequência deve começar com 1 e cada número subsequente também deve ser 1, ou o primeiro membro da sequência pode não ser igual a 1, mas é -1.
O teste de Miller-Rabin leva a a
a∈ Z n aleatória. Se a sequência acima não começar com 1 ou se o primeiro membro da sequência não for 1 ou -1, então
n não é simples.
Acontece que, para qualquer
n composto, incluindo números de Carmichael, a probabilidade de aprovação no teste de Miller-Rabin é de aproximadamente 1/4. (Em média, muito menos.) Assim, a probabilidade de que
n passará em várias execuções de teste diminui exponencialmente.
Se
n não passar no teste de Miller-Rabin com uma sequência iniciada por 1, teremos uma raiz quadrada não trivial de 1 módulo
n e poderemos
encontrar eficientemente os divisores de n . Portanto, os números de Carmichael são sempre convenientes para fatorar.
Quando o teste é aplicado a números da forma
pq , onde
p e
q são números primos grandes, eles não passam no teste de Miller-Rabin em quase todos os casos, já que a sequência não começa com 1. Portanto, não poderemos quebrar o RSA.
Na prática, o teste de Miller-Rabin é implementado da seguinte forma:
- Dado
n , precisamos encontrar s tais que n – 1 = 2 S q para alguns q ímpares. - Faça um aleatório
a ∈ {1,...,n−1} - Se a q = 1,
n passa no teste e paramos a execução. - Para
i= 0, ... , s−1 verifique a igualdade a (2^i)q = −1 . Se a igualdade for válida, n passa no teste (interrompe a execução). - Se nenhuma das condições acima for atendida,
n será composto.
Antes de realizar o teste de Miller-Rabin, vale a pena realizar mais algumas divisões triviais em pequenos números primos.
Estritamente falando, esses testes são testes para determinar se um número é considerado composto, pois não provam que o número que está sendo verificado é primo, mas eles definitivamente provam que ele pode ser composto.
Ainda existem algoritmos determinísticos trabalhando em tempo polinomial para determinar a simplicidade (Agrawal, Kayal e
Saxena ), mas hoje eles são considerados impraticáveis.