Input: Integer n > 1;

if (n has the form ab with b > 1) then output COMPOSITE

r := 2
while (r < n) {
	if (gcd(n,r) is not 1) then output COMPOSITE
	if (r is prime greater than 2) then {let q be the largest factor of r-1 
	if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then 
	break
	}
	r := r+1
}

for a = 1 to 2sqrt(r)log n {
	if ( (x-a)p is not (xp-a) (mod xr-1,p)) then output COMPOSITE
}
output PRIME;