http://www.cic.unb.br/~rezende/sd.htm > Algoritmos: Primalidade determinística

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.


Breve Histórico

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.
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.
 
A plataforma Maple (http://www.maplesoft.com/), um software específico para aplicações matemáticas, nos possibilitou implementar todos os passos anterirores à linha 12 com facilidade. Entretanto as operações entre polinômios no Maple também são bastante complexas e de toda forma a solução da incongruência da linha 12 continua a eludir os implementadores.
Uma tentativa de implementar o algoritmo com o uso da linguagem Hugs (http://haskell.cs.yale.edu/hugs/), uma linguagem funcional para inteligência artificial especialmente apropriada para tratamento de problemas matemáticos também obteve um certo grau de sucesso. O Hugs trata todo número como uma lista de dígitos e foi originalmente implementado para tratar com números arbitrariamente grandes, o que facilitou em muito a implementação de certos trechos do algoritmo. Novamente foi o tratamento de operações sobre polinômios que dificultou a implementação completa do algoritmo. A linguagem não oferece diretamente estruturas para tratar operações sobre esse tipo de dados. Após um longo período de deliberação, foi possível imaginar um método para o tratamento destes, mas o sistema era lento e altamente experimental, sendo que não refletiria corretamente o tempo do algoritmo AKS a menos de ser otimizado. A otimização do tratamento de operações sobre polinômios em Hugs exigiria um tempo suplementar e poderia representar um outro projeto por si só.




Código da implementação em Maple:

restart;

#função que checa se n = a^b

NisAb := proc(n)

local b, ret, lim;

ret:=false;

lim:= trunc(evalf((log(n))/log(2)));

for b from 2 to lim while (not ret) do

if type(eval(exp(log(n)/b)),integer) then 

if type(eval(root(n,b)),integer) then ret := true end if;

fi;

od;

return(ret);

end:

#passo2

# retorna 0 se n não é primo, r=n se n é primo, r<n se não sabe dizer

# se n é primo ou não.

passo2 := proc(n)

local r,q;

for r from 2 while r < n and r<>0 do

if (evalb(gcd(n,r)<>1)) thenr:=0; break; end if;

# isprime é uma função que checa primalidade probabilisticamente

# utilizada aqui por motivos de testes, pois essa impolementação 

# de AKS está incompleta.

if (isprime(r)) then

if(r=2) then q:=1 else q:=ifactors(r-1)[-1][-1][1]; end if;

if (q >= evalf(4*sqrt(r)*(log[2](n)))) and (evalf((n^((r-1)/q))mod(r))<>1) then break; end if;

fi;

od:

return(r);

end:

>

#Implementação da conjectura final

incongruencia := proc(r,n)

local a, lim, congruente;

congruente:=true;

lim:=trunc(evalf(2*sqrt(r)*log[2](n)));

for a from 1 to lim while congruente do

#testa incongruencia

od:

return(congruente);

end:

#Implementação do algoritmo de AKS semi-completo 

# (faltando o teste de incongruência)

AKSisPrime := proc(n)

local eprimo, r;

eprimo:=true;

if (n<2) then print("N deve ser maior que 1!"); eprimo:=false; end if;

if eprimo and evalb(NisAb(n)) then eprimo:=false; end if;

if eprimo then r:=passo2(n); end if;

if (r=0) then eprimo:=false;

elif (r < n) then eprimo:=evalb(incongruencia(r,n));

end if;

return(eprimo);

end:

>


Código implementação em Hugs:

module Primality where

primos n = pri [2..n]

pri (p:ps) = p:pri[x|x<-ps, mod x p /= 0]

pri [] = []

fat 1 = 1

fat (n+1) = (n+1) * (fat n)

-- o Problema é que SQRT não tá definido pra Integer, daí, tem q trazer de Integer pra Num

-- poranto, basta acrescentar o fromInteger e fica: sqrt (fromInteger(n))

sieveList n = primos (floor (sqrt (fromInteger(n))))

largestPrime n = findLargest n (reverse (sieveList n))

findLargest n (x:xs)

| (n `mod` x) ==0 = x

| otherwise = findLargest n xs

findLargest _ [] = 1

-- Daqui em diante eh a funcao principal

primeIsInP n

| (n > 1) = posPrime n

| otherwise = 2 /= 2 -- False

posPrime n

| (formN n) = 2 /= 2 -- False

| otherwise = (findR 2 n)

-- checar para b de 2 a logN/log2, se e^(logN/b) é inteiro, se for, testar se n=a^b.

formN::(Integer->Bool)

formN n = formBN 2 n

formBN::(Integer->Integer->Bool)

formBN b n

| (exp ((log (fromInteger(n))) / (fromInteger(b))) == fromInteger(floor ((exp ((log (fromInteger(n))) / (fromInteger(b))))))) = 2 == 2 -- True

| ((fromInteger(b)) < ((log (fromInteger(n))) / (log 2))) = (formBN (b+1) n)

| otherwise = 2 /= 2 -- False

findR r n

| (r == (n-1)) = forA 1 r n -- True

| (gcd n r) /= 1 = 1==2 --False

| (test1 && test2) = forA 1 r n

| otherwise = findR (r+1) n

where

q = largestPrime (r-1)

test1 = (mq >= (4 * (sqrt mr) * (logBase 2 mn)))

test2 = ((n ^ (floor((mr-1)/mq)) `mod` r) /=1)

mq = fromInteger(q)

mn = fromInteger(n)

mr = fromInteger(r)

-- último passo do algoritmo, checar a incongruencia (x-a)^n /= (x^n-a) mod (x^r-1,n)

forA::(Integer->Integer->Integer->Bool)

forA a r n

| (a > floor(lim)) = 2==2 --True

| (ehIncongruente a r n) = 1==2--False

| otherwise = forA (a+1) r n

where

lim = (2 * (sqrt mr) * (logBase 2 mn))

mr = fromInteger(r)

mn = fromInteger(n)

-- Como não conseguimos implementar a incongruencia, assumimos verdadeiro para saber quais números

-- chegam até esse passo do algoritmo, sendo possíveis primos até aqui

ehIncongruente a r n = 1==2 --False

-- teste de primalidade usando fatoração prima com crivo

primdiv n

| (largestPrime n) == 1 = 2==2

| otherwise = 1==2


Conclusão

O trabalho pode ser feito, porém é necessário ter acesso ao paper citado (Primality and identity testing via chinese remaindering [2]) para poder compreender melhor as idéias por trás do algoritmo. Ainda sim, para garantir que o algoritmo terá a complexidade calculada por Agrawal-Kayal-Saxena seria necessária uma pesquisa mais extensa de cada parte do algoritmo, bem como o acompanhamento e orientação de um professor interessado no algoritmo, talvez algum projeto de um semestre.

Bibliografia

[1]- Agrawal, M., Kayal, N. & Saxena, N: Prime is in P, internal publication of the Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India, August 6, 2002.

[2]- Agrawal & Biswas: Primality and identity testing via chinese remaindering, in Proceedings of Annual IEEE Simposium on Foundations of Computer Science, 1999

* Pablo L. R. Santos, Raul Xavier Neto e Thelmo Enoque, Bacharelandos em Ciência da Computação da Universidade de Brasília, alunos da disciplina Segurança dos Dados em 1/02