Constructing finite field extensions with large order elements

ABSTRACT

In this paper, we present an algorithm that given a fixed prime power q and a positive integer N, finds an integer n ∈ [N, 2qN] and an element α ∈ Fqn of order greater than 2^n/logqⁿ, in time polynomial on N. Our result is inspired by the recent AKS primality testing algorithm [1] and the subsequent improvements [3, 4, 2].

REFERENCES

• 1: M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. http://www.cse.iitk.ac.in/news/primality.pdf, 2002.
• 2: D. J. Bernstein. Proving primality in essentially quartic random time. http://cr.yp.to/papers/quartic.pdf, 2003.
• 3: Pedro Berrizbeitia. Sharpening "primes is in p" for a large family of numbers. http://lanl.arxiv.org/abs/math.NT/0211334, 2002.
• 4: Qi Cheng. Primality proving via one round in ECPP and one iteration in AKS. In Dan Boneh, editor, Proc. of the 23rd Annual International Cryptology Conference, volume 2729 of Lecture Notes in Computer Science, Santa Barbara, 2003. Springer-Verlag.
• 5: Shuhong Gao. Elements of provable high orders infinite fields. Proc. American Mathematical Society, 127:1615--1623, 1999.
• 6: J. von zur Gathen and Igor Shparlinski. Gauss periods infinite fields. In Proc. 5th Conference of Finite Fields and their Applications, pages 162--177. Springer-Verlag, 1999.