Geração Prime

Na continuação do tópico iniciado nesta série de artigos , hoje falaremos sobre a geração de números primos. A geração é probabilística e é garantida. Portanto, nosso caso tem uma garantia que permite que você use os números obtidos em aplicativos relacionados à criptografia, o que garante, por exemplo, a segurança de gerenciar seu dinheiro por meio de aplicativos bancários. Além disso, você verá como é garantido o recebimento de números primos de tamanho suficiente para criptografia, bem como quais podem ser os problemas se você negligenciar as garantias.


O esquema geral de segurança para troca de dados é baseado na complexidade de fatorar um grande número composto. Além disso, se houver muitos fatores, eles serão pequenos, e isso simplifica bastante o hacking do sistema de segurança. Portanto, um grande número composto é obtido multiplicando dois números primos de um determinado tamanho. Mas aqui um problema é óbvio - como escolher um número primo suficientemente grande?

Primeiro, determine o tamanho. Na criptografia moderna, a ordem do número composto é determinada pela fórmula $$$2 ^ {2048}$ , ou seja, a ordem real é 2048 em notação binária. E os divisores deste número composto são da ordem de 1024, ou seja, em algum lugar ao redor dos valores $$$2 ^ {1024}$ . Por que 1024? Como há dez anos um fator da ordem de 768 foi fatorado, e hoje é muito provável que os números compostos da ordem de 1024 sejam decompostos.Então foi decidido pela confiabilidade duplicar a ordem de uma só vez, ou seja, para 2048. Bem, é fácil determinar a partir dessa ordem ordem dos fatores necessários.

Mas o que acontece se a ordem dos fatores for muito menor que 1024? Então, em um tempo aceitável, você pode decompor um número composto, mesmo que seja da ordem de 2048. Isso significa que é necessário garantir que os fatores escolhidos por nós tenham uma ordem próxima a 1024 e sejam simples, ou seja, eles não são fatorados. Mas aqui a própria escolha é realizada de acordo com um esquema probabilístico, e isso apenas leva a problemas em potencial.

A probabilidade da simplicidade de um número é verificada com base na suposição de que o número é "mais provável" primo se o seu período (que é descrito aqui ) for um divisor do próprio número, menos um ( $$$N-1$ ) Na forma de uma fórmula, fica assim:

$$

$$a ^ p \ pmod N = 1$$

$$

$$N-1 \ pmod p = 0$$

Aqui $$$N$ - número investigado, $$$a$ - valor de $$$2$ antes $$$N-2$ (determina a base do sistema numérico em que o período é calculado), $$$p$ - período do número investigado. Operação $$$mod$ aqui significa pegar o restante da divisão do primeiro operando pelo segundo.

As verificações existentes se baseiam nessa abordagem, pois para grandes números a determinação incondicional da simplicidade por testes conhecidos leva muito tempo. Mas o menos dessa verificação é óbvio - às vezes você pode obter um número composto, em vez de um número simples. Além disso, ninguém sabe quais divisores farão parte desse número. Mais precisamente, um invasor poderá descobrir aplicando os métodos de fatoração conhecidos, que começam a funcionar em um tempo aceitável se os fatores estiverem na ordem de menos de algumas centenas de bits.

Com que frequência o erro probabilístico de simplicidade? Raramente o suficiente. Há um erro para várias dezenas de milhares de simples, e às vezes dois, mas nada nos garante de três. Além disso, muito depende do teste usado. Portanto, por exemplo, na biblioteca de linguagem Java padrão da classe BigInteger, é implementada uma verificação que permite uma falha de 2 a 3 vezes por mil simples. Ou seja, você não deve pensar que, se teoricamente houver muito poucos erros, na prática tudo estará no chocolate.

Como isso é perigoso? Parece não ser tão assustador quanto alguns podem dizer, porque bem, se um site que fecha a navegação em suas páginas com o protocolo https recebe uma chave facilmente calculada, qual será o problema? Bem, os hackers descobrirão quais notícias você lê neste site e qual é o objetivo? Mas, na verdade, a criptografia não é feita apenas quando se navega na web. Uma situação mais desagradável acontecerá se os hackers descobrirem a chave do seu serviço bancário favorito para gerenciar remotamente o seu dinheiro. Embora, novamente, pareça que, para certamente abrir a troca com o banco (e se o banco usar uma verificação de simplicidade fraca), o hacker terá que esperar cerca de 500 anos até que a probabilidade de emitir uma chave facilmente calculada seja finalmente percebida, porque as chaves geralmente têm um período de validade de 1 ano e portanto, para garantir a invasão, é necessário aguardar até que 500 edições de uma nova chave sejam executadas. Parece que tudo é lógico, mas existe outro "mas" - existem muito mais bancos do que 500 no mundo. Portanto, agora, talvez no seu banco favorito, os hackers podem obter acesso ao seu próprio dinheiro.

Você está com medo? Certamente que não, porque somos todos muito corajosos, até que o pau assado bica. Mas ainda há algo a temer. Embora a probabilidade de um ataque bem-sucedido por hackers precisamente no seu banco não seja tão alta, mas, mesmo assim, se for realizada, seu dinheiro provavelmente não será encontrado. Porque É muito simples - a primeira suposição padrão do serviço de segurança do banco é que alguém com os direitos de acesso apropriados é o culpado. Não é um hacker, a probabilidade de interferência que eles também consideram mínima, ou seja, alguém que é seu. Portanto, um hacker pode ficar impune.

