🏇🏾 🙍🏾 🧤 Algoritmos de pesquisa de números primos ◾️ 👋🏼 🧔🏼

“O maior número primo é 2 ^32582657 -1 . E afirmo com orgulho que me lembrei de todos os seus números ... em forma binária ".
Karl Pomerance

Um número natural é chamado primo se tiver apenas dois divisores diferentes: um e ele próprio. A tarefa de encontrar números primos assombra os matemáticos há muito tempo. Por um longo tempo, esse problema não teve aplicação prática direta, mas tudo mudou com o advento da criptografia de chave pública. Este artigo discute várias maneiras de procurar números primos, tanto de interesse puramente acadêmico quanto usados atualmente em criptografia.

Peneira de Eratóstenes

Peneira de Eratóstenes - um algoritmo proposto pelo matemático grego antigo Eratóstenes. Este método permite encontrar todos os números primos menores que um número n . A essência do método é a seguinte. Pegue um conjunto de números de 2 a n . Riscar todos os números divisíveis por 2, exceto 2. Do conjunto (eliminamos), passamos para o próximo número “não eliminado” - 3, novamente riscamos tudo o que é divisível por 3. Passamos para o próximo número restante - 5 e assim sucessivamente até chegamos ao n . Depois de executar as etapas acima, apenas os números primos permanecerão na lista original.

O algoritmo pode ser ligeiramente otimizado. Como um dos divisores do número composto n é obrigatório

l e q s l a n t s q r t n

$\ leqslant \ sqrt {n}$ , o algoritmo pode ser parado após a exclusão dos números divisíveis por

s q r t n

$\ sqrt {n}$ .

Ilustração da operação do algoritmo da Wikipedia:

A complexidade do algoritmo é

O (n l o g l o g n)

$O (n \ log \ log n)$ ao mesmo tempo, para armazenar informações sobre quais números foram riscados, é necessário

O (n)

$O (n)$ memória.

Há várias otimizações para reduzir esses indicadores. Um truque chamado fatoração de roda é incluir na lista inicial apenas números coprime com os primeiros números primos (por exemplo, menos de 30). Em teoria, propõe-se levar os primeiros simples até cerca de

s q r t l o g n

$\ sqrt {\ log n}$ . Isso reduz a complexidade do algoritmo em

l o g l o g n

$\ log \ log n$ vezes. Além disso, a chamada segmentação é usada para reduzir o consumo de memória. O conjunto inicial de números é dividido em segmentos de tamanho

l e q s l a n t s q r t n

$\ leqslant \ sqrt {n}$ e para cada segmento, a peneira de Eratóstenes é aplicada separadamente. O consumo de memória é reduzido para

O (s q r t n)

$O (\ sqrt {n})$ .

Peneira Atkin

Um algoritmo melhor para selecionar números compostos foi proposto por Atkin e Bershtein e foi chamado de Peneira de Atkin . Este método é baseado nas três propriedades a seguir dos números primos.

Propriedade 1

Se n for um número positivo que não seja múltiplo do quadrado de um número primo e que

n e q u i v 1 (m o d 4)

$n \ equiv 1 (\ mod 4)$ . Então n é primo se e somente se o número de raízes da equação

4 x^{2} + y^{2} = n

$4x ^ 2 + y ^ 2 = n$ estranho.

Propriedade 2

Se n for um número positivo que não seja múltiplo do quadrado de um número primo e que

n e q u i v 1 (m o d 6)

$n \ equiv 1 (\ mod 6)$ . Então n é primo se e somente se o número de raízes da equação

3 x^{2} + y^{2} = n

$3x ^ 2 + y ^ 2 = n$ estranho.

Propriedade 3

Se n for um número positivo que não seja múltiplo do quadrado de um número primo e que

n e q u i v 11 (m o d 12)

$n \ equiv 11 (\ mod 12)$ . Então n é primo se e somente se o número de raízes da equação

3 x^{2} - y^{2} = n

$3x ^ 2-y ^ 2 = n$ estranho.

As evidências para essas propriedades são fornecidas neste artigo .

