# Agrawal: A Polynomial Time Algorithm for Testing Primality

The primality testing algorithm we present is based upon the following identity: is prime if and only if

where we consider this congruence as an identity in the polynomial ring . This easily gives a randomized algorithm which runs in polynomial time: rather than verifying it completely (which would be far too expensive), you verify it modulo a randomly chosen degree polynomial ; repeating this sufficiently often, you expect to witness a failure of this congruence to hold fairly quickly if is composite.

Conjecture. To prove that is prime, it is enough to let run over the set

We were unable to prove this conjecture, but, instead the modified conjecture, which is then a proposition:

Proposition. [Modified conjecture] To prove that is prime, it is enough to let run over the set

except when has a small' prime factor ( ).

Remark. One can replace the assumption that does not have a small prime factor by adding to the list the polynomials .

For a fixed , this gives only that is a prime power, which is a condition readily checked.

We now prove the modified conjecture.

If is prime, clearly all of these conditions will hold.

Assume that is composite and does not have a small' prime factor. Assume that

for every . First, observe that is not a prime power. This follows as

so substituting for everywhere we get

and substituting for we get

hence

so for all .

Suppose for a prime. Then ( does not have a small prime divisor) so as the group is cyclic. Therefore for all . A simple counting argument (look at all of the possible numbers whose prime divisors are all smaller than , the identity holds for them but there are more than of them) shows that this cannot happen.

Assume that is composite but not a prime power. Let , prime, and fix . Now:

Claim. We have

for if and only if

for .

This can be seen by replacing by as appropriate.

Definition. A number is introspective for if

Both and are introspective for , . Indeed, a prime is trivially introspective for every polynomial.

Observe that if and are introspective for , then so is . This is clear as

Secondly, observe trivially that if is introspective for and , then it is for .

Now let and

Observe that every is introspective for every .

Let be the order of the group generated by and in . There are elements in less than or equal to .

Furthermore, there are distinct polynomials of degree which are distinct modulo and , where is an irreducible factor of the th cyclotomic polynomial in . We show this as follows.

The number of polynomials in of degree is at least by simply considering products of distinct linear factors in . Assume that and . (We will come back to this: we can choose the value of to obtain it.) Then

and

Let , and let be of degree in and . Suppose . Then

for all . Therefore is a root in of the polynomial . This is a contradiction, as each of the elements are distinct (they are roots of unity in the field) for the representatives of the group generated by and , but the degree of is .

Let , and ; this is possible as is the order of the group generated by and in . Let be of degree . Then

so is a root in of the polynomial . Since was an arbitrary element of , each is a root of this polynomial with degree but there are more than of them, contradiction.

Finally, we show that and . Suppose the order of is in . Then . Now use the fact that the least common multiple of the first numbers is at least .

It is easy to see that this algorithm has runtime .

Back to the main index for Future directions in algorithmic number theory.