Uma tentativa de implementação do
algoritmo de primalidade "AKS"Trabalho do curso de Segurança de Dados 1/02
Pablo Santos, Raul Xavier Neto e Thelmo Enoque *
Departamento de Ciência da Computação
Universidade de Brasília
Setembro de 2002
Nota do Editor
Três cientistas da computação surpreenderam a comunidade de matemáticos ao descobrirem um algoritmo determinístico para testar se um número inteiro é primo ou composto (múltiplo de números distintos de si e da unidade), que dizem exibir custo computacional mensurável por uma função polinomial em relação ao tamanho da representação do número. Ou seja, um algoritmo determinístico polinomial para teste de primalidade. Trata-se de um problema que dura séculos, e a surpresa maior da descoberta está na aparente simplicidade do algoritmo. Aparente, mas, até onde? Estaria correta a análise de complexidade do algoritmo feita por seus descobridores, atribuindo-lhe custo polinomial de grau doze?Estas são as questões a que se dedicaram, como trabalho final do curso de Segurança de Dados 1/02 da UnB, os autores deste artigo, surpreendidos que foram, também, pela notícia da descoberta a menos de um mes do final do curso. Eles se debruçaram sobre o artigo onde os descobridores do algoritmo, Manindra Agrawal e seus alunos ainda não formados, Neeraj Kayal e Nitin Saxtena, do Departamento de Ciência da Computação e Engenharia do Instituto Indiano de Tecnologia em Kanpur, divulgaram a descoberta, em busca de respostas.
A importância deste trabalho, neste curso, se deve ao fato dos números primos terem se tornado vitais para a segurança computacional nos dias de hoje, devido à importância da criptografia assimétrica para os mecanismos de proteção ao acesso, transmissão e integridade de dados em uma rede digital aberta, como é a Internet, conjugado ao fato dos números primos estarem no centro inercial da teoria que dá suporte à criptografia assimétrica. Os algoritmos usados atualmente para testar primalidade de números inteiros, na escala de tamanho de números usados em criptografia, são rápidos, mas são probabilísticos.
Esses algoritmos probabilísticos apenas fornecem a probabilidade de um número ser primo, sendo zero se o número for sabidamente composto, e próximo de um em caso contrário. Apesar da probabilidade do número ser primo poder ser tão próxima da certeza quanto se queira, estes algoritmos não apresentam uma prova de primalidade. Além disso, existe um certo tipo de número composto que falseará esses testes para qualquer medida de proximidade de certeza que se escolha: são os números de Carmichael. Não obstante os números de Carmichael existirem em quantidade infinita, eles não atrapalham a prática de se produzir chaves nas implementações de criptografia assimétrica baseada nos números primos.
Especialistas suspeitavam que um algoritmo determinístico de tempo polinomial fosse possível. Mas não previam a simplicidade da solução em 13 linhas que Agrawal e seus alunos apresentaram. Assim que foi divulgado o artigo relatando a descoberta, ele e o algoritmo nele descrito e analisado passaram a ser analisados por vários cientistas em todo o mundo. Carl Pomerance, dos Laboratórios Bell da Lucent, em Nova Jersey, por exemplo, acredita que a existência da prova deixará os criptologistas preocupados. "Se há um teste simples para saber se um número é primo, também pode haver uma forma simples de determinar os fatores primos que estamos atualmente investigando". Ele fala da posição de autoridade máxima em Teoria dos Números que se lhe reputa. Quanto a este artigo, é uma singela contribuição inicial do Departamento de Ciência da Computação da UnB neste sentido.
Muito antes de começarem a usar números primos para aplicações criptográficas os matemáticos já estavam preocupados em achar um algoritmo eficiente para testar a primalidade de um número. Breve Histórico
O crivo de Erastótenes foi o primeiro algoritmo a funcionar com todos os primos e foi concebido por volta de 240aC, no entanto a sua complexidade é exponencial. No século XVII Fermat provou o conhecido “pequeno teorema de Fermat” que garante que qualquer número primo p e qualquer inteiro a, não divisível por p, a^(p-1)º 1 mod p.
Depois que a primalidade se tornou importante para a criptografia, na década de 70 com o uso de exponenciação modular, apareceram vários algoritmos de teste, a maioria deles probabilísticos.Os testes probabilísticos são bastante eficientes, porém não dão certeza da primalidade do número. É aí que o algoritmo proposto por Agrawal, Kayal e Saxena pode ser decisivo, pois dará certeza da primalidade com complexidade polinomial.
Objetivos
Estudar e implementar o algoritmo para teste de primalidade de números proposto no paper “Primes is in P” submetido por Manindra Agrawal, Neeraj Kayal e Nitin Saxena (www.cse.iitk.ac.in/primality.pdf). Uma vez implementado o algoritmo, comparar o tempo necessário para sua execução com o tempo de algoritmos como o Crivo de Eratóstenes e o algoritmo de Montecarlo para avaliar o custo/benefício a fim de utiliza-lo para aplicações de criptografia.
Desenvolvimento
O algoritmo Agrawal Kayal Saxena não é trivial. O empreendimento de implementá-lo também não. Por isso foram realizadas algumas consultas com professores do departamento de Matemática. À medida que o trabalho prosseguia ganhávamos mais dúvidas do que respostas.
A primeira dúvida veio logo na primeira linha do algoritmo, onde devemos testar se o número n fornecido como entrada é da forma a^b (com b > 1) com complexidade de ordem O(log3 n).
Consultamos o professor Lineu Neto que fez algumas sugestões de pesquisa e logo em seguida com o professor Nigel Pitt que “matou a charada” com um laço de iteração na variável b que verifica se o exp(log(n)/b) é um número inteiro. O limite superior do laço é log(n)/log(2).
Depois, fomos conversar com o professor Salahodim Shokranian para esclarecermos alguns pontos e notações que não estávamos familiarizados na álgebra envolvida para a compreensão do algoritmo.Ainda restavam muitas dúvidas de implementação. Precisávamos de mais familiaridade com a computação algébrica para ganhar produtividade efetiva. Fosse outra a natureza do problema já teríamos uma idéia bem mais clara da solução.A décima segunda linha do algoritmo foi o maior desafio (todo o resto era trivial nas três linguagens utilizadas C++, Hugs e Maple). Primeiro por que não tínhamos disponível nenhuma ferramenta ou biblioteca que implementasse congruência polinomial. O grande problema na implementação do algoritmo foi entender e tornar computável a incongruência do passo 12.Procuramos, então, o professor Maurício Ayala. Essa foi sem dúvida a entrevista mais proveitosa. O referido professor pretende publicar um detalhamento do algoritmo para os próximos meses e além de interessado possui familiaridade com a álgebra computacional.
Ele apontou alguns erros em nosso método de trabalho e ressaltou com ênfase que é preciso concentrar todos os esforços inicialmente em entender o paper. Segundo o professor Ayala o artigo Primality and identity testing via chinese remaindering [2] é essencial para o entendimento e implementação do AKS. Infelizmente, não tivemos acesso ao paper.
Outra observação do professor é que o algoritmo conforme foi publicado é apenas um esboço (essa opinião parece ser corroborada pelas listas de discussão na internet). E que é preciso utilizar diversas técnicas avançadas de programação para garantir que a complexidade O(log(n)^12) seja atingida.
Implementações
Em um primeiro tempo, tentamos implementar o algoritmo Agrawal-Kayal-Saxena (AKS) em C/C++ com a biblioteca Miracl (ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip), "Multiprecision Integer and Rational Arithmetic C/c++ Library", para números estendidos. A biblioteca Miracl, entretanto, no tratamento de operações sobre polinômios só permite expoentes inteiros convencionais. O algoritmo AKS pede polinômios com expoentes muito grandes e seria-nos necessário escrever uma extensão para o tratamento de operações sobre polinômios com expoentes do tipo big (inteiro estendido). Um dos criadores/colaboradores da Miracl, Mike Scott (mscott@indigo.ie), implementou a incongruência do passo 12 (o código está na pasta source da biblioteca sob o nome de TP.CPP), porém, não ficou claro o laço de iteração de a e r tem que ser inteiro comum, portanto não poderíamos testar para números muito grandes.