Para quem se interessa por algoritmos de teste de primalidade:
http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
Esse é o famoso artigo de Manindra Agrawal, Neeraj Kayal e Nitin Saxena (AKS).
O que impressiona é que até a descoberta desse algoritmo, não se conhecia nenhum algoritmo que fosse ao mesmo tempo polinomial e funcionasse em todos os casos (i.e. para números inteiros quaisquer). Os algoritmos anteriormente conhecidos ou eram exponenciais ou só funcionavam para alguns números com propriedades específicas (e havia aqueles que respondiam probabilisticamente).
Segundo entendi, a complexidade do AKS é de cerca de O(log^12( n )). Uma modificação recente conseguiu melhor para O(log^6( n )).
Fórum