No estágio inicial do algoritmo, a peneira de Atkin é uma matriz A do tamanho n preenchida com zeros. Para determinar números primos, todos

x, y < s q r t n

$x, y <\ sqrt n$ . Para cada par é calculado

4 x^{2} + y^{2}

$4x ^ 2 + y ^ 2$ ,

3 x^{2} + y^{2}

$3x ^ 2 + y ^ 2$ ,

3 x^{2} - y^{2}

$3x ^ 2-y ^ 2$ e o valor dos elementos da matriz

A [4 x^{2} + y^{2}]

$A [4x ^ 2 + y ^ 2]$ ,

A [3 x^{2} + y^{2}]

$A [3x ^ 2 + y ^ 2]$ ,

A [3 x^{2} - y^{2}]

$A [3x ^ 2-y ^ 2]$ aumenta em um. No final do algoritmo, os índices de todos os elementos da matriz que possuem valores ímpares são números primos ou quadrados de um número primo. Na última etapa do algoritmo, os quadrados dos números restantes no conjunto são riscados.

Da descrição do algoritmo resulta que a complexidade computacional da peneira de Atkin e o consumo de memória são

O (n)

$O (n)$ . Ao usar a fatoração e segmentação das rodas, a estimativa de complexidade do algoritmo é reduzida para

O (n / l o g l o g n)

$O (n / \ log \ log n)$ e consumo de memória até

O (s q r t n)

$O (\ sqrt {n})$ .

Números de Mersenne e teste de Luke-Lemer

Obviamente, com esses indicadores de complexidade, mesmo a peneira otimizada da Atkin não pode ser usada para procurar primos realmente grandes. Felizmente, existem testes rápidos para verificar se um determinado número é primo. Ao contrário dos algoritmos de peneira, esses testes não são projetados para procurar todos os números primos, eles só conseguem dizer com alguma probabilidade se um determinado número é primo.

Um desses métodos de teste é o teste de Luc-Lemer . Este é um teste determinístico e incondicional da simplicidade. Isso significa que a aprovação no teste garante a simplicidade do número. Infelizmente, o teste é destinado apenas a números de um tipo especial

2^{p} - 1

$2 ^ p-1$ onde p é um número natural. Esses números são chamados de números de Mersenne.

O teste de Luke-Lemer afirma que o número de Mersenne

M_{p} = 2^{p} - 1

$M_p = 2 ^ p-1$ primo se e somente se p for primo e

M_{p}

$M_p$ divide

(p - 1)

$(p-1)$ membro da sequência

S_{k}

$S_k$ definir recursivamente:

S_{1} = 4, S_{k} = S_{k - 1}^{2} - 2

$S_1 = 4, S_k = S_ {k-1} ^ 2-2$ para

k > 1

$k> 1$ .

Para o número

M_{p}

$M_p$ comprimento de p bits, a complexidade computacional do algoritmo é

d i s p l a y s t y l e O (p^{3})

${\ displaystyle O (p ^ {3})}$ .

Devido à simplicidade e ao determinismo do teste, os maiores números primos conhecidos são os números de Mersenne. O maior número primo conhecido de hoje é

2^{82.589.933} - 1

$2 ^ {82.589.933} -1$ , sua notação decimal consiste em 24.862.048 dígitos. Você pode admirar essa beleza aqui .

Teorema de Fermat e teste de Miller-Rabin

Não são conhecidos muitos números primos de Mersenne; portanto, a criptografia de chave pública requer uma maneira diferente de pesquisar números primos. Um desses métodos é o teste de simplicidade de Fermat . É baseado no pequeno teorema de Fermat, que afirma que se n é primo, então para qualquer a que não seja divisível por n , a igualdade

a^{n - 1} e q u i v 1 p m o d n

$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ . A prova do teorema pode ser encontrada na Wikipedia .

O teste de simplicidade de Fermat é um teste probabilístico, que consiste em enumerar vários valores de a se pelo menos um deles satisfizer a desigualdade

a^{n - 1} n o t e q u i v 1 p m o d n

