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.