Number Theory & Cryptography - Assignement 2 - Question 1: Implement Rabin-Miller algorithm for Primality Testing. - Done with Aviral - November 9, 2011

rabinmiller.gp

/* Question 1: Implement Rabin-Miller algorithm for Primality Testing. */

/*
   Input: n>3, an odd number, k for accuracy
   Output: 'composite' or 'possibly prime'
*/
rabinmiller(n, k) = {
	d = n - 1;
	s = 0;
	while( (d%2 == 0),
		d = d / 2;
		s = s + 1;
	);
	while( ( k>0 ),
		k--;
		a = random( n-3 ) + 2;
		x = Mod( a^d, n );
		if( ( (x==1) || (x==n-1) ),
			next(1);
		);
		r = 1;
		while( (r <= s-1),
			r++;
			x = Mod(x^2, n);
			if((x==1),
				print("Composite!");
				return(0);
			);
			if((x==n-1),
				next(2);
			);
		);
		print("Composite!");
		return(0);
	);
	print("Probably prime!");
	return(0);
}