$a ^ {n-1} \ not \ equiv 1 \ pmod n$ , o número n é composto. Caso contrário, n é provavelmente primo. Quanto mais valores de um usado no teste, maior a probabilidade de n ser primo.

Infelizmente, existem números compostos n para os quais a comparação

a^{n - 1} e q u i v 1 p m o d n

$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ vale para todos um primo mutuamente com n . Esses números são chamados de números Carmichael . Os números compostos que passam com êxito no teste de Fermat são chamados Fermat pseudo-simples. O número de Fermat pseudo-simples é infinito; portanto, o teste de Fermat não é a maneira mais confiável de determinar números primos.

Teste de Miller-Rabin

Resultados mais confiáveis podem ser alcançados combinando o pequeno teorema de Fermat e o fato de que para um primo p não há outras raízes da equação

x^{2} e q u i v 1 p m o d p

$x ^ 2 \ equiv 1 \ pmod p$ exceto 1 e -1. O teste de Miller-Rabin enumera vários valores de a e verifica se as seguintes condições são verdadeiras.

Seja p um primo e

p - 1 = 2^{s} d

$p-1 = 2 ^ sd$ , então para qualquer uma de pelo menos uma das condições for verdadeira:

$a ^ {d} \ equiv \ pm1 {\ pmod {p}}$
Existe um número inteiro r <s tal que $a ^ {2 ^ {r} d} \ equiv -1 {\ pmod {p}}$

Pelo teorema de Fermat

a^{p - 1} e q u i v 1 p m o d p

$a ^ {p-1} \ equiv1 \ pmod p$ e desde

p - 1 = 2^{s} d

$p-1 = 2 ^ sd$ da propriedade das raízes da equação

x^{2} e q u i v 1 p m o d p

$x ^ 2 \ equiv 1 \ pmod p$ segue-se que, se acharmos que uma das condições não é satisfeita, então p é um número composto. Se uma das condições for cumprida, o número a é chamado de testemunha da simplicidade do número n, de acordo com Miller, e o número n em si é provavelmente primo.

Quanto mais testemunhas de simplicidade forem encontradas, maior a probabilidade de n ser primo. De acordo com o teorema de Rabin, a probabilidade de um número escolhido aleatoriamente a testemunhar a simplicidade do número composto é aproximadamente

1 / 4

$1/4$ .

Portanto, se verificarmos k números aleatórios a , então a probabilidade de tomar o número composto como primo

a p r o x (1 / 4)^{k}

$\ aprox (1/4) ^ k$ .

A complexidade do algoritmo

O (k l o g^{3} p)

$O (k \ log ^ 3p)$ onde k é o número de verificações.

Devido à sua velocidade e alta precisão, o teste de Miller-Rabin é amplamente utilizado na busca de números primos. Muitas bibliotecas criptográficas modernas usam apenas esse teste para verificar a simplicidade de grandes números e, como Martin Albrecht mostrou em seu trabalho , isso nem sempre é suficiente.

Ele foi capaz de gerar esses números compostos que foram aprovados no teste de simplicidade nas bibliotecas OpenSSL, CryptLib, JavaScript Big Number e muitos outros.

Teste de Luke e Baillie - Teste PSW

Para evitar vulnerabilidades relacionadas a situações em que um número composto gerado por um invasor é apresentado como primo, Martin Albrecht sugere o uso do teste Baillie - PSW . Apesar do teste Baillie - PSW ser probabilístico, até o momento, não foram encontrados números compostos que passem com êxito nesse teste. Por encontrar esse número em 1980, os autores do algoritmo prometeram uma recompensa de US $ 30. O prêmio ainda não foi reivindicado.

Vários pesquisadores verificaram todos os números até

2^{64}

$2 ^ {64}$ e nenhum número composto passou no teste Baillie - PSW. Portanto, para números menos

2^{64}

$2 ^ {64}$ o teste é considerado determinístico.

A essência do teste é verificar consistentemente o número em um tempo de inatividade por dois métodos diferentes. Um desses métodos é o teste de Miller-Rabin já descrito acima. O segundo é o teste de Lucas para uma forte pseudo-simplicidade .

