Bem, eu não sou especialista no assunto, mas uma observação óbvia é que para tentar na força bruta fatorar N, vc vai usar no máximo 2√N/ln(N) divisões (pelo teorema dos números primos). Uma coisa bastante interessante seria vc mostrar que seu algoritmo faz menos interação que isso, ou ainda que na maioria dos casos ele é melhor.
Em ter, 11 de jan de 2022 10:03, Eric Campos Bastos Guedes < ebastosgue...@gmail.com> escreveu: > Proponho um algoritmo para quebrar o RSA. O algoritmo que eu propus antes > trabalhava com números muito grandes e por isso podia não funcionar > direito. Esse trabalha com números bem menores porque usa módulo N numa > etapa. O algoritmo e sua explicação estão no YouTube com o mesmo título > desse e-mail. São dois vídeos, o que conta é o mais recente deste ano de > 2022. > > QUEBRA DO RSA - ALGORITMO N.2 > > PASSO 1: a=3 > > inicializando o valor de a > > PASSO 2: N é o inteiro a ser fatorado > > N é o número usado no RSA. N é o produto de dois números primos grandes > não muito próximos. > > PASSO 3: M=N^512 (N elevado a 512) > > M é um número grande mas não muito grande. O valor de P não vai > ultrapassar muito o valor de M. P é uma variável inteira que acumula > fatores primos. Aí você faz MDC(P, N) para tentar fatorar N. > > PASSO 4: a=a+1 > > O valor de a é atualizado para a+1, isto é, é acrescentado 1 ao valor de > a > > PASSO 5: P=a > > O valor de P é inicializado > > PASSO 6: b = número aleatório entre 0 e 1 > PASSO 7: Se b > 1/2 faça c=1 senão faça c=-1 > > O objetivo dos passos 6 e 7 é atribuir à variável c um valor que pode ser > 1 ou -1. Isso nem precisa ser feito de modo aleatório, mas acho que vai > funcionar melhor se for aleatório. > > PASSO 8: P=P(P+c) > > É uma atribuição de valor. O novo valor de P passa a ser P(P+c). Note que > P+c é relativamente primo com P. Na prática são acrescentados novos fatores > primos a P que vai acumular fatores primos. > > PASSO 9: Se P < M vá para o PASSO 6 > > Esse passo determina um looping para acumular fatores em P. > > PASSO 10: Se MDC(P, N) for diferente de 1 vá para o PASSO 14 > > Se MDC(P, N) for diferente de 1 ele pode ser um fator primo de N. Resta > verificar se ele não é o próprio N. Isso vai ser feito no PASSO 14. > > PASSO 11: P = Resto da divisão de P por N > > Esse passo é para trabalharmos com números menores. > > PASSO 12: Se P < 4 faça P=4 > > Talvez esse passo possa ser omitido > > PASSO 13: vá para o PASSO 6 > > PASSO 14: Se MDC(P, N)=N vá para o PASSO 4 > > Se MDC(P, N) = N não foram encontrados fatores primos e algoritmo recomeça > do ponto apropriado. > > PASSO 15: MDC(P, N) é fator (primo) de N > > FIM > > Eu fui menção honrosa na Olimpíada Ibero-americana de Matemática > Universitária em 2006. Acho que este meu trabalho merece ser avaliado. > > > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
