Algoritmos Matemáticos para calcular números primos - algoritmo AKS

O algoritmo AKS

No teste de Monte Carlo, se testarmos todas as possibilidades de r, poderemos afirmar se um número é primo. No entanto, isso é inviável para p grande. Logo, se fosse possível achar um sub-conjunto de valores para r quando aplicados ao teste nos fornecesse uma resposta certa, então teríamos um teste determinístico em P. É isso que faz o algoritmo AKS.

Input: Integer n > 1

1. if (n = ab with b > 1) then output COMPOSITE;

2. r := 2;

3. while (r < n) {

4. if (gcd(n,r) is not 1) then output COMPOSITE;

5. if (r is prime greater than 2) then {

6. let q be the largest factor of r-1;

7. if (q > 4sqrt(r)log n) and not(n(r-1)/q 1 (mod r)) then

8. break;

9. r := r + 1;

10. }

11. for a := 1 to 2sqrt(r)log n {

12. if not( (x-a)n (xn-a) (mod xr-1,n) ) then output COMPOSITE;

13. }

14. output PRIME;

As linhas de 1 a 10 funcionam como um filtro para descartar muitos valores que não influem na decisão de primalidade, dados certos princípios algébrico já conhecido.

Na primeira linha, é necessário aplicar um algoritmo que detecte potências perfeitas em tempo polinomial.

A linha 4, verifica se o máximo divisor comum de dois inteiros n e r é diferente de 1.

Note que se n for primo, mdc(n, r) = 1 para qualquer r < n. Já na linha 5, é preciso determinar se o número r é primo por força bruta (todos os valores até sua raiz quadrada), pois se for usado algum algoritmo probabilístico (comum nas linguagens matemáticas como Maple e Matlab), então estaremos tornando o AKS também probabilístico.

A linha 6 determina o maior fator primo de r-1 (q) sendo r primo.

Na linha 12, vemos a aplicação do Pequeno Teorema de Fermat. Considere C(n, p) = n! / p!(n-p)!, n primo diferente de 2 e a co-primo de n. Então, temos que:

(x-a)n = - C(n,0)x0an + C(n,1)x1an-1 + ... - C(n,n-1)xn-1a1 + C(n,n)xna0 =

= -an + C(n,1)x1an-1 + ... - C(n,n-1)xn-1a1 + xn

Como C(n, i) 0 (mod n) (divisível por n) para i [1, n-1], temos em módulo n que:

(x - a)n -an + xn (xn - an) (xn - a) (mod n)

Já se n for composto, então ele terá um fator primo q. Considere qk a maior potência de q que divide n (n = rqk). Então, temos que o binômio de xi quando i = qk:

C(n, i) = n!/i!(n-i)! = (qkr)!/qk!(qkr-qk)! =

= (qkr)(qkr-1)!/(qk)(qk-1)!(qkr-qk)! = (r)(qkr-1)!/(qk-1)!(qkn-1)!

E este binômio não é divisível por n=rqk (igual a zero módulo n) e, por isso, n é composto. Isto é facilmente verificável dividindo-se os binômios de uma linha n do Triângulo de Pascal por n e constatando que todos são divisíveis se e somente se n é primo.

0: 1

1: 1 1

2: 1 2 1

3: 1 3 3 1

4: 1 4 6 4 1

5: 1 5 10 10 5 1

6: 1 6 15 20 15 6 1

7: 1 7 21 35 35 21 7 1

8: 1 8 28 56 70 56 28 8 1

9: 1 9 36 84 126 126 84 36 9 1

10:1 10 45 120 210 252 210 120 45 10 1

Os binômios da linha n são divisíveis por n quando este é primo.

O problema desta abordagem é que quando n for muito grande, calcular todos os n-1 binômios o pior caso, C(n, n-1)0 (mod n) será muito custoso. Alterando a congruência para módulo xr-1, implicitamente, faz-se o teste apenas para os r últimos termos de (x - a)n, ou seja, i [n-r, n-1].

No entanto, agora, alguns compostos n podem equivocadamente satisfazer a congruência da linha 12 para alguns valores de (a, r) e, por isso, são testados separadamente na linha 2.

O algoritmo primeiro escolhe um r primo para obter q, o maior fator primo de r-1, tal que este r delimita um intervalo onde certamente haverá um fator primo de n se este for composto.

Em seguida, o algoritmo testa a congruência para a [1, 2r1/2log(n)], uma quantidade de testes realizáveis em tempo polinomial no pior caso. Este é justamente o avanço feito por este algoritmo.