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
In fact, we replace by ; the proof remains essentially unchanged. Instead of considering congruences, we instead think of equalities in the ring
Definition. A pseudofield is a pair where is a ring (commutative with ) and such that there exists and satisfying:
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.
Theorem. Let be a pseudofield of characteristic and degree such that , has no prime factor , and such that
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
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:
Back to the
main index
for Future directions in algorithmic number theory.