AKS teste de primalidade

Evolução
Por ter alto custo e executar em tempo polinomial, muitos pesquisadores motivaram-se em diminuir ainda mais a complexidade do AKS original [22]. Na primeira melhoria, Lenstra propõe uma mudança ao calcular o valor de r, de tal forma que, de O(log6n), o algoritmo passa a ser O(log5n). Esse valor de r é mais fácil de ser calculado, pois não é necessário saber se r é primo e nem conhecer a fatoração prima de r-1. Abaixo, o algoritmo com a melhoria:

No passo dois é necessário o calculo de or(n), feito em tempo O(log7n), O(log2n) + O(log5n), pelo algoritmo:

O passo sete do algoritmo não é alterado, porém o valor de r por ele usado é menor, diminuindo o número de iterações. Isso faz o algoritmo ter custo final O(log7,5n). A segunda melhoria, proposta por Lenstra em conjunto com Pomerance, consiste em substituir o polinômio ( xr – 1), usado no passo 12 do algoritmo original, por outro cuidadosamente escolhido. O calculo de r é substituído pelas etapas que definem o polinômio a ser utilizado, o que faz o processo ter custo menor que o proposto até então. Ao final, obtemos um custo de O(log6n). A melhoria proposta por Berrizbeitia, assim como a Lenstra-Pomerance, altera o polinômio do passo 12 do algoritmo original, porém depende de algumas configurações de entrada para funcionar:

A melhoria realizada pelo algoritmo consiste em trocar a equação (x+a)n = xn + a (mod xr -1, n) por (mx + 1)n = mxn + 1(mod x2^s – a, n). Nesta equação, s = 2 log log n e m varia de 1 a 2max(s-k,0), em que k é a maior potência de 2 que pode dividir n – 1 ou n + 1. O custo desse algoritmo é maior que o de Lenstra-Pomerance, porém, se satisfeitas as exigências para o valor de n, o custo chega a O(log4n).

Materiais e Métodos

-Técnicas
A paralelização de algoritmos sequenciais é feita de forma simples usando a API OpenMP, pois ao acrescentar poucas linhas de código (diretivas de