Como corrigir este problema? Você precisa aprender como obter números primos garantidos. Mas como garantir sua simplicidade? Existem quatro métodos para isso.

O primeiro método é eliminado com um mínimo de restrições. Esta é geralmente uma variante da peneira melhorada de Eratóstenes. O método é confiável e garantido, mas limitado a pedidos muito modestos (menos de cem). Portanto, este método não é aplicável em criptografia.

O segundo método é a enumeração com restrições mais fortes. Portanto, se o período de um número for igual ao número em si, menos um, o número será garantido como primo. A fórmula aqui é - $$$N-1 = p$ . Mas, para determinar a igualdade do período da diferença entre o número e a unidade, são usados ​​métodos muito pesados ​​que não funcionam para todas as classes de números. Portanto, seu uso em criptografia baseia-se no número limitado de números de classes específicas ou durante a verificação, se aumentarmos o tamanho do número. Além disso, mesmo números de uma determinada classe por si só não garantem nada, o que significa a necessidade de classificar muitos números de candidatos. Aqui, por exemplo, os números de Mersenne, para os quais há um teste incondicional de simplicidade, já foram resolvidos e descobriram que eles estão praticamente ausentes no intervalo usado na criptografia. Aqui está a lista inteira com pedidos próximos - 1279, 2203, 2281, 3217. Como você pode ver, de 1024 a 2048, há apenas um número adequado. Mas mesmo se levarmos o resto, o número deles indica muito claramente - não vale a pena! Então, novamente, estávamos sem sorte com o método de verificação.

O terceiro método é probabilístico. É o que é usado hoje, inclusive no seu banco favorito. Como ele trabalha? Muito simples - o restante da divisão de um número arbitrário em uma potência é verificado $$$N-1$ em $$$N$ se o restante for um, é provável que o número seja primo. E aqui a palavra "provavelmente" é a mais desagradável aqui. Embora os métodos probabilísticos para verificar a simplicidade também contenham aprimoramentos adicionais, no entanto, como mostrado acima, a biblioteca Java padrão é frequentemente confundida.

E, finalmente, o quarto método. Ele não funciona tão rápido quanto os testes probabilísticos (embora algo possa ser otimizado aqui também), mas fornece números primos garantidos, e mesmo com um período facilmente definível. Qual é o período ideal, você pergunta? Por exemplo, para gerar uma sequência pseudo-aleatória ou de criptografia. Mais precisamente, conhecendo o período, sabemos exatamente quantos números haverá na sequência, o que facilita o planejamento de quanto tempo podemos usar o gerador de sequência com base nesse número. É verdade que isso já se aplica à criptografia simétrica, mas também pode ser útil em vários casos. A seguir, consideraremos uma teoria que garante a simplicidade de verificar os números dos candidatos.

Enquadramento teórico

Para entender como gerar números primos garantidos, você precisa mergulhar em um pouco de matemática. Mas não se assuste, a matemática está aqui no nível da quinta série.

Para garantir a integridade, é recomendável procurar aqui detalhes sobre o que são um período e uma série de resíduos. Bem, diga brevemente que vários resíduos são formados dividindo o “canto” (um método conhecido por qualquer aluno) da unidade pelo número escolhido para o estudo. Ao mesmo tempo, a cada etapa, aparece uma diferença entre o número mais alto, com um zero adicionado a ele e o produto do número sob investigação por um valor de 0 a 9 (para o sistema de números decimais) - esse é o restante. Mas existem muitas etapas na divisão pelo “canto”, portanto, também existem muitos resíduos, e juntos eles formam uma série de resíduos nos quais o mesmo conjunto de números é repetido periodicamente um número infinito de vezes. Um sinal do início de um novo ciclo é o restante igual a um. A quantidade de resíduo entre unidades é a duração do período (ou ciclo). Isso, de fato, é tudo, mas também vale a pena entender que esse método de construção de uma série de saldos pode ser aplicado usando qualquer sistema numérico e, em particular, o sistema com base 2 (em vez de 10, como é habitual na escola) será usado com mais frequência. Ao usar outros sistemas numéricos, todas as regras são preservadas, mas o número de variantes do produto em cada etapa será diferente, igual a b (da base), ou seja, a base do sistema numérico.

Portanto, pelo mostrado anteriormente, sabemos que os números compostos sempre fornecem períodos relativamente curtos que não incluem um número de valores "proibidos". Conhecendo a fatoração de um número composto, é fácil calcular quantos valores devem estar ausentes em um número de resíduos que formam o período de um determinado número. Uma série de resíduos não conterá fatores e todos os números que são múltiplos desses fatores se a própria série for construída com base em um sistema numérico que não seja múltiplo de nenhum dos divisores (ou seja, a base não será dividida por divisores do número). Por exemplo, se houver apenas dois fatores, o número de resíduos múltiplos é determinado pela fórmula $$$m = a + b-2$ onde $$$m$ - o número de resíduos múltiplos, $$$a$ e $$$b$ Os fatores estão formando nosso número composto. Conhecendo o número de resíduos "proibidos", é fácil calcular que uma série de resíduos com mais da metade do valor $$$N-1$ terá um comprimento igual a $$$L = N-1- (a + b-2) = N-a-b + 1$ . Ou seja, essa série estará em $$$a + b-2$ menor do que a série que resultaria se o número fornecido fosse primo. Isso explica por que todos os números com um período igual ao período completo (ou seja, $$$N-1$ ), acabou sendo simples - se pelo menos um elemento ("proibido") fosse excluído da sequência de resíduos, o período seria menos $$$N-1$ . Como resultado da existência de tal regularidade, observamos a operacionalidade de todos esses testes de probabilidade, que hoje verificam a simplicidade de um número. Esses testes calculam valores em uma série de saldos por posição. $$$N-1$ ou $$$(N-1) / 2$ e se os valores forem iguais $$$1$ ou $$$N-1$ , é altamente provável que o número seja primo. Por que apenas com alta probabilidade e não garantida? Como os testes probabilísticos de período não são calculados, mas entre posições $$$N-1$ e $$$(N-1) / 2$ pode haver mais unidades, o que significa a desigualdade do período em relação ao valor $$$N-1$ mas se o período não for igual $$$N-1$ , o número pode ser composto. Além disso, a falta de igualdade em si mesma não é crítica, outra coisa é importante - números pseudo-simples podem fornecer esse arranjo de unidades. Entre os números verificados por esse teste, você pode encontrar números pseudo-simples que são compostos e que ajudam hackers que roubam seu dinheiro. Afinal, quais são os divisores de tais números compostos? Eles podem ser pequenos o suficiente para que um invasor abra facilmente uma troca de dados criptografados.

Agora lembre-se por que os números pseudo-primos podem aparecer. Esses números têm períodos curtos que se repetem várias vezes durante todo o período. $$$N-1$ portanto, às vezes eles podem “se encaixar” e se encaixam várias vezes em um período inteiro. Portanto, por exemplo, o número 25 tem um período de 4 para o sistema numérico com base 7. $$$N-1$ para 25 é 24, tente dividir: 24/4 = 6. Ou seja, esse período é apresentado um número inteiro de vezes em um período completo. Esse fato pode ser verificado pela fórmula acima para reduzir o período, mas levando em consideração o fato de que aeb são iguais nesse caso. O período máximo possível será 24-4 = 20, aqui 24 é o número total de resíduos, 4 é o número de resíduos que são múltiplos de 5. Mas o período nem sempre é o máximo e todas as outras opções podem ser obtidas dividindo o período máximo completamente. 20 é dividido por 2,4,5,10, e apenas dividindo 20 por um número da lista acima, obtemos um período de 4 de comprimento, o que nos dá no final de todo o período $$$N-1$ unidade. E ao verificar a simplicidade, apenas os valores na posição são verificados $$$N-1$ , ou seja, o último valor em todo o período. E para 25 é igual a 1, que é um sinal da simplicidade do número. Embora, de fato, seja um sinal claro de simplicidade, é para todas as bases de sistemas numéricos que menos $$$N$ , o último valor no período completo é igual a um. Mas não há como verificar se há números grandes em todos os sistemas de números; portanto, números pseudo-simples aparecem às vezes usados ​​mesmo em criptografia, o que aumenta a vulnerabilidade de nossas finanças.

Como eliminar a influência de números pseudo-primos? Em princípio, é simples - você pode verificar os períodos para todos os sistemas numéricos, mas, para esta operação, para números grandes, não haverá tempo suficiente. Portanto, iremos para o outro lado. E o caminho também é simples (no sentido literal - ele usa outros números primos). Vimos que períodos curtos podem caber em um período inteiro um número inteiro de vezes, e isso nos dá números pseudo-simples. Mas o que nos impede de tomar e cancelar essas segundas-feiras? Sim, em geral, nada impede.

Por curtos períodos, o período completo ( $$$N-1$ ) deve ser dividido em muitos divisores. Assim, para o número 25, o período completo 24 é dividido em 2, 3, 4, 6, 8, 12. Há tantas possibilidades de penetrar no território protegido de números pseudo-simples. Então, precisamos apenas tomar o primo como um período completo, porque ele não se divide em nada e, portanto, automaticamente nos salva do elemento inimigo. É verdade que existe um "mas" - precisamos de números primos, e eles são conhecidos por serem ímpares (exceto por uma exceção - 2), o que significa que se $$$N-1$ simples então ele mesmo $$$N$ não pode mais ser simples. Portanto, teremos que admitir a possibilidade de surgir períodos incompletos. Por que isso é ruim? Como vimos acima, o período completo garante a simplicidade do número, mas ainda não provamos o período incompleto. Então, precisamos provar esse momento.

A prova é bem simples - para compostos $$$N$ período de duração $$$N-1$ duas vezes, obtidas em um sistema numérico que não é um múltiplo dos divisores de N, possuem apenas duas linhas de resíduos e nenhuma delas deve conter números que são múltiplos dos divisores de N $$$N$ (Números "proibidos"). Se pelo menos um elemento for excluído de uma linha de resíduos, o segundo diminuirá automaticamente na mesma quantidade (afinal, uma linha é igual a outra multiplicada por qualquer número que não esteja na primeira). Portanto, se houver divisores no número $$$N$ , obtemos uma duração total mais curta de dois períodos com todos os saldos "permitidos" que o valor do período completo e, assim, movemos a unidade de seu lugar no final do período inteiro, garantindo assim a ausência de pseudo-simplicidade. Mas o número de remanescentes de múltiplos divisores pode fornecer exatamente metade ou um terço do período completo? De fato, receberíamos, por exemplo, dois terços dos saldos "permitidos" (duas linhas) e um terço dos saldos "proibidos" e, no total - o período completo. Mas, para obter um terço, precisamos garantir a divisibilidade de todo o período ( $$$N-1$ ) por 3, que podemos facilmente excluir - pegue um número primo, multiplique-o por dois e adicione um ao resultado - voila, temos a garantia de excluir a pseudo-simplicidade. Ele tem o número de divisores divisíveis por divisores não pode ser igual a um terço do período completo, porque ele não pode dividir por três períodos completos. Resta a opção com metade do restante, que é um múltiplo dos divisores $$$N$ . Esta opção é eliminada um pouco mais difícil, então haverá uma pequena digressão abaixo.

Cálculo do período, ou todos os números - os filhos de Mersenne

O período de qualquer número pode ser calculado. No caso mais simples, o cálculo é feito simplesmente dividindo o canto $$$1 / N$ até encontrarmos o restante igual a um (no sistema numérico, não um múltiplo dos divisores $$$N$ ) Mas para grandes números, isso é irrealisticamente longo. Portanto, é necessário derivar uma fórmula para calcular o período. E essa fórmula existe, embora não em sua forma ideal, quando temos um número na entrada e um período na saída. A fórmula é:

$$

$$N = \ frac {b ^ {m + n + 1} -1} {b ^ n + k}$$

Aqui $$$N$ - número investigado, $$$b$ - a base do sistema numérico utilizado (base), $$$m$ - grau máximo $$$b$ em que o resultado da exponenciação é menor $$$N$ (em outras palavras, o índice de nível sênior em $$$N$ no sistema numérico $$$b$ ), $$$n$ - distância da esquerda para a direita em uma série de resíduos do índice $$$m + 1$ (igual ao número de bits em $$$N$ ) para um, $$$k$ É algum coeficiente inteiro.

Saída da fórmula

Pela definição da fórmula, é claro que (1) $$$b ^ {m + 1} -N = x$ isto é, o primeiro grau $$$b$ que é maior $$$N$ , permite subtrair $$$N$ e obter alguma diferença na forma $$$x$ . Também resulta da definição que (2) $$$x * b ^ n-k * N = 1$ aqui $$k é um coeficiente inteiro. Se você multiplicar(1)por$k$$$b n e substitua$b^n$$$x ∗ b n ao seu valor de(2), que é igual a$x*b^n$$$k N + 1 , obtemos então$kN+1$$$$b^{m+n+1}=N*b^n+kN+1=N*(b^n+k)+1 => N=\frac{b^{m+n+1}-1}{b^n+k}$ .

Propriedades úteis

Como podemos ver, usando esta fórmula, você pode obter números com um período conhecido. É verdade que há uma dificuldade - você precisa selecionar um coeficiente$$k , que para grandes números novamente se torna algo inatingível. Mas a fórmula nos dá outra coisa - vemos claramente como todos os números são formados. Sim, absolutamente todos os números inteiros positivos podem ser obtidos por esta fórmula, porque todos os números têm algum período. E, curiosamente, todos os números são obtidos dividindo o número de Mersenne por um de seus divisores. Lembre-se de que um número de Mersenne é igual a um número$k$$$$2^n-1$ .Na fórmula do numerador, vemos uma generalização para os números de Mersenne com qualquer base (incluindo 2, é claro). E se estivermos interessados ​​em números primos, não precisaremos de outras bases além de 2.

Sabendo que dividimos o número de Mersenne, seria útil calcularmos o período de números precisamente para o caso da divisão de números de Mersenne (lembre-se do conceito estendido de período aqui ). Mas o mais notável é que a fórmula para calcular o período de Mersen coincide com a fórmula para calcular um período do tipo$$$1/N$ . Bem, para derivar a fórmula para dividir os números de Mersenne, o mesmo princípio é usado para derivar a fórmula para dividir $$1 / N , com exceção da fórmula para calcular o valor em uma série de resíduos com índice$1/N$$$n que se parece com isso -$n$$$b n + 1 - 1b - 1 , e para números binários obtemos$\frac{b^{n+1}-1}{b-1}$$$$2^{n+1}1$ .

Agora temos todas as cartas em mãos e podemos começar o jogo abrindo os arqueiros pseudo-simples nas fileiras dos primos.

Como sabemos nas séries anteriores, quando divisível, todo o período Mersen de um número deve caber no número de dígitos do número Mersenne um número inteiro de vezes. Portanto, na fórmula acima, uma solução em números inteiros é possível apenas se o denominador tiver um período igual ao numerador ou várias vezes menor. Mas um período muito mais curto nos dará, incluindo divisores do próprio número$$N , porque se$N$$$N divide o número de Mersenne, então seus divisores também dividem o número de Mersenne. E este é um ponto muito importante, porque daí decorre que os comprimentos dos períodos dos divisores N dividem o comprimento do período$N$$$N completamente. Ou seja, se tomarmos$N$$$N é tal que seu período é igual ao período do numerador, então todos os divisores$N$$$N será ao mesmo tempo divisores do número de Mersenne e, portanto, devem se encaixar no período e$N$$$N e Mersenne numeram um número inteiro de vezes.$N$

Novamente cerca de metade do período

Agora, lembre-se de que paramos na busca de uma maneira de provar que podemos excluir o caso quando metade do comprimento de uma série de números residuais é um múltiplo de seus divisores. Queríamos provar isso para eliminar os números pseudo-primos ao escolher um número primo como base para a construção do período do próximo número primo. Então agora sabemos que, se o número construído tiver divisores, seus períodos sempre dividem o período do número construído completamente. Resta então verificar quais divisores podem se encaixar nas restrições dadas anteriormente ao número construído. E essas restrições - seu período é dividido apenas em$$2 e diante$2$$$$(N-1)/2$ . Portanto, apenas números com pontos podem ser divisores $$$2$ e $$$(N-1)/2$ . Período $$2 tem um número$2$$$2 , nenhum outro número desse período tem mais. Período$2$$$2 não cabe um número inteiro de vezes em$2$$$( N - 1 ) / 2 , porque$(N-1)/2$$$( N - 1 ) / 2 é primo, portanto a divisibilidade em três é excluída por esse período. Portanto, resta apenas uma possibilidade - os divisores têm um período$(N-1)/2$$$$(N-1)/2$ . Mas o número não pode ser menor ou igual ao seu período; portanto, o valor mínimo para os divisores é $$$(N-1)/2+1$ . Se multiplicarmos dois divisores mínimos, obtemos: $$( N - 1 ) 2 / 4 + ( N - 1 ) + 1 = ( N 2 - 2 N + 1 + 4 N ) / 4 = ( N 2 + 2 N + 1 ) / 4 , este valor tem de haver mais$(N-1)^2/4+(N-1)+1=(N^2-2N+1+4N)/4=(N^2+2N+1)/4$$$N , porque estamos falando de divisores$N$$$$N$ . Então obtemos a desigualdade $$$(N^2+2N+1)/4\leq N => N^2-2N+1\leq 0$ . Essa desigualdade pode ser negativa ou igual a zero apenas para $$N = 1 , portanto, para todos os números construídos dessa maneira, a pseudo-simplicidade é excluída se o número resultante for maior que$N=1$$$$1$ . Bem, para números menores, podemos testar a simplicidade, mesmo na mente.

Agora, existem duas opções - o novo número é um número primo, que é o que precisávamos, ou este é um número composto e, portanto, seu período não se ajusta a um número inteiro de vezes em um período inteiro, e, portanto, esse número pode ser facilmente verificado pela simplicidade, calculando o último valor em uma série completa de resíduos. Ou seja, o número construído pode ser facilmente verificado com testes de simplicidade probabilística padrão e, o que é importante, o resultado do teste não será probabilístico, mas garantido. Então, no final, nos livramos da maldição da pseudo-simplicidade, que pressiona todos os testes probabilísticos.

Mas é claro que a vida seria melhor se todos os problemas fossem resolvidos de maneira tão simples. Eliminando a pseudo-simplicidade, não excluímos números que não estão ocultos de ninguém e que não estão ocultos em nada. E com eles há mais um problema - por enquanto, podemos verificar um termo arbitrário na sequência de resíduos apenas elevando a uma potência e depois pegando o restante. Mas esse método é muito lento. Mais precisamente, é rápido o suficiente para os números usados ​​na criptografia, mas não é adequado para encontrar números primos grandes em casa, porque requer muitos anos de computação em um computador doméstico comum, o que não nos permite obter 400k $ (como mostrado aqui ).

No entanto, quase tudo está pronto para o cálculo de números primos criptográficos. Embora nosso velho amigo permaneça - maximalismo. Ele pergunta - se você pode usar um período $$$(N-1) / 2$ , o que impede o uso de períodos $$$(N-1) / 4, (N-1) / 6, (N-1) / 8$ etc? E acontece que com o devido cuidado - nada impede!

Da mesma forma que no período $$$(N-1) / 2$ para o período $$$(N-1) / 4$ somos capazes de estabelecer um limite inferior multiplicando por um primo por 4 e adicionando 1. Então garantimos a nós mesmos o pseudo-simples com períodos inferiores a $$$(N-1) / 4$ . Portanto, resta considerar a possibilidade de ocorrências pseudo-simples com um período múltiplo de 4, 3, 2 (1 é excluído para componentes, como mostrado acima). A partir da fórmula para calcular o número pelo período, vê-se que o período do dividendo deve ser igual ao múltiplo menos comum de seus divisores, o que implica que o possível período do número $$$N$ não deve caber apenas um número inteiro de vezes em $$$N-1$ (caso contrário, não haverá pseudo-simplicidade), mas também conterá um número inteiro de períodos de divisores. Assim, o número de divisores possíveis de um número pseudo-primo é bastante limitado. Como o período de qualquer número não pode ser maior $$$N-1$ , para um possível divisor $$$N$ dando como resultado da divisão 3, o período não pode ser mais longo $$$N / 3-1$ além disso, levamos em conta que o período de 3 é 2. $$$N / 3$ deve ser estranho porque é estranho $$$N$ . Pelo exposto, segue-se que o período par N / 3-1 é o menor múltiplo comum com um período 2 do número 3, o que significa que o período possível de um N potencialmente pseudo-simples deve ser igual ao período do número $$$N / 3$ . No total, há um valor do período $$$N$ cuja pseudo-simplicidade é possível, esse $$$(N-1) / 4$ . Para outros valores, $$$N / 3$ muito pouco ou seu período (e com ele o período $$$N$ ) irá para a área proibida abaixo $$$(N-1) / 4$ . A mesma história com números ímpares, menos $$$N / 3$ mas seus períodos não podem ser mais longos $$$(N-1) / 4$ e, portanto, todos eles são simplesmente excluídos da consideração. Agora mostre isso $$$N / 3$ não pode ter um período $$$(N-1) / 4$ , o que significa que não pode dividir todo o período inteiro. Primeiro, lembre-se da fórmula $$$m = a + b-2$ , que nos fornece o número de múltiplos resíduos de divisor para um número divisível apenas por $$$a$ e $$$b$ . No nosso caso $$$N$ deveria ser dividido em $$$N / 3$ e por 3, todos os outros divisores são excluídos, então obtemos - $$$m = N / 3 + 3-2 = N / 3 + 1$ . Agora, a partir de todo o período, você precisa subtrair os valores "proibidos", que serão $$$N / 3 + 1$ e divida por 4. Obtemos o período possível do trabalho $$ : $$$p = (N-1-N / 3-1) / 4 = N / 6-1 / 2$ que menos $$$(N-1) / 4$ , ou seja, um período de duração $$$(N-1) / 4$ impossível devido à necessidade de levar em consideração os resíduos "proibidos", que levam todos os períodos pseudo-simples possíveis para a região proibida (menos $$$(N-1) / 4$ ) Isso significa que essa situação nos garante que o número construído não é pseudo-simples e, portanto, podemos ter certeza novamente dos resultados de um teste de simplicidade probabilístico subsequente.

Da mesma forma, e considerando a divisibilidade de todo o período, pode-se obter os mesmos resultados para outros valores. Mas se quisermos obter números primos criptográficos dessa maneira, multiplicando por 2,4,6, aumentaremos o tamanho do número por um período muito longo, por isso faz sentido olhar na direção de outra opção - multiplicação de dois números primos. Se multiplicarmos um primo por outro, obteremos um número ímpar, portanto, também devemos multiplicar por 2 para obter um período par completo e um candidato ímpar para primo. O período completo neste caso será dividido em $$$2, a, b, 2a, 2b, ab$ onde $$$a$ e $$$b$ São números primos. Agora, precisamos provar que ou os períodos indicados não darão pseudo-simplicidade ou encontrar sinais nos alertando sobre a presença de pseudo-simplicidade. Observe que, se o período for igual a $$$2 * a * b$ , o número será primo (como mostrado acima). Também é mostrado acima que um número de meio período não pode ser pseudo-simples, portanto, um período de duração $$$ab$ pode ser excluído. Apesar de completo, você pode verificar o período $$$ab$ maneiras alternativas. Então, se o período é $$$ab$ , então, dado que $$$a$ e $$$b$ simples, fica claro que o múltiplo menos comum de períodos divisores $$$N$ só pode ser igual $$$ab$ , enquanto os períodos dos divisores podem ser iguais a $$$ab$ ambos ou um $$$a$ e outro $$$b$ . Como o período é sempre menor que o número em si, então $$$(ab + x) * (ab + y)$ obviamente haverá mais $$ . Portanto, a pseudo-simplicidade não é possível com esse período. Portanto, resta verificar os períodos $$$2, a, b, 2a, 2b$ . 2 é menor que o período mínimo possível para todos os números, maior que 3, portanto excluímos esse período. Agora, suponha que o número construído seja dividido por $$$m$ e $$$n$ , então com a igualdade do período $$$N$ significado $$$a$ , seus períodos também serão iguais $$$a$ , porque este é o único múltiplo menos comum para dois números, porque $$$a$ não dividido em nada. Segue-se que $$$(a + x) * (a + y) = N = ab * 2 + 1$ onde $$$a + x = m$ - o primeiro fator possível com um período $$$a$ e $$$a + y = n$ segundo. Seguinte: $$$a ^ 2 + ax + ay + xy = 2ab + 1$$$$=>$$$$a ^ 2 + ax + ay + (ka + r) = 2ab + 1$$$$=>$$$$a + x + y + k = (2ab + 1-r) / a$ . Aqui $$$r$ pode ser igual a apenas um, caso contrário, o número inteiro não funcionará à esquerda. Então: $$$x + y + k = 2b-a$ , da qual se conclui que se $$$a \ geq 2b$ , então pseudo-simples com um período $$$a$ não pode ser. Resta verificar a pseudo-simplicidade em $$$a <2b$ , o que pode ser feito verificando os valores na série de resíduos na posição $$$a$ se houver 1, esse número pode ser pseudo-simples e deve ser excluído de outras operações. Raciocínio para $$$b$ completamente análogo, o que significa a necessidade de verificar a igualdade da unidade e seu restante, desde que $$$b <2a$ .

