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

**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
*

**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

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

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

Now let and

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

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

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.