\\ Pedro Patricio
\\ verifica se n passa o teste de Miller de base 2
\\ 

/* a escrita de n-1=(2^s)t */


decomp(n)=
{	local(s,t);
	
	n=n-1; \\ queremos n-1=(2^s)*t
	s=1; t=n\2;
	while( t%2!=1,
		s++;
		t=t\2
	);
	return([s,t])
}

/* o teste de Miller base 2 */

Miller2(n)=
{	local(primo,s,t,j);

	primo=false;
	s=decomp(n)[1];
	t=decomp(n)[2];
	if(Mod(2^t,n)==Mod(1,n), 
		primo=true,
	\\else	
		j=0;
		while(Mod(2^(2^j*t),n)!=Mod(-1,n) & j<s,
			j++);
		if(j<s, primo=true)
	\\fim-else
	);
	return(primo)
}