Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Gauss periods: orders
and cryptographical applications


Authors: Shuhong Gao, Joachim von zur Gathen and Daniel Panario
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
Supplement: Additional information related to this article.
MathSciNet review: 1458221
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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$, $b=2,3,5,6,7,10,11,12$ 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 $GF(p^n)$, 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 $GF(2^n)$ 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

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11T30, 94A60, 11Y16, 12Y05, 68Q25

Retrieve articles in all journals with MSC (1991): 11T30, 94A60, 11Y16, 12Y05, 68Q25


Additional Information

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: https://doi.org/10.1090/S0025-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.
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society