Mathematics of Computation

Author(s): Shuhong Gao; Joachim von zur Gathen; Daniel Panario.
Journal: Math. Comp. 67 (1998), 343-352.
MSC (1991): Primary 11T30, 94A60; Secondary 11Y16, 12Y05, 68Q25
Supplement: Additional information related to this article.
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: Experimental results on the multiplicative orders of Gauss periods in finite fields are presented. These results indicate that Gauss periods have high order and are often primitive (self-dual) normal elements in finite fields. It is shown that Gauss periods can be exponentiated in quadratic time. An application is an efficient pseudorandom bit generator.

1.: L.M. Adleman and H.W. Lenstra, Jr., Finding irreducible polynomials over finite fields, Proc. 18th Annual ACM Symp. on Theory of Computing (1986), 350-355.
2.: G.B. Agnew, R.C. Mullin, I.M. Onyszchuk and S.A. Vanstone, An implementation for a fast public key cryptosystem, J. of Cryptology, 3 (1991), 63-79. MR 92b:94034
3.: G.B. Agnew, R.C. Mullin and S.A. Vanstone, An implementation of elliptic curve cryptosystems over $F_{2^{155}}$ , IEEE J. on Selected Areas in Communications, 11 (1993), 804-813.
4.: T. Beth, Efficient zero-knowledge identification scheme for smart cards, Advances in Cryptology (Proc. Eurocrypt `88), Springer LNCS 330 (1988), 77-84. CMP 21:11
5.: I.F. Blake, S. Gao and R. Lambert, Constructive problems for irreducible polynomials over finite fields, in Information Theory and Applications (A. Gulliver and N. Secord, eds), Springer LNCS 793 (1994), 1-23. MR 95c:94007
6.: M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudorandom bits, SIAM J. Computing, 13 (1984), 850-864. MR 86a:68021
7.: J. Brillhart, D.H. Lehmer, J.L. Selfridge, B. Tuckerman and S.S. Wagstaff, Factorizations of $b^n\pm 1$ , Up to High Powers, Contemporary Mathematics, 22, 2nd ed., AMS, 1988. MR 90d:11009
8.: W. Diffie and M.E. Hellman, New directions in cryptography, IEEE Trans. Info. Th., 22 (1976), 644-654. MR 55:10141
9.: T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Info. Th., 31 (1985), 469-472. MR 86j:94045
10.: S. Gao, J. von zur Gathen and D. Panario, Gauss periods, primitive normal bases, and fast exponentiation in finite fields, preliminary version in Proc. Latin'95, Valparaíso, Chile, Springer LNCS 911 (1995), 311-322; full version in Technical Report 296/95, Department of Computer Science, University of Toronto, 1995.
11.: S. Gao and D. Panario, Tests and constructions of irreducible polynomials over finite fields, in Foundations of Computational Mathematics, F. Cucker and M. Shub (Eds.), Springer Verlag, 1997, 346-361.
12.: S. Gao and S.A. Vanstone, On orders of optimal normal basis generators, Math. Comp., 64 (1995), 1227-1233. MR 95j:11117
13.: J. von zur Gathen and F. Pappalardi, Density estimates related to Gauss periods, 1996, preprint.
14.: J. von zur Gathen and I.E. Shparlinski, Orders of Gauss periods in finite fields, in Proc ISAAC '95, Springer LNCS 1004 (1995), 208-215. MR 97b:11153
15.: C.F. Gauss, Disquisitiones Arithmeticae, Braunschweig, 1801. English Edition, Springer-Verlag, 1986. MR 87f:01105
16.: T. Hansen and G.L. Mullen, Primitive polynomials over finite fields, Math. Comp., 59 (1992), 639-643. MR 93a:11101
17.: D. Jungnickel, Finite Fields: Structure and Arithmetics, Bibliographisches Institut, Mannheim, 1993. MR 94g:11109
18.: L. Lamport, Password authentication with insecure communication, Comm. ACM, 24 (1981), 770-772.
19.: C.H. Lim and P.J. Lee, Another method for attaining security against adaptively chosen ciphertext attacks, Advances in Cryptology (Proc. Crypto '93), Springer LNCS 773 (1994), 420-434.
20.: D.L. Long and A. Wigderson, The discrete logarithm hides $O(\log n)$ bits, SIAM J. Computing, 17 (1988), 363-372. MR 89e:68026
21.: A.J. Menezes, I.F. Blake, X.H. Gao, R.C. Mullin, S.A. Vanstone, and T. Yaghoobian, Applications of Finite Fields, Kluwer Academic Publishers, 1993.
22.: I.H. Morgan and G.L. Mullen, Primitive normal polynomials over finite fields, Math. Comp., 63 (1994), 759-765. MR 95a:11106
23.: R.C. Mullin, I.M. Onyszchuk, S.A. Vanstone and R.M. Wilson, Optimal normal bases in , Discrete Applied Math., 22 (1988/1989), 149-161. MR 90c:11092
24.: National Institute for Standard and Technology, Federal Information Processing Standard for Digital Signature Standard (DSS), FIPS 186, May 1994.
25.: R. Peralta, Simultaneous security of bits in the discrete log, Advances in Cryptology (Proc. Eurocrypt `85), Springer LNCS 219 (1986), 62-72. CMP 18:16
26.: C.P. Schnorr, Efficient identification and signatures for smart cards, Advances in Cryptology (Proc. Crypto '89), Springer LNCS 435 (1990), 239-252. MR 92e:94024
27.: C.P. Schnorr, Efficient signature generation by smart cards, J. of Cryptology, 4 (1991), 161-174.
28.: V. Shoup, Exponentiation in using fewer polynomial multiplications, preprint, 1994.
29.: A. Wassermann, Konstruktion von Normalbasen, Bayreuther Mathematische Schriften, 31 (1990), 155-164. MR 91h:11145
30.: A. Wassermann, Zur Arithmetik in endlichen Körpern, Bayreuther Mathematische Schriften, 44 (1993), 147-251. MR 94g:11114
31.: Y. Zheng and J. Seberry, Practical approaches for attaining security against adaptively chosen ciphertext attacks, Advances in Cryptology (Proc. Crypto '92), Springer LNCS 740 (1993), 292-304.
32.: Y. Zheng and J. Seberry, Immunizing public key cryptosystems against chosen ciphertext attacks, IEEE J. on Selected Areas in Communications, 11 (1993), 715-724.
33.: N. Zierler and J. Brillhart, On primitive trinomials (mod 2), Information and Control, 13 (1968), 541-554. MR 38:5750
34.: N. Zierler and J. Brillhart, On primitive trinomials (mod 2), II, Information and Control, 14 (1969), 566-569. MR 39:5521
35.: M. \v{Z}ivkovi\'{c}, A table of primitive binary polynomials, Math. Comp., 62 (1994a), 385-386. MR 94d:11099
36.: M. \v{Z}ivkovi\'{c}, Table of primitive binary polynomials, II, Math. Comp., 63 (1994b), 301-306. MR 94i:11099

Shuhong Gao
Affiliation: Department of Mathematical Sciences Clemson University Clemson, SC 29634-1907, USA
Email: sgao@math.clemson.edu

Joachim von zur Gathen
Affiliation: Fachbereich Mathematik-Informatik Universität-GH Paderborn D-33095 Paderborn, Germany
Email: gathen@uni-paderborn.de

Daniel Panario
Affiliation: Department of Computer Science University of Toronto Toronto, Ontario M5S 1A4, Canada
Email: daniel@cs.toronto.edu

DOI: 10.1090/S0025-5718-98-00935-1
PII: S 0025-5718(98)00935-1
Keywords: Finite fields, primitive elements, normal bases, cryptography, pseudorandom bit generators
Received by editor(s): February 16, 1996
Additional Notes: This paper is in final form, no version of it will be submitted for publication elsewhere.
Copyright of article: Copyright 1998, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS