Get best of the week

Um modelo de uma série natural de números e seus elementos. Células com várias linhas




Em outro trabalho de uma série de artigos sobre a série natural de números (NRF), são usados os conceitos e a notação G 2 ± - o modelo NRF na forma de um plano infinito discreto (de células com coordenadas (x1, xo)) ( veja aqui ), no qual o compósito é par ou o número natural ímpar (VLF) em cada célula do modelo é descrito pela relação N = x1 2 ± xo 2 . Consideramos outra propriedade importante da Série Natural de Números, a multiplicidade de células modelo, para o módulo de cifra RSA, que é importante para resolver o problema de fatoração de grandes números (ZFBCH).

Sobre anéis algébricos e a cifra RSA


A RSA cifrada e similares são basicamente baseadas em uma construção matemática estrita - um anel de resíduo numérico finito (KCHKV) modula um número composto N = dmdb, onde dm é um divisor principal menor, db é um divisor maior.

O requisito para a chave (em particular, o módulo N) da cifra é que ambos os divisores sejam primos de capacidade muito alta (até 300 dígitos decimais). veja aqui

Outro requisito importante para uma chave de cifra é o requisito para a diferença dos divisores
| db - dm | = Δ. Deve ter a mesma alta capacidade que os próprios divisores. Um exemplo simples do KPKV é o fragmento inicial de uma série natural de números com a adição de um elemento zero. Todos os números seguidos formam um anel de 0 a N - 1. Mais detalhes sobre anéis podem ser encontrados em livros de álgebra superior.

A resistência da cifra RSA à divulgação de chaves é estimada como muito alta e todos os esforços dos criptoanalistas do mundo para decifrá-la desde que sua publicação (1978) ainda não teve sucesso. Existem várias razões para esta situação.

Os algoritmos publicados para implementar ataques à cifra são baseados no conceito de uma peneira numérica proposta por Eratóstenes antes da nova era. A cada nova publicação, vemos uma versão ligeiramente aprimorada do algoritmo, mas, aparentemente, essas melhorias não são suficientes para ter sucesso. A idéia da peneira de Eratóstenes [1] foi progressiva em sua época, mas agora não funciona.

Na Internet, há uma lista de números RSA que a empresa é convidada a fatorar. A lista foi publicada em 1991 e está longe de ser completa. Uma análise dos resultados da decomposição multiplicativa de números da lista está disponível, pois os próprios números estão abertos a todos.

A partir da análise, conclui-se que quanto mais dígitos na descrição do número, mais tempo era necessário para sua decomposição. A conclusão é que a decomposição do módulo N utiliza algoritmos muito sensíveis à capacidade dos números, ou seja, os algoritmos usam as propriedades dos números que são muito dependentes de sua capacidade. Quero dizer propriedades como os "sinais de divisibilidade" dos números. Eles praticamente não dependem da profundidade de bits do número fatorável ( veja aqui ).

Os trabalhos publicados são limitados, em regra, ao processamento do próprio número, ignorando seu ambiente, as propriedades de vizinhos próximos e distantes em um sistema numérico específico. Altas esperanças dos autores e expectativas são atribuídas a novos dispositivos de computação: quantum, fóton, molecular e similares.

Autores de publicações e proprietários da empresa, ou seja, algoritmos de criptografia não negam outras novas abordagens e não excluem a possibilidade de criar novos algoritmos baseados em novas idéias, para as quais a tarefa de fatorar grandes números não será válida e sua solução será bem-sucedida. Eu, como autor desta publicação, sou atraído apenas por novos desenvolvimentos originais no campo da solução do HFBCH.

A maioria das minhas publicações é dedicada apenas a novas abordagens, começando com a síntese de modelos da série natural de números, estudando suas propriedades e usando essas propriedades no desenvolvimento de novos algoritmos originais para resolver o ZFBCH. Seguindo nesta direção, foi possível estabelecer (aberta) a Lei de Distribuição de Divisores (RDA) do número N na NRCh RDA .

Verticais (colunas) G 2 ± - modelos NRF


Um exemplo dessa nova abordagem é o uso de somas de pares de números ao quadrado. Esses números são obtidos da NRF e devem atender aos requisitos: dois números são adjacentes e sua soma é igual ao número composto N que queremos fatorar, mais dois números são quadrados que satisfazem a equação N + x1 2 = xo 2 .

Outro requisito: a soma dos quadrados dos números adjacentes da decomposição aditiva com os dois quadrados encontrados deve ter valores iguais (correspondentes) ( veja aqui ). Se for possível atender aos requisitos acima, a fatoração de N é garantida. O exemplo 1 abaixo ilustra essa possibilidade.

