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.

Um clássico problema de programação é o calculo para descobrir números primos de forma rápida e precisa. Por isso, decidi fazer no meu tempo ocioso uma função em python que retorne se um número é ou não primo.
Usei o teorema que diz que todo o número não primo é divisivel por outro menor ou igual a sua raiz quadrada e o resultado foi o seguinte:

import math
def primo(a):
	for i in xrange(2,int(math.sqrt(a)+1)):
		if(a%i==0):
			print("%d nao e primo" % a)
			return 0
	print("%d e primo" % a)
	return 1