\\ Pedro Patricio
\\ Maio de 2007

\\ O Algoritmo probabilistico de primalidade de Solovay-Strassen

\\ sintaxe: solovay(numero,nbases)


solovay(numero,nbases=1)=
{
	local(i,primo);

	i=1;
	primo=1;
	
	/*salvaguarda do caso em que numero e' par */
	if(numero==2, print("2 e' primo"), /*else*/
	if(numero%2==0, print(numero" e' garantidamente composto"),

	/*aqui comeca a parte nao trivial*/

	while(i<=nbases && primo,
		b=random(numero-1)+1;
		if(Mod(b,numero)^((numero-1)/2)!=Mod(kronecker(b,numero),numero),
			print(numero" e' garantidamente composto; testemunha: "b);
			primo=0;		
		);
	i++);
	if(primo==1,
		print(numero" e' provavelmente primo");
	,/*else*/
		primo=0);
	return(primo);

	); /* fim dos if's do inicio */
	);
}