O esquema considerado é original, difere do proposto por L. Euler e outros matemáticos em um entendimento mais simples e transparente.

Exemplo 1 . ( Soma dos quadrados ). É fornecido o número composto N = dmdb = 209723. É necessário encontrar sua decomposição multiplicativa, ou seja, os valores dos fatores dm e db.
Solução . Usamos as propriedades das somas dos quadrados em 2+ - o modelo circular hiperbólico.

Pegamos a raiz quadrada de N, √209723 = 457.955 = 458 e arredondamos para um número inteiro maior.
Em seguida, encontramos as diferenças dos seguintes quadrados e o número N com a verificação da igualdade dessa diferença em relação ao quadrado inteiro: 458 2 - 209723 = 41 ≠ ▢, 459 2- 209723 = 958 ▢ ▢, 460 2 - N ▢ ▢,
461 2 - N ≠ ▢,

462 2 - 209723 = 3721 = 61 2 = ▢. No quinto passo, a diferença desejada é igual ao quadrado inteiro. Encontramos a decomposição aditiva de N = 209723 = sm + sb = 104861 + 104862 em termos adjacentes. Verifique a igualdade da soma dos quadrados nas células do modelo
N (x11, xo) = N (x11, sm), N (x12, xo2) = N (x12, sb), em
que sm, sb são os números das colunas e x11 e x12 são os números das linhas modelos. Esses números são determinados a partir das relações de igualdade das somas dos quadrados.

sm 2 + 462 2 = 104861 2 + 213444 = 10995829321 + 213444 = 10996042765;
sb 2 + 61 2 = 104862 2 + 3721 = 10996039044 + 3721 = 10996042765. As quantidades nas células, conforme o esperado, acabaram sendo iguais entre si.

Para tais somas, escrevemos a igualdade sm 2 + 462 2 = sb 2 + 61 2 e a transformamos na igualdade da diferença de quadrados 462 2 - 61 2 = sb 2 - sm 2 . À direita, a diferença dos quadrados é sempre igual a N e a diferença esquerda é convertida no produto
462 2 -61 2 = (462 - 61) (462 + 61) = 401 · 523 = 209723 = N.

Ambos os fatores são números primos, ou seja, a fatoração do número N é completada com sucesso. A desvantagem dessa abordagem é a necessidade de encontrar a soma dos quadrados com valores correspondentes nas colunas adjacentes do modelo. Com grandes números, esta é uma operação bastante demorada. Em essência, essa tarefa é reduzida à seleção de um quadrado desse tipo, que, somado ao número N, fornece um quadrado maior.

Horizontal (linhas) G 2- - modelos de baixa frequência


Trabalhar com números, resolver problemas urgentes como o HFBCH ou o logaritmo discreto sugere que o pesquisador de alguma forma ordenou e classificou os números ( aqui ) e não trabalha cegamente, não de forma aleatória, mas prediz o resultado esperado, com base nas hipóteses sobre o resultado.

Uma das propriedades das linhas (horizontais) do modelo G 2- - NRF é a dependência linear dos valores de cada célula da próxima linha do modelo sobre os valores nas células da célula anterior, que é expressa pelo somatório simples dos valores das células da parte superior das duas linhas adjacentes com um valor constante da última célula da linha inferior. é
N (x1, x) = N (H1-1 ho) + N (x1, x1 - 1), é executado enquanto ho toda a linha de fundo (ver Tabela 1) clicável



Figura 1 - Valores que são múltiplos dos números ímpares compostos nos primeiros 100 (destacados por um preenchimento)
A figura mostra células preenchidas com um preenchimento com números iguais ao produto dos números das diagonais.

A peculiaridade desses números é que os números das diagonais no módulo N do CCCH, considerados como elementos do anel, quando eles são exibidos (quadrados) e o resultado é módulo, os anéis permanecem eles mesmos (elementos fixos).

O primeiro número como o módulo é N = 15. Para isso, a célula múltipla contém o produto dos números das diagonais 10 · 6 = 60 = 15 · 4 múltiplos do módulo com o coeficiente k = 4. Para os números das diagonais: 6 2 ≡ 6 (mod15); 10 2 × 10 (mod15).

Tome o segundo número como o módulo N = 35. Para isso, a célula múltipla contém o produto dos números das diagonais 21 · 15 = 315 = 35 · 9 múltiplo do módulo com um coeficiente k = 9. Para os números das diagonais: 15 2 ≡ 15 (mod35);
21 2 ≡ 21 (mod35). Assim será para todos os números N pertencentes à diagonal longa D1, na linha em que a célula N múltipla é indicada pelo preenchimento.