Para o período $$$2a$ nós temos: $$$4a ^ 2 + 2ax + 2ay + xy = 2ab + 1$$$$=>$$$$4a ^ 2 + 2ax + 2ay + (ka + r) = 2ab + 1$$$$=>$$$$4a + 2x + 2y + k = (2ab + 1-r) / a$$$$=>$$$$2x + 2y + k = 2b-4a$ . Temos isso por $$$4a \ geq 2b$ (ou equivalente - $$$2a \ geq b$ ) novamente, não pode haver simplicidade, mas se $$$2a <b$ , então você precisa verificar o saldo da posição $$$2a$ . Da mesma forma para $$$b$ - verifique se $$$2b <a$ . No total, obtemos para $$$a$ e para $$$b$ a necessidade de verificar apenas itens de linha $$$2a$ e $$$2b$ porque períodos $$$a$ e $$$b$ repetirá apenas na posição $$$2a$ e $$$2b$ . A verificação é realizada apenas nas condições acima, o que quase dobrará o processo ao verificar valores grandes $$$a$ ou $$$b$ , porque para eles eles devem $$$a \ geq 2b$ com o esquema de geração simples abaixo, e valores mais baixos serão verificados muito rapidamente devido ao seu pequeno tamanho.

Assim, os fundamentos teóricos foram mostrados acima como capazes de gerar números primos garantidos para áreas críticas, como a criptografia.

Além disso, é aberta uma maneira de verificar a simplicidade de um número arbitrário, desde que sejam encontrados os divisores de todo o período ( $$$N-1$ ) Portanto, para números primos <126.000.000, o número de "números primos multiplicados" pertencentes à classe é 676625, com o número total de números primos 7163812, o que nos dá um pouco menos de 9,5%. Para números primos de até um bilhão, temos 3,49% pertencentes à classe 2p + 1, 1,8116% da classe 4p + 1, 2,4709% da classe 6p + 1 e apenas 7,7746%, onde p é um número primo. É verdade que deve-se notar que a decomposição de todo o período de grandes números é muito difícil. Nesse caso, você pode oferecer uma verificação recursiva, que aumentará um pouco o tamanho dos números disponíveis para verificação, mas ao mesmo tempo reduzirá significativamente a proporção de números que passam nessa verificação, porque se o coeficiente que determina a associação das classes de números primos recursivos for igual a 0,2, já na segunda verificação, possuem apenas 0,04 ou 4% do número total de números primos. No entanto, em alguns casos, essa abordagem pode ser benéfica.

Resultados práticos

O gerador em si, é claro, foi escrito e testado, já que a complexidade é mínima. Durante a verificação, verificou-se que o seguinte algoritmo seria totalmente funcional:

Temos, por exemplo, 1.000 primos iniciais, que podem ser gerados usando a peneira de Eratóstenes ou simplesmente baixados daqui . Em seguida, multiplicamos cada valor por cada restante e não esquecemos de multiplicar por dois e, em seguida, adicionamos um. O candidato resultante é frequentemente dividido por 3, porque os números primos têm uma característica específica semelhante à presença de uma carga nas partículas na física. Pessoas simples com a mesma “carga” são repelidas e, com outras diferentes, são atraídas. Nesse caso, a “carga” é o restante da divisão por 3. Ou seja, se o restante da divisão por 3 for o mesmo para os dois primos, o novo primo não funcionará, porque será dividido por 3. E se o restante for diferente, podemos encontrar o caminho certo. candidato a simples. Além disso, todos os simples obtidos por multiplicação são “sincronizados”, ou seja, recebem o mesmo restante igual a 2. Portanto, é inútil multiplicá-los por si mesmos novamente. Portanto, para obter novos números primos, precisamos filtrar a parte do 1000 inicial para a qual o módulo do triplo (o restante da divisão por 3) é 1. Assim, após a primeira multiplicação de todos com todos, crescemos na quantidade de números que já não têm sentido multiplicar entre si, portanto, para aumentar ainda mais o tamanho (àquele usado na criptografia), precisamos multiplicar repetidamente os números primos obtidos pelos números "carregados de forma oposta" selecionados anteriormente. Após multiplicar e adicionar uma unidade, realizamos verificações de acordo com o critério para a possibilidade de pseudo-simplicidade e, se o critério for atendido, verificamos o restante na posição 2a para cada candidato. Se houver 1, o candidato será rejeitado. Em seguida, cada candidato é verificado pelo teste probabilístico usual, ou seja, o valor é calculado na série de resíduos na posição $$$(N-1) / 2$ se é 1 ou $$$N-1$ , diante de nós há um número primo garantido.

Ao executar a geração, deve-se ter em mente que, a cada iteração, é obtido um aumento no número de primos gerados, ou seja, o coeficiente de multiplicação para 1.000 primos iniciais é muito mais que a unidade. Portanto, para obter primos criptográficos, é necessário limitar a geração; caso contrário, isso levará muito tempo e poderá não haver memória suficiente. Ao mesmo tempo, não se deve reduzir o conjunto inicial de simples, porque a geração deve ser o mais aleatória possível, para que, conhecendo seu algoritmo, o invasor não preveja os valores resultantes. Para isso, é necessário implementar um mecanismo para cortar os galhos da árvore geradora, o que permite obter, a cada vez, simples e únicos, distantes dos gerados anteriormente. E, claro, cortar o excesso acelera significativamente o processo.

