Como dito, não existe grande dificuldade em se escrever um programa para fatorar N. Mesmos os menos otimizados encontrariam o resultado mais cedo ou mais tarde. Talvez a maior dificuldade neste sentido seria o de ter uma linguagem que conseguisse trabalhar com números inteiros de qualquer tamanho, sendo que o python já tem isto. Os maiores desafios foram o cálculo do D e a decifragem da mensagem. Outros desafiados chegaram mais rápido do que eu nos valores de P e Q, mas não conseguiram, a tempo, algoritmos para o D e a mensagem.

Descobrindo a chave privada D

Essa parte não foi difícil, visto que eu estava programando em Python. Na parte anterior, obteve-se o P e o Q, fatores primos da chave pública. Para se descobrir a chave privada, usa-se um pequeno algorítimo, baseado no algorítimo de Euclides. Este programa é uma completa reimplementação do programa fornecido pelo Prof. Elgio em Algoritmo de euclides estendido.

Porém, propositadamente, o programa do prof. foi escrito em C, que, sabe-se, é bastante limitado no tratamento de números grandes, comportando números de, no máximo 32 bits (ou 64, dependendo da sua arquitetura), o que não ajuda muito com a ordem de tamanho de números que estamos trabalhando. Já Python não possui limitação alguma quanto ao tamanho dos números, dando suporte nativo a números de qualquer tamanho (posteriormente foi publicado um artigo ensinando como lidar com números de qualquer tamanho em C. O mesmo pode ser conferido em Programação com números inteiros gigantes). Esse realmente foi um diferencial que me ajudou muito. Segue o código do algorítimo de Euclides estendido em python.


Este programa foi o que, inicialmente, me deu uma grande vantagem em relação aos outros participantes, por ser razoavelmente complexa sua implementação em C. Aqui não houve criatividade alguma, sendo esse programa uma cópia quase exata do fornecido pelo professor Elgio, porém, em python, o que o expande a números gigantes.

Decifrando as mensagens

Eis aqui o problema que, creio eu, mais deu dor de cabeça aos outros participantes. Bem, pelo menos deu a mim, até que conseguisse resolvê-lo. Para fazer a descriptografia das mensagens é necessário elevar um número enorme a outro maior ainda, e depois tirar o módulo por um número grande também.

Mesmo para computadores potentes, essas operações se tornam inviáveis, pois elas fazem a potência do número, e depois tiram o módulo. Mas não nos importa saber a potência, apenas o módulo. E essa operação é bem mais fácil de ser realizada, com a técnica correta. O algorítimo que eu implementei é, na realidade, uma técnica bem parecida com a que professor Elgio descreveu, após o término do desafio, em Cálculo da potência modular de forma eficiente:


Então, vamos lá. Note que o operador d >> 1 divide d por 2 (por isso da potência dois lá em baixo no (r**2)) e arredonda o valor para baixo, porque vai decrescendo o d até 1 (e até 0, se continuar, por isso d > 1). O operador d & 1 é um simples operador lógico, que, neste caso, retorna 1 se o número for ímpar, e 0 se o número for par.

Isso, como você pode imaginar, faz com que a lista l tenha, arredondado pra baixo, log₂(d) elementos, sendo 0 os que foram tirados quando d era par e 1 quando d era impar. Esses serão os restos da divisão que serão apropriadamente compensados na próxima função.

Após isto, a função l.pop() vai retirando o próximo valor (FILO, first in, last out) da lista l, retornando-o a v e deletando-o da lista. Esse valor, que, lembro, é 0 ou 1, eleva a, e o multiplica ao quadrado de r, calculado previamente, antes das alterações das variáveis. Se 0, o valor é multiplicado por 1, resultando nele mesmo, e tirado o modulo por n, se 1, o a multiplica a potência, fazendo o papel do resto das divisões anteriores por 2, e então, novamente, tirado o módulo por n.

Quando l se esgotar, o laço termina, e a função retorna o valor final de r, que, por sempre estar sendo tirado o módulo por n, retornará o mesmo valor da potência final.

Matematicamente, os restos parciais da divisão do número d, elevado quantas vezes necessário aos fatores 2 de n, e tirado o resto novamente, retorna o próprio número. Na prática, é algo como: o resto de uma potência por um número n é igual ao resto por n do resto desse número também por n elevado ao expoente que se queira.