Exemplo 2. ( Cálculo de uma célula múltipla ). O módulo KChKV composto N = 77 está definido. de acordo com as propriedades 1,2, o valor na célula N (x1 = 39, xo = 17) é calculado como a soma dos valores na célula acima do dado e na última célula da linha x1 = 39 igual ao módulo do CCFV.
N (x1, xo) = N (x1 = 39, xo = 17) = N (38, 17) + N (39, 39-1) => 1232 = 1155 +77.
N (x1, xo) = N (x1 = 39, xo = 17) = N (38, 17) + N (39, 39 –1) = 38 2 - 17 2 + 39 2 - 38 2 => 1232 = 1155 +77.

Por outro lado, o valor em cada célula de uma linha arbitrária é calculado como a diferença dos quadrados das coordenadas da célula ou como o produto da diferença das coordenadas da célula pela soma
N (x1, xo) = N (x1 = 39, xo = 17) = 39 2 - 17 2 = ( 39-17) (39 + 17) = 22,56 = 1232 = 16,77.

Existem outras maneiras menos óbvias de calcular o valor na célula.

O exemplo considerado é notável, pois estabelece uma conexão formalizada do modelo em consideração com um anel numérico finito de resíduos pelo módulo composto.

Sabe-se que a primeira diagonal longa 2 ± é o modelo NCR. contém em suas células todos os seguintes números, ímpares seguidos, que podem ser considerados como módulos para reduzir estruturas algébricas. As estruturas em si são formadas a partir de elementos - números naturais. Aqui não vamos nos aprofundar nos conceitos de álgebra superior, mas indicaremos apenas fatos que são interessantes do ponto de vista de sua representação no modelo G 2 - da NRF.

Entre todos os elementos do módulo N da estrutura QPCW, existe um conjunto I = {x}, chamado idempotentes, e cujos quadrados, após a redução (redução do módulo), mantêm seus valoresx 2 x (mod N). Tais elementos são chamados imóveis na teoria dos mapeamentos. Além disso, indicaremos idempotentes pelos símbolos I1, II, ...

Outra classe de elementos, o conjunto H = {x} do QCF, chamado involutions, possui a seguinte propriedade x 2 ≡ 1 (mod N). Além disso, denotaremos involuções pelos símbolos 1, 2, ...

O papel desses elementos do anel é muito grande na solução de problemas aplicados, e aqui consideraremos alguns fatos interessantes e úteis para resolver o HFBC. O fato é que a teoria dos anéis não responde à pergunta de quais dos elementos do anel são idempotentes, que são involuções. Como estabelecer esses elementos, como determinar seus valores, para um determinado módulo N do anel.

Acontece que os idempotentes são, além disso, elementos que são múltiplos de divisores diferentes do módulo N. O módulo do produto é zero, pois é um múltiplo de N, mas a soma de dois idempotentes é igual a N + 1. Tendo o valor de idempotente, podemos resolver o problema de encontrar o maior fator comum (comum tanto para o módulo quanto para idempotente).

E a partir daqui não é difícil resolver o problema de fatoração do módulo de anel, o que garantirá que a chave privada da cifra assimétrica seja encontrada e que o ataque a essa cifra seja bem-sucedido.

O exemplo considerado com uma célula com um valor que é um múltiplo do valor na célula mais à direita da linha (um múltiplo da célula) tem a peculiaridade de que o produto das diagonais no múltiplo da célula é o produto dos idempotentes do anel.

Fatoração de N usando idempotentes de um anel de número finito


.. Esquemas VLF N. Fatoração Utilização de idempotents KPKV
Todos ( 1 , ) G 2 - células são únicos e são combinadas em linhas: horizontais com números 1 (eles contêm células número 1), verticais com números 1, diagonais: curta (K) com números x1 + xo e longo (D) com números x1 - xo.

Em cada célula (x1, xo) do modelo, as linhas dos tipos nomeados se cruzam, cujos números são determinados pelas coordenadas da célula. As células do modelo podem conter não números, mas apenas diferenças representáveis ​​dos quadrados de outros números (coordenadas).

A horizontal do modelo pode ser definida pelo número x1 e a vertical pelo número xo, respectivamente. Cada célula contém o número N (x1, xo) = x1 2 - xo 2. As últimas células horizontais formam uma diagonal longa D1 e contêm os valores

N (x1, x1 - 1) = x1 2 - x1 2 + 2x1–1 = 2x1 - 1,

