(VENCIDO) *** GANHE UM LIVRO aqui no Vol (Desafio RSA 2) [RESOLVIDO]

Quebrar os N exige esforço de CPU, mas o D e as mensagens exige APENAS UM PROGRAMA CORRETO! O cálculo é IMEDIADO para D e MSG com o programa certo.

André já fez o seu que calcula o D.
Por isto está DISPARADO na frente com 506 pontos ao quebrar, agora a pouco, o P4/Q4 e D4.

Cloves mandou n7 e n8
Otacílio entrou na jogada. Enviou N1,D1,MSG1,N2,D2,MSG2,M3,D3,MSG3,N4,D4,N5,D5,N6/D6

André Vitor também achou uma maneira de quebrar a msg e EMPATOU com Carlos Ferreira.

André Vitor e Otacílio com 1226 pontos.
Ambos faltando APENAS N7 e N8 para vencer.

Enquanto isto, Carlos Ferreira mandou N7 e N8 e depois D2, D3, D4, D5, D6, D7 e D8, somando 1526 pontos.

SITUAÇÃO as 9:30 de 14/Ago. Carlos ganhando. Só falta ele descobrir MSG2 e MSG3.

Otaício e André Vitor em segundo, só faltando N7,D7,N8,D8 para ambos.

As 9:40 temos a seguinte situação:

Carlos Ferreira: quebrou todos os N, mas ainda faltam os D e MSG (só quebrou o D1 e MSG1). Falta ele programar o código para achar D e MSG

Otacílio e André: ambos já tem código para calcular o D e o MSG. Estão pendurados pela quebra do N7 e N8. Questão de tempo.

FINAL DO DESAFIO A QUALQUER MOMENTO

Andre quebrou N7/D7

Quebra do N.

É provável que P e Q estejam muito mais perto de raiz quadrada de N do que de 0.

Assim, ao invés de começar o laço em 3, indo de 2 em 2, ganha-se MUITO, começando o laço em raiz quadrada de N, deixando ele IMPAR e voltando de 2 em 2.

N=221.
Começando em 3, testa-se 3,5,7,9,11,13 (ACHOU. Seis passos).

Raiz de 221 = 14 (só parte inteira). 14 é par, então começa-se em 15: 15, 13 (ACHOU). Dois passos.

E se tem vários cores ou vários processadores:

Core 1: de raiz(N), dec 4
Core 2: de raiz(N)+2, dec 4

Exemplo:

N =221, raiz = 14 -> 15
Core 1: 15, 11, 7, ...
Core 2: 17, 13, 9, ...

Código:
Início = ImparMaior(Raiz(N)) + (ID*2)
DEC = (NCORES*2)

ID deve ser o identificador da máquina/core. 0 para o proc/core 0, 1 para o proc/core 1, etc

NCORES eh quantas maquinas/cores tem: 2 de for uma dual core.

Caracas...

Os caras não estão pra brincadeira... Meu problema é que surgiu um monte de coisas pra fazer aqui na empresa e não vou conseguir terminar o desafio a tempo...

Vou ver se consigo finalizar mesmo assim o código para depois postar no forum...

[]s

Cloves Jr

André Vitor enviou todas as respostas vencendo assim o desafio.

PARABÉNS ao André.
Pelos emails que recebi vi que foi mais do que merecido, pois teve muito trabalho.

Segue o programa que criei para descobrir a chave. Dei uma melhorada nele, coisas que queria fazer antes mas não tinha tempo, mas em suma, nada de novo além do que usei. Notem o uso da lib processing, não inclusa nas instalações padrões python ainda, mas facilmente instalada via easy_install. Como o VOL num tava respeitando minhas identações (axo que não sei algo que deveria saber =), resolvi postar no meu google sites (inoperante, só pra funcionalidades msm).
http://sites.google.com/site/andrevitorfilerepository/Home/rsa04_p_q.py

Estou postando também o link pro meu Google Sites do algorítimo Euclides Extendido, que é uma recodificação em python do programa do prof. Elgio. É o mesmo programa, apenas algumas adaptações pra linguagem, mas a sintaxe e algorítimos são os mesmos. A vantagem é que, como é feito em python, tem suporte nativo a números gigantes, sem ter que recorrer a alguns artifícios em outras linguagens para resolver o problema.
http://sites.google.com/site/andrevitorfilerepository/Home/euclides_ext.py

Segue a função que usei para calcular as potencias modulares de forma mais rápida. Ninguém merece elevar números dakele tamanho à outros de tamanhos equivalentes. Essa função usa alguns conceitos de restos da divisão de potencias, algebra. Algumas fontes são a internet e o livro Majorando IME, que tem uns conceitos muito legais tambem. Como ainda não aprendi a fazer o VOL respeitar minhas indentações, vou colocar um ~ no começo da linha para cada identação dakela linha.

def potencia(c, d, n):
~ r = c % n
~ l = []
~
~ while d > 1:
~~ l.append(d & 1)
~~ d = d >> 1
~ while l:
~~ v = l.pop()
~~ r = ((a ** v) * r ** 2) % n
~ return r

Eu fiz um programinha em python para descobrir o P e o Q e consequentemente QQ. Mas estou com dificuldades para calcular o quociente de Euler... é difícil de calcular na força bruta, e não sei calcular matematicamente...