AQUECIMENTO desafio RSA [RESOLVIDO]

Legal...

Então não estou tão ruim assim...

Fiz um em shell script somente com duas otimizações e consegui chegar em 63 segundos num Pentium D 3.0 Ghz..

Vou tentar otimizar mais e ver o quanto consigo melhorar em shell script... depois é só passar pra C...

Só como curiosidade... Você pode passar o tamanho aproximado do número do desafio?

[]s

Cloves Jr

Serão vários N, não apenas um.

Cada um em um grau de dificuldade maior.

Os primeiros serão ridículos, dentro ainda do espaço de 32-40 bits.

O último está lá pelos 70 bits de tamanho.

1) Eu ia limpar este tópico removendo as mensagens de aquecimento quando o desafio entrasse no ar. Desisti. Ao invés disto, irei iniciar o desafio em um tópico novo, anunciado aqui. Lembrando, dois dias após a publicação do artigo

2) CONFIRMADO. Depois do PRIMEIRO desafio, valendo 500 pontos, irei lançar um OUTRO, mais difícil, valendo UM LIVRO, que enviarei para qualquer parte do Brasil. Para fazer justiça ao assunto do tópico, que é a Criptografia, o livro será "o Livro dos Códigos" de Simon.

Assim quem ganhar o desafio dos 500 pontos já estará um passo a frente para ganhar o livro, POREM, como parte das regras exige a publicação do código, todos que lerem terão quase as mesmas chances, pois poderão apenas usar o código já publicado.

Infleizmente terei que manter a restrição de participação dos meus alunos. Eles estudaram isto e alguns até viram meu código com minhas otimizações. Sairiam com uma imensa vantagem.

SERÁ MUITO LEGAL!

Com certeza a escolha da linguagem é parte significante.

Faz tempo que quero migrar um artigo interno meu sobre isto para o VOL, mas ainda não o fiz porque a Linguagem C perdeu para o PHP e isto eu não aceito!

Preciso melhorar o código em C para que ele VENÇA o PHP, ora bolas!
http://gravatai.ulbra.tche.br/~elgio/disciplinas/?MAT=VOL&ARQNOME=080508-tempoLing.html&DISC...

(Se ficar quebrado o link acima, acesse http://gravatai.ulbra.tche.br/~elgio/disciplinas/ coloque VOL como matrícula e selecione a disciplina "Coisas que publico para o mundo". Vira uma lista de assuntos, Escolha o primeiro "Comparação de desempenho de linguagens")

O problema é que até agora só fiz algoritmos. Programação começo esse semestre. No máximo que posso fazer é algo em portugol e testar em pascal. Mas acho que vai ser meio complicado achar o resultado ehehehehehe

Boa sorte para quem tentar.

To fritando meu processador do jeito que implementei o código...hauhauha

100% de cpu, hauhaa isso porque eu estou usando o menor número que você passou, hauha

vou melhorar o algoritmo aqui =P

[]'s

Bom testei com N = 144

deu certo haha, mas o problema é quando coloco um valor N gigante!

hauahauha

é não deu certo,

quando eu coloco um número muito grande "166306807" ele me mostra vários número que multiplicados se resulta em N, porém após algum tempo de execução o programa começa aparecer valores "loucos" para P e Q, haha

mas com N = 144 deu certo =P

hauhauah

[]'s

Artigo acaba de ser publicado no HOME do Vol.

Significa que na SEXTA FEIRA os valores de N do desafio serão postados
http://www.vivaolinux.com.br/artigo/Criptografia-assimetrica-com-o-RSA/

@Elgio

Uma dúvida, como deve ser o resultado do programa, apenas mostrar 1 resultado?
pois do jeito que eu fiz aparece vários resultados de P e Q,

ou eu estou fazendo errado =P

Como N foi gerado a partir de dois números primos, P e Q, somente existem DOIS divisores, ou seja, apenas UM P e um Q.

Contudo, caso tenha havido um erro na geração das chaves (P e Q não eram primos), não importa. Ao achar UM P e um Q, qualquer que seja, quebrou-se o algoritmo.

Veja um exemplo.

Tenho um N MUITO GRANDE:
N = 1308881339770618216278492249627915044337069338458164167832695

Este N foi gerado pelos números P e Q também grandes:
P = 1214031856739561104303265096777
Q = 1078127672271951424306891641535

Achar estes valore de P e Q levaria DIAS mesmo com a melhor ferramenta.

Contudo, houve um grande equívoco na escolha, pois Q não é primo.
Ao se executa a ferramenta para encontrar P e Q, ela em MICROSSEGUNDOS acha a resposta:

p = 5
q = 261776267954123643255698449925583008867413867691632833566539

GRANDE VACILO, pois o N gigantão divide por 5. Paciência, a "grande" chave N acaba de ser quebrada. Jogando estes valores no teorema de euclides ele retornará sim um valor d que pode ser usado para reverter a criptografia.

Portanto o programa de vocês acaba quando encontrar UM DIVISOR, seja qual for (ou outro não precisa ser buscado, né. Bata fazer N/P para achar o Q).

Uma dica importante: sempre testem se os valores fecham. Os programas podem estar bugados e gerarem valores absurdos de P e Q. Ao achar ou pensar ter achado um valor de P e Q, façam um:

echo "P * Q"|bc

E vejam se isto resulta mesmo no N publicado.

Vou tentar também. Já estudei sobre o assunto, faz uns 2 anos. Na época não mexi com nenhum tipo de implementação. Essa é a chance.