Gauss periods: orders and cryptographical applications

Gao, Shuhong; von zur Gathen, Joachim; Panario, Daniel

doi:10.1090/S0025-5718-98-00935-1

Gauss periods: orders and cryptographical applications
HTML articles powered by AMS MathViewer

by Shuhong Gao, Joachim von zur Gathen and Daniel Panario PDF

Math. Comp. 67 (1998), 343-352 Request permission

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.

References

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.
G. B. Agnew, R. C. Mullin, I. M. Onyszchuk, and S. A. Vanstone, An implementation for a fast public-key cryptosystem, J. Cryptology 3 (1991), no. 2, 63–79. MR 1113370, DOI 10.1007/BF00196789
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.
T. Beth, Efficient zero-knowledge identification scheme for smart cards, Advances in Cryptology (Proc. Eurocrypt ‘88), Springer LNCS 330 (1988), 77–84.
Ian F. Blake, Shuhong Gao, and Robert Lambert, Constructive problems for irreducible polynomials over finite fields, Information theory and applications (Rockland, ON, 1993) Lecture Notes in Comput. Sci., vol. 793, Springer, Berlin, 1994, pp. 1–23. MR 1289223, DOI 10.1007/3-540-57936-2_{2}7
Manuel Blum and Silvio Micali, How to generate cryptographically strong sequences of pseudorandom bits, SIAM J. Comput. 13 (1984), no. 4, 850–864. MR 764183, DOI 10.1137/0213053
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^n \pm 1$, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR 996414, DOI 10.1090/conm/022
Whitfield Diffie and Martin E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644–654. MR 437208, DOI 10.1109/tit.1976.1055638
Taher ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory 31 (1985), no. 4, 469–472. MR 798552, DOI 10.1109/TIT.1985.1057074
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.
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.
Shuhong Gao and Scott A. Vanstone, On orders of optimal normal basis generators, Math. Comp. 64 (1995), no. 211, 1227–1233. MR 1297469, DOI 10.1090/S0025-5718-1995-1297469-6
J. von zur Gathen and F. Pappalardi, Density estimates related to Gauss periods, 1996, preprint.
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
Carl Friedrich Gauss, Disquisitiones arithmeticae, Springer-Verlag, New York, 1986. Translated and with a preface by Arthur A. Clarke; Revised by William C. Waterhouse, Cornelius Greither and A. W. Grootendorst and with a preface by Waterhouse. MR 837656, DOI 10.1007/978-1-4939-7560-0
Tom Hansen and Gary L. Mullen, Primitive polynomials over finite fields, Math. Comp. 59 (1992), no. 200, 639–643, S47–S50. MR 1134730, DOI 10.1090/S0025-5718-1992-1134730-7
Dieter Jungnickel, Finite fields, Bibliographisches Institut, Mannheim, 1993. Structure and arithmetics. MR 1238714
L. Lamport, Password authentication with insecure communication, Comm. ACM, 24 (1981), 770–772.
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.
Douglas L. Long and Avi Wigderson, The discrete logarithm hides $O(\textrm {log}\,n)$ bits, SIAM J. Comput. 17 (1988), no. 2, 363–372. Special issue on cryptography. MR 935345, DOI 10.1137/0217021
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.
Ilene H. Morgan and Gary L. Mullen, Primitive normal polynomials over finite fields, Math. Comp. 63 (1994), no. 208, 759–765, S19–S23. MR 1257578, DOI 10.1090/S0025-5718-1994-1257578-3
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
National Institute for Standard and Technology, Federal Information Processing Standard for Digital Signature Standard (DSS), FIPS 186, May 1994.
R. Peralta, Simultaneous security of bits in the discrete log, Advances in Cryptology (Proc. Eurocrypt ‘85), Springer LNCS 219 (1986), 62–72.
C.-P. Schnorr, Efficient identification and signatures for smart cards, Advances in cryptology—CRYPTO ’89 (Santa Barbara, CA, 1989) Lecture Notes in Comput. Sci., vol. 435, Springer, New York, 1990, pp. 239–252. MR 1062237, DOI 10.1007/0-387-34805-0_{2}2
C.P. Schnorr, Efficient signature generation by smart cards, J. of Cryptology, 4 (1991), 161–174.
V. Shoup, Exponentiation in $GF(2^n)$ using fewer polynomial multiplications, preprint, 1994.
Alfred Wassermann, Konstruktion von Normalbasen, Bayreuth. Math. Schr. 31 (1990), 155–164 (German). MR 1056152
Alfred Wassermann, Zur Arithmetik in endlichen Körpern, Bayreuth. Math. Schr. 44 (1993), 147–251 (German). Dissertation, Universität Bayreuth, Bayreuth, 1992. MR 1224776
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.
Y. Zheng and J. Seberry, Immunizing public key cryptosystems against chosen ciphertext attacks, IEEE J. on Selected Areas in Communications, 11 (1993), 715–724.
Neal Zierler and John Brillhart, On primitive trinomials $(\textrm {mod}\ 2)$, Information and Control 13 (1968), 541–554. MR 237468, DOI 10.1016/S0019-9958(68)90973-X
Neal Zierler and John Brillhart, On primitive trinomials $(\textrm {mod}\ 2)$. II, Information and Control 14 (1969), 566–569. MR 244204, DOI 10.1016/S0019-9958(69)90356-8
Miodrag Živković, A table of primitive binary polynomials, Math. Comp. 62 (1994), no. 205, 385–386. MR 1201073, DOI 10.1090/S0025-5718-1994-1201073-4
Miodrag Živković, Table of primitive binary polynomials. II, Math. Comp. 63 (1994), no. 207, 301–306. MR 1240662, DOI 10.1090/S0025-5718-1994-1240662-8