O tempo de execução do teste depende do número de candidatos gerados. Cada um dos candidatos passa em um teste de probabilidade, que retarda a geração ao máximo. Nas execuções de teste para obter algumas centenas de alcance simples $$$2 ^ {900}$ - $$$2 ^ {1200}$ 5 a 20 minutos foram gastos. Essa diferença de tempo é explicada por várias maneiras pelas quais o algoritmo passa na árvore de geração. Assim, inicialmente, a geração é limitada a cerca de 10 números, mas à medida que o tamanho criptográfico se aproxima, a geração diminui devido a uma redução significativa no coeficiente de multiplicação com o aumento do número. Portanto, é necessário aumentar o número de primos intermediários, mas é difícil dizer quão específico é e, portanto, um simples aumento na quantidade permitida por um fator de dois é usado para limitá-lo com um aumento no tamanho do número e um excesso de um limite aproximado. Como resultado, dentro dos limites das limitações, o número de novos simples pode flutuar e, assim, fazer uma diferença significativa no tempo total de geração.

A seguir, o texto de um procedimento Java que gera números primos. Naturalmente, ele não atende aos requisitos criptográficos que vão muito além do código do programa e se relacionam principalmente a questões organizacionais. Na parte puramente de software, o procedimento não implementa o mecanismo para aparar as ramificações da árvore de geração, com exceção da restrição mais simples. No entanto, como um exemplo da implementação do algoritmo de geração, o programa pode ajudar com algo.

Parâmetros de entrada é a lista inicial de simples e PrintWriter para salvar o resultado em um arquivo. Após a conclusão do algoritmo, o arquivo conterá todos os produtos dos números primos gerados com os números iniciais que possuem um módulo de três igual a um. O resultado pode ser verificado usando serviços online que implementam a fatoração de números, mas deve-se entender que eles podem usar um teste probabilístico para simplificar antes de executar a fatoração e, portanto, para verificar a abordagem proposta, eles se tornam inúteis (porque todos os números já são verificados por um teste probabilístico). Porém, alguns deles imediatamente começam a fatorar o número proposto em fatores; esses sites podem incutir alguma confiança adicional na correção do método proposto.

public static void generatePrimes(List<Integer> primes, PrintWriter pw) { List<BigInteger> mod3_1 = new ArrayList<BigInteger>(); List<BigInteger> l = new ArrayList<BigInteger>(); BigInteger three=BigInteger.valueOf(3), two=BigInteger.valueOf(2); for (int k=0;k<primes.size()-1;k++) { BigInteger seed=BigInteger.valueOf(primes.get(k)); BigInteger s2=seed.shiftLeft(1); BigInteger r0=seed.remainder(three); if (r0.intValue()==1) mod3_1.add(seed); for (int i=k+1;i<primes.size();i++) { BigInteger p=BigInteger.valueOf(primes.get(i)); BigInteger r=p.remainder(three); if (r.intValue()==r0.intValue()) continue; // divisible by 3 else addIfPrime(p,seed,s2,two,l); } } List<BigInteger> ps=l; do { System.out.println("found "+l.size()+", bits="+l.get(0).bitLength()); l=new ArrayList<BigInteger>(); for (int k=0;k<ps.size();k++) { BigInteger seed=ps.get(k); BigInteger s2=seed.shiftLeft(1); for (int i=0;i<mod3_1.size();i++) addIfPrime(mod3_1.get(i),seed,s2,two,l); int n=100000; // change following to adjust for required bit count if (l.size()>0) if (l.get(0).bitLength()<700) n=10; else if (l.get(0).bitLength()<800) n=20; else if (l.get(0).bitLength()<900) n=40; if (l.size()>n) break; } ps=l; for (int i=0;i<l.size();i++) pw.println(l.get(i)); pw.flush(); } while (l.size()>0); System.out.println("Done"); } private static void addIfPrime(BigInteger a, BigInteger b, BigInteger b2, BigInteger two, List<BigInteger> l) { BigInteger a2=a.shiftLeft(1), fp=b.multiply(a2), n=fp.add(BigInteger.ONE); BigInteger r=null; if (a2.compareTo(b)<0) r=two.modPow(a2,n); // 2a<b else if (a.compareTo(b2)<0) r=two.modPow(a,n); // a<2b if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=null; if (b2.compareTo(a)<0) r=two.modPow(b2,n); // 2b<a else if (b.compareTo(a2)<0) r=two.modPow(b,n); // b<2a if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=two.modPow(fp.shiftRight(1),n); if (r.compareTo(BigInteger.ONE)!=0) return; l.add(n); } 

Bem, agora que você (bem, quase) sabe tudo sobre a geração de números primos, talvez seus interesses vão além da criptografia sozinho e será interessante o estudo da teoria dos números, pois, como mencionado acima, está disponível para alunos da quinta série, mas, ao mesmo tempo, também permite que você encontre diamantes verdadeiros independentemente, sem esperar pela ajuda de matemáticos sérios.