Elias Granja Jr.

No último post sobre números primos, citei uma forma que ainda utiliza fatoração, que não é uma maneira rápida de se descobrir se um número é ou não primo, apesar das várias formas de “pular” alguns números.

Como voltei a ler o livro Algoritmos do Dasgupta, Sanjoy et al. achei mais uma forma de se fazer isso pulando a parte chata da fatoração.
Essa formula se baseia no fato que para todo número primo p e todo a, 1<= a < p tem a seguinte afirmação como verdade:

a^( p – 1 ) mod p = 1 mod p

Dessa forma pode-se evitar a fatoração que é algo absurdamente lento. Em python ficaria da seguinte forma:

def primo( num ):
	if( 2**(num-1) % num == 1 % num):
		print "primo"
	else:
		print "nao primo"

O problema do teorema é que ele não afirma que “se e somente se” a igualdade for verdadeira teremos um número primo, ou seja, poderia haver números compostos que passariam no teste. E existem.  Os números de Carmichael passam no teste e por isso, de acordo com a wikipedia, eles também são chamados de pseudoprimos. Porém eles são raros e dependendo de tão grande é o primo que você necessita, como na criptografia RSA, vale a pena o risco de se usar um pseudoprimo ao invés de fatorar um número gigantesco.

Além disso, existem casos em que o valor de a também deixaria a igualdade verdadeira para números compostos, Sanjoy afirma que metade dos valores possíveis de a fazem isso se desconsiderarmos os números de Carmichael.

Uma forma de se evitar falsos positivos é testar o número com diferentes e aleatórios valores para a. Quanto mais testes, menor é a probabilidade de erro. Testar 100 valores para a faria com que seja mais fácil um raio cósmico queimar o computador do que obter um falso positivo, brinca Sanjoy.