Input: integer n > 1
if n is of the form a**b, b > 1
    output COMPOSITE;
r = 2;
while r < n
    if gcd(n,r) <> 1
       output COMPOSITE;
    if r is prime
       let q be the largest prime factor of r-1;
       if (q >= 4 sqr(r) log n)
          and (n**((r-1)/q) is not congruent
             to 1 mod r)
          break;
    r = r + 1;
for a = 1 to 2 sqr(r) log n
    if ((x-a)**n is not congruent
       to (x**n-a) (mod x**r-1, n))
          output COMPOSITE;
output PRIME;

Example 1: Modified deterministic polynomial-time algorithm.