# Lenstra: Primality Testing with Pseudofields

This is joint work with Carl Pomerance.

If are real-valued functions on a set and , then we say if there exists such that for all , .

Theorem. There is a deterministic algorithm that given , , correctly decides whether or not is prime and that has runtime .

The theorem of AKS begins (in brief) as follows. Let be a positive integer, a prime number with , and

for a small set of , and the multiplicative order of modulo is at least . Together with other conditions, we conclude is a prime. This has runtime . For , we get with effective constant. For an ineffective constant, one can get . It would be optimal to have , which would require but here we run into Artin's conjecture on primes with prescribed primitive root. To get around this, we generalize the situation slightly to give more parameters.

In fact, we replace by ; the proof remains essentially unchanged. Instead of considering congruences, we instead think of equalities in the ring

This is a Galois extension of of degree . We now replace the polynomial with other polynomials for which the same proof techniques apply. In this case, is a field if and only if is a prime number and is a primitive root modulo . We are led to introduce rings that `try very hard' to be fields.

Definition. A pseudofield is a pair where is a ring (commutative with ) and such that there exists and satisfying:

• is a subring of with , and there exists with:
• ;
• for all prime, ; and
• ;
• Equivalently, as a ring with for some monic polynomial of degree satisfying:
• ;
• ; and
• for all primes , .

Also equivalently, a pseudofield is characterized by the conditions that be Galois with cyclic group generated by , generates as a ring, and .

Theorem. There is a deterministic algorithm that given and decides if is a pseudofield in time

It is routine to verify this using the second set of conditions.

Example.

1. If is a prime with , then is a pseudofield if and only if the order of modulo is .
2. If is prime, then is a pseudofield if and only if is a field and .
3. If (so that ) and , then is a pseudofield if and only if --in other words, is a pseudoprime to base .

Theorem. Let be a pseudofield of characteristic and degree such that , has no prime factor , and such that

for . Then is a power of a prime number.

The proof uses: for each prime , there exists a unique such that for all , . This is a result coming from Galois theory for rings.

This leads to a deterministic primality test with runtime equal to the time to construct the pseudofield plus the time to check the conditions; the latter takes time .

In the context of primality testing, there is a procedure which converts any (honest) method for constructing finite fields to a method for checking primality. If the algorithm on input crashes, then was not prime; if it returns a polynomial , then one checks (efficiently) if this gives rise to a pseudofield, which then verifies that is prime, and otherwise produces a proof that is not prime.

Therefore we look for algorithms for constructing finite fields. Our construction relies on the following theorem:

Theorem. [Kummer 1846] For prime and , put

where is a primitive th root of unity in . The polynomial is monic and irreducible of degree . If is prime, , then is irreducible if and only if the order of modulo is equal to .

Fact. Let be a pseudofield of characteristic and degree for such that ; then is a pseudofield of characteristic and degree .

Theorem. There exists an effective computable constant such that there is a deterministic algorithm that given finds a finite sequence of pairs such that:

• , pairwise coprime;
• prime, ;
• The order of modulo is ; and
• satisfies

and .
This algorithm runs in time , with an effective constant.

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