Elements of provable high orders in finite fields

Gao, Shuhong

doi:10.1090/S0002-9939-99-04795-4

Elements of provable high orders in finite fields
HTML articles powered by AMS MathViewer

by Shuhong Gao PDF

Proc. Amer. Math. Soc. 127 (1999), 1615-1623 Request permission

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

Leonard M. Adleman and Kevin S. McCurley, Open problems in number-theoretic complexity. II, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 291–322. MR 1322733, DOI 10.1007/3-540-58691-1_{7}0
Eric Bach, Comments on search procedures for primitive roots, Math. Comp. 66 (1997), no. 220, 1719–1727. MR 1433261, DOI 10.1090/S0025-5718-97-00890-9
S. Gao, “Gauss periods, groups, and normal bases,” preprint, 1997.
Shuhong Gao and Hendrik W. Lenstra Jr., Optimal normal bases, Des. Codes Cryptogr. 2 (1992), no. 4, 315–323. MR 1194773, DOI 10.1007/BF00125200
S. Gao and S. Vanstone, “On orders of optimal normal basis generators,” Math. Comp. 64 (1995), 1227–1233.
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.
Shuhong Gao, Joachim von zur Gathen, and Daniel Panario, Gauss periods: orders and cryptographical applications, Math. Comp. 67 (1998), no. 221, 343–352. With microfiche supplement. MR 1458221, DOI 10.1090/S0025-5718-98-00935-1
Joachim von zur Gathen and Igor Shparlinski, Orders of Gauss periods in finite fields, Algorithms and computations (Cairns, 1995) Lecture Notes in Comput. Sci., vol. 1004, Springer, Berlin, 1995, pp. 208–215. MR 1400245, DOI 10.1007/BFb0015425
R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, 1983. (Now distributed by Cambridge University Press.)
A.J. Menezes (Ed.), I.F. Blake, X. Gao, R.C. Mullin, S.A. Vanstone and T. Yaghoobian, Applications of Finite Fields, Kluwer, 1993.
R. C. Mullin, I. M. Onyszchuk, S. A. Vanstone, and R. M. Wilson, Optimal normal bases in $\textrm {GF}(p^n)$, Discrete Appl. Math. 22 (1988/89), no. 2, 149–161. MR 978054, DOI 10.1016/0166-218X(88)90090-X
Victor Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), no. 197, 369–380. MR 1106981, DOI 10.1090/S0025-5718-1992-1106981-9
I. E. Shparlinskiĭ, On primitive elements in finite fields and on elliptic curves, Mat. Sb. 181 (1990), no. 9, 1196–1206 (Russian); English transl., Math. USSR-Sb. 71 (1992), no. 1, 41–50. MR 1085150, DOI 10.1070/SM1992v071n01ABEH001389
Daqing Wan, Generators and irreducible polynomials over finite fields, Math. Comp. 66 (1997), no. 219, 1195–1212. MR 1401947, DOI 10.1090/S0025-5718-97-00835-1
Yuan Wang, On the least primitive root of a prime, Sci. Sinica 10 (1961), 1–14. MR 130848