Teste de pseudo-simplicidade de Luke Strong

Sequências de Lucas são pares de sequências de recorrência

\ {U_ {n} (P, Q) \}, \ {V_ {n} (P, Q) \}

$\ {U_ {n} (P, Q) \}, \ {V_ {n} (P, Q) \}$ descrito pelas expressões:

d i s p l a y s t y l e U_{0} (P, Q) = 0, q u a d U_{1} (P, Q) = 1, q u a d U_{n + 2} (P, Q) = P c d o t U_{n + 1} (P, Q) - Q c d o t U_{n} (P, Q), n g e q 0

${\ displaystyle U_ {0} (P, Q) = 0, \ quad U_ {1} (P, Q) = 1, \ quad U_ {n + 2} (P, Q) = P \ cdot U_ {n +1} (P, Q) -Q \ cdot U_ {n} (P, Q), \, n \ geq 0}$

d i s p l a y s t y l e V_{0} (P, Q) = 2, q u a d V_{1} (P, Q) = P, q u a d V_{n + 2} (P, Q) = P c d o t V_{n + 1} (P, Q) - Q c d o t V_{n} (P, Q), n g e q 0

${\ displaystyle V_ {0} (P, Q) = 2, \ quad V_ {1} (P, Q) = P, \ quad V_ {n + 2} (P, Q) = P \ cdot V_ {n +1} (P, Q) -Q \ cdot V_ {n} (P, Q), \, n \ geq 0}$

Vamos

U_{n} (P, Q)

$U_n (P, Q)$ e

V_{n} (P, Q)

$V_n (P, Q)$ São sequências de Lucas, onde os números inteiros P e Q satisfazem a condição

d i s p l a y s t y l e D = P^{2} - 4 Q n e q 0

${\ displaystyle D = P ^ {2} -4Q \ neq 0}$

Calculamos o símbolo de Jacobi :

l e f t (f r a c D p r i g h t) = v a r e p s i l o n

$\ left ({\ frac {D} {p}} \ right) = \ varepsilon$ .

Encontre tais r, s para os quais a igualdade

n - ε = 2^{r} s

$n-ε = 2 ^ rs$

Para prime n , uma das seguintes condições é válida:

n divide $U_s$
n divide $V_ {2 ^ js}$ por algum j <r

Caso contrário, n é composto.

A probabilidade de um número composto n ser aprovado no teste Luc para um determinado par de parâmetros P, Q não excede 4/15. Portanto, após a aplicação do teste k vezes, essa probabilidade é

(4 / 15)^{k}

$(4/15) ^ k$ .

Os testes de Miller-Rabin e Luke produzem conjuntos disjuntos de números pseudo-simples, respectivamente, se o número p passou nos dois testes, é simples. É nessa propriedade que se baseia o teste Baillie - PSW.

Conclusão

Dependendo da tarefa, vários métodos para encontrar números primos podem ser usados. Por exemplo, ao procurar primos grandes de Mersenne, primeiro, usando a peneira de Eratóstenes ou Atkin, uma lista de primos é determinada até um certo limite, suponha que até

10^{8}

$10 ^ 8$ . Em seguida, para cada número p da lista, usando o teste Luc-Lemer, é verificado se há simplicidade

M_{p} = 2^{p} - 1

$M_p = 2 ^ p-1$ .

Para gerar um grande número primo para fins criptográficos, um número aleatório a é selecionado e verificado pelo teste de Miller-Rabin ou pelo Baillie - PSW mais confiável. De acordo com o teorema da distribuição de números primos , para um número selecionado aleatoriamente de 1 a n, a chance de ser primo é aproximadamente igual

f r a c 1 l n n

${\ frac {1} {\ ln n}}$ . Portanto, para encontrar um número primo de 1024 bits, basta classificar cerca de mil opções.

Fontes PS

A implementação de todos os algoritmos descritos no Go pode ser visualizada no GitHub .

Algoritmos de pesquisa de números primos