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
Additional Information
- Shuhong Gao
- Affiliation: Department of Mathematical Sciences Clemson University Clemson, SC 29634-1907, USA
- MR Author ID: 291308
- Email: sgao@math.clemson.edu
- Joachim von zur Gathen
- Affiliation: Fachbereich Mathematik-Informatik Universität-GH Paderborn D-33095 Paderborn, Germany
- MR Author ID: 71800
- 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
- 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 1998 American Mathematical Society
- Journal: Math. Comp. 67 (1998), 343-352
- MSC (1991): Primary 11T30, 94A60; Secondary 11Y16, 12Y05, 68Q25
- DOI: https://doi.org/10.1090/S0025-5718-98-00935-1
- MathSciNet review: 1458221