dependendo do número horizontal. As células desta diagonal contêm todos os seguintes números ímpares seguidos. Para o intervalo de números [d1min, d1max], d1min, d1max ∊ D1, a soma de seus valores determina a forma aditiva do número N.

Exemplo 3 ( Cálculo do valor kN de uma célula múltipla como a soma dos elementos de um fragmento da diagonal D1 )

= 77 + 75 + 73+ ... + 37+ 35 = 1232 = 16 · 77 = 22 · 56 , em
que i = 1 (1) 22 . O último significa que o número de termos (22) no total é igual a um divisor menor


N (x1, xo) e o termo médio (56) é o divisor maior de N (x1, xo).

Se as células do modelo G 2 ± diagonal principal com a equação x1 = xo forem incluídas no modelo G 2 - , o valor nelas será zero. Então, ao gerar valores nas células da linha com o número x1 em sua última célula, obtemos o valor 2x1–1, pois ele resume o valor da célula da linha com o número x1–1 localizado acima e esse valor é 0. Propriedades importantes de G 2 - - O modelo e suas células são os seguintes.

Propriedade 1. Todos os números nas células da horizontal atual x1 podem ser obtidos a partir dos números nas células correspondentes da horizontal anterior (superior) com o número x1 - 1 somando seus valores com um valor constante de 2x1 - 1.

Tabela 1 - Fragmento G 2 - - modelos de 2 linhas 38 e 39, N = 77



De fato, N (x1, xo) = N (x1 –1, xo) + 2x1 - 1 = x1 2 - 2x1 + 1+ 2x1 - 1– xo 2 = x1 2 - ho 2 .

Propriedade 2. A segunda propriedade segue da primeira. Qualquer número N (x1, xo) na célula horizontal com o número x1 pode ser obtido como a soma dos valores nas células do fragmento da diagonal longa D1, dos quais o d1max maior é o número da última célula horizontal x1 e o d1min menor é o número na célula que intercepta a diagonal D1 com ho vertical.

Propriedade 3 . Para um VLF N quadrado colocado na célula da extrema direita da horizontal x1, nessa horizontal, há uma célula na qual um múltiplo de N será colocado, ou seja, o número kN, k> 1. A pesquisa dessa célula é um problema não trivial e difícil de resolver.

Uma ilustração dessa propriedade são os dados na Tabela 2. Para os números das primeiras cem que não possuem quadrado e composto N, colocados nas células d1∊ D1 com um valor de 2x1 - 1, outra célula (x1, xo) contendo o valor N (x1, xo) = kd1 é um múltiplo d1

Tabela 2.


K · D é o produto das diagonais que se cruzam na célula com o valor de kN.

Propriedade 4 . Todos os números N (x1, xo) nas células da horizontal horizontal x1 podem ser obtidos como o produto dos números das diagonais a = x1 + xo curto eb = x1 - xo longo, cruzando-se nessas células.

É conveniente ilustrar as propriedades com um exemplo numérico.Exemplo
4 . Vamos considerar 2 -- modelo. Definimos N = pq = 7 · 11 = 77 para a fatoração da ELF.Este é um número ímpar e para ele existe uma célula na diagonal longa D1 que fica horizontalmente com o número x1 = ½ (N + 1) = 39.

O próprio número 77 é colocado no último célula desta horizontal, contendo, como todas as outras células, a diferença dos quadrados das coordenadas x1 2 - xo 2 .

A primeira célula desta horizontal na vertical xo = 0 é ocupada pelo número
x1 2 = 39 2 = 1521. O valor do número em qualquer célula intermediária da horizontal x1 é, por um lado, o produto dos números b = x1 - xo longo e curto a = x1 + xo diagonais, a interseção ab = (x1 + xo) (x1 - xo) nela.

Por outro lado, é igual à diferença entre os quadrados dos números horizontais (para todas as células horizontais esse quadrado x1 2 é o mesmo) e o vertical xo 2 , que também se cruzam nessa célula intermediária, ou seja,
N (x1, xo) = x1 2 - xo 2 .

Além disso, todos os valores nas células horizontais x1 (pela propriedade 1) são iguais à soma dos valores N (x1, xo) = N (x1 - 1, xo) + 77 das células horizontais correspondentes com o número x1 - 1, ou seja, da parte superior acima e uma constante igual a N = 77.

Suponha que, para os números das diagonais, o valor x1 + xo = I1 = 56 seja escolhido para o curto e para o longo o valor x1 seja xo = I2 = 22, ou seja, valores de idempotentes não triviais do módulo de anel de resíduo N.

