E cá estamos nós, a parte mais demorada do desafio consiste na criação de um programa que teste todas as possibilidades de divisão para os números N a fim de se obter seus fatores P e Q. Facilmente já se pode perceber uma otimização fraca, mas que já diminui o esforço pela metade. O primeiro impulso poderia ser construir um programa que tentasse dividir N por 2, depois por 3, 4, 5. No entanto os múltiplos de 2 não precisam ser testados. A rigor, testando-se apenas a divisibilidade do número por 2 é suficiente para todos os pares, mas, claro, qual é o sentido em se fazer uma chave par? Por esse motivo, os testes podem ser feitos apenas nos ímpares, começando em 3.

Esta parte do desafio não exige grande habilidade, programas complexos ou raciocínio lógico. O problema dos divisores de um número é extremamente clássico, sendo um dos primeiros exercícios aos aprendizes de qualquer linguagem de programação. Um programa simples em python para resolver este problema, e minha primeira versão da resolução deste exercício, que funcionou satisfatoriamente bem para as primeiras e mais simples chaves:


Note que este programa era, inicialmente, um programa apenas de verificação de primos. Importante ressaltar, para alguns, que, na fatoração de um número qualquer, basta que se testem as possibilidades de 2 à raiz quadrada daquele número, já que, matematicamente, se um número tiver divisores (não for primo) ao menos um deles será, certamente, menor ou igual que a raiz do mesmo.

Este programa me ajudou muito, principalmente na quebra das primeiras chaves, as mais fracas (com divisores pequenos), mas logo se mostrou insuficiente ao trabalhar com chaves maiores. A principal limitação dele, como da maior parte dos programas inicialmente feitos pra isso, é a de ser single-thread. Isso quer dizer que, mesmo com processadores relativamente potentes, com mais de um núcleo, ele fica limitado a apenas um, não usufruindo nem de metade da potência computacional da máquina. A segunda versão do programa, e que incluiu os últimos recursos importantes, obrigou-me a aprender multi-threading em python para implementação no programa. Sempre gostei de python, mas nunca tinha me aprofundado a esse ponto, até por falta de necessidade pra isso. Segue o programa final:



Este programa, sim, poderia tirar o máximo do computador, dentro da limitação do python por ser uma linguagem interpretada. Mas esta ainda não foi a versão utilizada para se vencer o desafio. Esta é a versão correta do programa, que divide o trabalho em partes iguais, no número de núcleos do computador, e executa os testes em cada parte, de ímpar em ímpar.

Após a dica 3 do Elgio, que infelizmente não deduzi de início, de que era muito mais provável que as chaves estivessem mais próximas da raiz do número do que do começo, o que evitaria um trabalho enorme, um programa mais informal, adaptado ao meu computador com 2 núcleos, foi criado com base nesse anterior, para que fizesse a busca na mesma faixa de números nos dois núcleos simultaneamente, mas decrementando em 4, ao invés de dois. Sendo assim, um dos núcleos processaria os números 13, 9 e 5 (num exemplo onde 13 seria a raiz de N), enquanto o outro faria 11, 7 e 3:



Graças a este programa e à última dica do Elgio, pude vencer o desafio, sendo que nunca conseguiria terminar o processamento da última chave a tempo (poderia levar dias).