Alguns programas usando a biblioteca gmp

Isto deve convencer ao leitor que nunca iremos muito longe enquanto não nos livrarmos de limites tão baixos sobre tamanhos de inteiros. Uma idéia seria usar uma biblioteca para inteiros de precisão arbitrária, como gmp (GNU MultiPrecision, cujas fontes podem ser obtidas em www.gnu.org) ou giantint (fontes em ..). Uma explicação de como funcionam estas bibliotecas está fora dos nossos objetivos; o leitor interessado deve consultar sua documentação. Basta-nos notar que elas permitem usar um tipo de variável novo, chamado mpz_t no gmp e giant no giantint, que funciona como um inteiro (e não um elemento de ${\mathbb{Z} }/(N)$ para algum valor fixo de N) sem limitações de tamanho exceto as impostas pela memória do computador. Note que para testar se M_p é primo pelo critério de Lucas-Lehmer, teremos que fazer comtas modulo M_p; um número módulo M_p ocupa p bits de memória e, levando em conta que talvez precisemos guardar alguns resultados intermediários, podemos estimar que a memória necessária se p é aproximadamente igual a 10 milhões deve ser de uns 10 MBytes, o que não é muito para os padrões atuais. Note por outro lado que se tentássemos calcular S_p-2(e não S_p-2 modulo M_p) isto excederia em muito a memória de qualquer computador.

Vejamos um programa simples que implementa o teste de Lucas-Lehmer usando a biblioteca gmp.

Bem, este programa finalmente funciona! Ele verifica corretamente se M_p é primo ou composto mesmo para valores altos de p. Por exemplo, testamos com ele a primalidade de M₁₁₂₁₃usando um Pentium 166-Linux, e a resposta certa veio após pouco menos de 6 minutos. Mas se é verdade que este programa está correto, ele pode ser tornado bem mais rápido. As contas no computador são feitas na base 2 mas a redução módulo M_p é feita sem levar em conta o fato de que M_p tem uma expansão na base 2 tão simples. O programa ll4.c é uma pequena modificação do anterior que explora estes fatos. Aproveitamos a ocasião para modificar o programa de tal forma que ele teste não apenas a primalidade de um número de Mersenne e sim de todos os números de Mersenne em uma faixa dada.

A principal diferença está na parte em que reduzimos módulo M_p: é muito fácil fazer uma divisão com resto de um inteiro n por 2^p, pois o resto n₁ corresponde aos últimos p algarismos na base 2 enquanto o quociente n₂ corresponde aos demais algarismos. Como $2^p \equiv 1 \pmod M_p$, podemos trocar $n = 2^p \cdot n_1 + n_2$por n₁ + n₂ sem alterar seu valor módulo M_p e sem sequer calcular o próprio M_p. Esta nova versão do programa demorou aproximadamente 1 minuto e 40 segundos para verificar a primalidade de M₁₁₂₁₃, 1 hora para verificar a primalidade de M₄₄₄₉₇ e 7 horas para testar todos os expoentes primos até 12000.

Um pequeno programa capaz de encontrar números primos relativamente grandes é nosso exemplo proth1.c, que usa o critério de Proth (Corolário 3.9) para procurar primos da forma $h \cdot 2^k + 1$; o programa encontra primos com centenas de algarismos em poucos segundos. Yves Gallot escreveu um programa sério para encontrar primos muito grandes deste tipo ^4.1.

Chegamos no ponto onde já temos programas que funcionam e devemos discutir como torná-los mais rápidos. Voltando ao exemplo do teste de Lucas-Lehmer, a parte que fica fora do for é claramente bem simples. Tudo o que vem dentro do for, por outro lado, é executado p vezes e portanto é com esta parte que devemos nos preocupar: uma multiplicação (ou um quadrado), algumas adições, subtrações e divisões por 2^p. Já vimos que as divisões por 2^p são simples; adições e subtrações são também rápidas, mesmo usando o método ensinado na escola. Resta a multiplicação, e é aí que nosso programa gasta quase todo seu tempo. Discutiremos no restante deste capítulo como multiplicar rapidamente inteiros com muitos algarismos.