Quando multiplicamos idempotentes não triviais como as diagonais do modelo G 2 - , obtemos em alguma célula horizontal (com o número x1 = 39) como produto o número múltiplo do módulo de anel de resíduo (77), localizado na última célula desta horizontal, ou seja, I1 · I2 =

56,22 = kN = 16,77 = 1232. Também é sabido pela teoria dos anéis que a soma dos idempotentes não triviais é igual a 1 + 2 = N + 1. Assim, com relação aos idempotentes desconhecidos, obtemos um sistema algébrico de equações que, além de dois idempotentes desconhecidos, também contém um terceiro coeficiente de multiplicidade desconhecido - k> 1.



Felizmente, o coeficiente k pode ser determinado fora do sistema de equações algébricas. Suponha que o coeficiente k já seja determinado por nós k = 16. Então resolvemos o sistema de equações.



O último termo na equação quadrática deve ser o quadrado de 39. Para fazer isso, adicione o número 289 = 17 2 aos lados esquerdo e direito da equação . Então obtemos
(I2 - 39) 2 = 17 2 ou I2 - 39 = ± 17 e, finalmente, I2 = 17 + 39 = 56 ou I2 = 39 - 17 = 22.
Resposta: Idempotentes são iguais a I2 = 22; I1 = 56 ou vice-versa: I2 = 56 e I1 = 22.

Agora voltamos à questão de determinar o valor do coeficiente de multiplicidade k.
Considere o seguinte algoritmo para determinar o coeficiente de multiplicidade do módulo N.

Algoritmo

1. Um número composto N = 77 é dado - o módulo do anel de resíduo;

2. Determine por N o valor do número horizontal x1 = ½ (77+ 1) = 39, na primeira célula
onde colocamos um quadrado 39 2 = 1521 e, em sua última célula, colocamos N = 77;

3. O produto dos idempotentes aparece na célula horizontal intermediária x1 = 39; para esta célula, a condição considera que o número é igual a kN e é representável pela diferença dos quadrados dos números naturais.

4. Portanto, subtraindo repetidamente do quadrado do número da primeira célula horizontal 39 2 = 1521 os valores x0 = 1,2,3, ... sucessivamente, cada vez que determinamos o valor de k, e é um número inteiro? Assim que a diferença se torna um múltiplo de N, o problema é resolvido: kN é encontrado.

Vamos considerar também outro algoritmo para determinar o coeficiente de multiplicidade do módulo N.

1. Um número composto N = 77 é dado - o módulo do anel de resíduo;

2. Determine por N o valor do número horizontal x1 = ½ (77+ 1) = 39, na primeira célula em
que colocamos o quadrado 39 2 = 1521 e em sua última célula colocamos N = 77;

3. O produto dos idempotentes aparece na célula intermediária da horizontal x1; para esta célula, a condição considera que o número é igual a kN e é representável pela diferença dos quadrados dos números naturais.

Usando a propriedade 2, o número kN pode ser encontrado pelo caminho indicado lá, ou seja, somando números ímpares decrescentes monotonamente a partir de um fragmento da diagonal D1 começando com d1max = 77 e terminando com d1min, cujo valor é a priori desconhecido, d1min, d1max ∊ D1.

4. Para estabelecer o último termo após cada etapa da soma, a divisibilidade da soma obtida é verificada por N = 77. A solução é a soma divisível por 77.

Tabela 3 - N números são múltiplos de 3 na linha central (a previsão é destacada pelo preenchimento).



Nesta tabela são números compostos (múltiplos três) seguem com intervalos alternados de 6 e 12. De fato, na linha N temos 21 - 15 = 6 e 33 - 21 = 12 e mais na mesma ordem. Presumivelmente, as lacunas entre os valores tabulares de N são devidas ao fato de que nos seis números adjacentes existem primos gêmeos, por exemplo, 16, 17, 18, 19, 20.

O próximo múltiplo de três 21 é apenas o sexto consecutivo após 15. Em 12 números consecutivos, pares de números primos duplos são possíveis, por exemplo, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ou os quadrados 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 são misturados com gêmeos simples. Em geral, a escolha é feita com a garantia de não encontrar um número não composto em uma posição correspondente a um múltiplo de três.

Nomeadamente, essa condição garante a confiabilidade da previsão muito à frente. Os números ausentes acabam sendo múltiplos não apenas de três, mas também de números primos grandes, o que permite que sejam considerados de outras posições.

Lista de publicações

1.Stechkin B.S., Matiyasevich Yu.V. Peneira de Eratóstenes // Anais da escola internacional de S.B. Stechkina sobre a teoria das funções. Ecaterimburgo, 1999. - p. 148

More articles:


All Articles