Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Elements of provable high orders in finite fields

Author: Shuhong Gao
Journal: Proc. Amer. Math. Soc. 127 (1999), 1615-1623
MSC (1991): Primary 11T55; Secondary 11Y16, 68Q25, 11T06, 12Y05
Published electronically: February 11, 1999
MathSciNet review: 1487368
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A method is given for constructing elements in ${\mathbb F}_{q^n}$ whose orders are larger than any polynomial in $n$ when $n$ becomes large. As a by-product a theorem on multiplicative independence of compositions of polynomials is proved.

References [Enhancements On Off] (What's this?)

  • 1. L.M. ADLEMAN AND K.S. MCCURLEY, ``Open problems in number theorectic complexity, II,'' in Proc. 1994 Algorithmic Number Theory Symposium, LNCS 877, Springer-Verlag, 1994, 291-322. MR 95m:11142
  • 2. E. BACH, ``Comments on search procedures for primitive roots,'' Math. Comp. 66 (1997), 1719-1727. MR 98a:11187
  • 3. S. GAO, ``Gauss periods, groups, and normal bases,'' preprint, 1997.
  • 4. S. GAO AND H.W. LENSTRA, JR., ``Optimal normal bases,'' Designs, Codes and Cryptography 2 (1992), 315-323. MR 93j:12003
  • 5. S. GAO AND S. VANSTONE, ``On orders of optimal normal basis generators,'' Math. Comp. 64 (1995), 1227-1233.
  • 6. S. GAO, J. VON ZUR GATHEN AND D. PANARIO, ``Gauss periods and fast exponentiation in finite fields,'' extended abstract in Lecture Notes in Computer Science, vol. 911, Springer-Verlag, 1995, 311-322.
  • 7. S. GAO, J. VON ZUR GATHEN AND D. PANARIO, ``Gauss periods: orders and cryptographical applications,'' Math. Comp. 67 (1998), 343-352. MR 98c:11134
  • 8. J. VON ZUR GATHEN AND I. SHPARLINSKI, ``Orders of Gauss periods in finite fields,'' Proc. 6th International Symposium on Algorithms and Computation, Cairns, LNCS 1004, 1995, 208-215. MR 97b:11153
  • 9. R. LIDL AND H. NIEDERREITER, Finite Fields, Addison-Wesley, Reading, MA, 1983. (Now distributed by Cambridge University Press.)
  • 10. A.J. MENEZES (ED.), I.F. BLAKE, X. GAO, R.C. MULLIN, S.A. VANSTONE AND T. YAGHOOBIAN, Applications of Finite Fields, Kluwer, 1993.
  • 11. R.C. MULLIN, I.M. ONYSZCHUK, S.A. VANSTONE AND R.M. WILSON, ``Optimal normal bases in $GF(p^n)$,'' Discrete Applied Math. 22 (1988/1989), 149-161. MR 90c:11092
  • 12. V. SHOUP, ``Searching for primitive roots in finite fields,'' Math. Comp. 58 (1992), 369-380. MR 92e:11140
  • 13. I. SHPARLINSKI ``On primitive elements in finite fields and on elliptic curves,'' Matem. Sbornik 181 (1990), no. 9, 1196-1206. (in Russian) MR 91m:11108
  • 14. D. WAN ``Generators and irreducible polynomials over finite fields,'' Math. Comp. 66 (1997), 1195-1212. MR 97j:11060
  • 15. Y. WANG, ``On the least primitive root of a prime,'' Scientia Sinica 10 (1961), 1-14. MR 24:A702

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 11T55, 11Y16, 68Q25, 11T06, 12Y05

Retrieve articles in all journals with MSC (1991): 11T55, 11Y16, 68Q25, 11T06, 12Y05

Additional Information

Shuhong Gao
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-1907

Keywords: Finite fields, primitive elements, elements of provable high orders, compositions of polynomials
Received by editor(s): September 16, 1997
Published electronically: February 11, 1999
Communicated by: David E. Rohrlich
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society