Constructing finite field extensions with large order elements
Qi Cheng

Abstract

increase the density of the sequence of n so that In this paper, we present an algorithm that given a the high order element problem can be eventually fixed prime power q and a positive integer N , finds solved. von zur Gathen and Igor Shparlinski [6] an integer n  [N , 2q N ] and an element   Fqn has obtained the following result: of order greater than 2n/ logq n , in time polynomial Proposition 1.1. Let q be a fixed prime power. on N . Our result is inspired by the recent AKS For any positive integer N , an integer n  N with primality testing algorithm [1] and the subsequent n = O(N log N ) and an element   Fqn of order improvements [3, 4, 2]. 1/2 2(2n) -2 can be computed in time polynomial on N. 1 Intro duction An important open problem in computational number theory is to construct a multiplicative generator for a given finite field. Although there are plenty of generators in a finite field, finding one is notoriously difficult, since we do not know how to test whether an element is a generator or not without computing integer factorization or discrete logarithm. In practice, small characteristic fields are particularly useful. In this context, one can ask a relevant but less restrictive question: for a fixed prime power q , can we find an element in Fqn with large order in time polynomial on n? Besides the apparent connection to the generator problem, the problem is interesting in its own regard [6]. However, it does not seem easier if we require the order to be c greater than q n for a constant c. A partial solution was given in [5], which presented a polynomial time algorithm producing an element with order at least nlogq n . Another relevant question asks to find a number n greater than a given number N , and c an element of order q n in Fqn for some constant c. The rationale of this question, which we call the special finite field high order element problem, is to deal with special finite fields first, and then try to
 Scho ol of Computer Science, the University of Oklahoma, Norman, OK 73019, USA. Email: qcheng@cs.ou.edu. This research is partially supp orted by NSF Career Award CCR0237845

All the above results are based on the properties of Gauss Periods. For a survey, see [6]. 2 Our results

A novel technique in the celebrated AKS primality testing algorithm and its subsequent improvements is to use low degree polynomials to obtain a large multiplicative subgroup modulo an integer and a polynomial. In this paper, we apply this idea to obtain a new solution to the special finite field high order element problem. Our result, which can be summarized in the following theorem, features a denser sequence of n and a much higher order. Theorem any N we an integer with order 2.1. Let q be a fixed prime power. For can compute in time polynomial on N n  [N , 2q N ] and an element   Fqn greater than 2n/ logq n .

It is based on the following result. Theorem 2.2. Let r be a prime power. Let xr-1 - g , g  Fr , be an irreducible polynomial over Fr and  be one of its roots in the extension field Frr-1 . Then for any a  F ,  + a has order greater than 2r - 1 . 2r -  r Note that rr+11 2 when r > 3. r +1 Proof. W.l.o.g., suppose that Frr-1 = Fr [x]/(xr-1 - g ), and  = x (mod xr-1 - g ).

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

1130


Denote the order of  + a by s. Then  + a is one of the roots of X s = 1. We want to estimate the number of roots of this equation. For any c  F , r c + a is one of the roots as well, since c + a is a conjugate of  + a over Fr . Let c1 , c2 , · · · , cr-1 be a list of all the elements in F . If (e1 , e2 , · · · , er-1 ) r and (e1 , e2 , · · · , er-1 ) are t1 o different sequences w of 1 onnegative integers, n ir-1 ei < r - 1 and i < r - 1, then due to the unique ir -1 e factorization over Fr [x] we have 1 (ci  + a)ei
ir -1

contradicts the assumption that g is a generator of F . r Now we are ready to describe the algorithm. Let q be a fixed prime power. The input of the algorithm is a positive integer N > 0. 1. Find the smallest positive integer t such that t(q t - 1)  N . Let n = t(q t - 1); 2. Find a generator in Fqt , denote it by g ; 3. Solve the equation xq be one of the roots;
t -1

- g = 0 in Fqn , let 

= = =

1 1 1

cei i
ir -1

1 1

( +
ir -1

a ei ) ci a ei ) ci

4. Output  + 1 ( or  + a for any a  Ft ). q From Step 1, we see that N  n  2q N . Step 2 and 3 altogether take time (q t )O(1) = N O(1) . Hence the algorithm takes time N O(1) . Applying Theorem 2.2 with r = q t  n/ logq n, the order of the output element is greater than 2n/ logq n . Acknowledgment: We thank Mr Yu-Hsin Li for helpful discussions. References

ci
ir -1

ei

( +
ir -1
i

(ci  + a)e .
ir -1

Now consider the subset of Frr-1 : 1 1 S={ (ci  + a)ei | ei < r - 1}.
ir -1 ir -1

All of the elements in S are roots of = 1. Thus s  |S |. The cardinality 1of S is the number of nonnegative solutions of ir -1 ei < r -1, which 2r - 1 . is r+1 Does there exist an irreducible polynomial of form xr-1 - g over Fr ? The following lemma answers the question. Lemma 2.1. The polynomial xr-1 - g is an irreducible polynomial over Fr if g is a generator of F . r Proof. Let  be a root of xr-1 - g over some extension of Fr . Denote [Fr () : Fr ] by d. We have [Fr (a) : Fr ] = d for any a  F , and a is also r a root of xr-1 - g . This implies that xr-1 - g can be factored into irreducible polynomials of degree d over Fq , and d|r - 1. Take the factor f (x) satisfying f () = 0. Assume f (x) is monic, and the constant coefficient of f (x) is m. The roots of f (x) have form d-1 , a1 , · · · , ad-1 . We have m = ( i=1 ai )d . So r -1 dm1 d =  F , and (d ) d = g . This - r
(
i=1

Xs

[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 in finite fields. Proc. American Mathematical Society, 127:1615­1623, 1999. [6] J. von zur Gathen and Igor Shparlinski. Gauss periods in finite fields. In Proc. 5th Conference of Finite Fields and their Applications, pages 162­ 177. Springer-Verlag, 1999.

ai )

1131