Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On orders of optimal normal basis generators

Authors: Shuhong Gao and Scott A. Vanstone
Journal: Math. Comp. 64 (1995), 1227-1233
MSC: Primary 11T30; Secondary 11Y05, 11Y16
MathSciNet review: 1297469
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we give some experimental results on the multiplicative orders of optimal normal basis generators in $ {F_{{2^n}}}$ over $ {F_2}$ for $ n \leq 1200$ whenever the complete factorization of $ {2^n} - 1$ is known. Our results show that a subclass of optimal normal basis generators always have high multiplicative orders, at least $ O(({2^n} - 1)/n)$, and are very often primitive. For a given optimal normal basis generator $ \alpha $ in $ {F_{{2^n}}}$ and an arbitrary integer e, we show that $ {\alpha ^e}$ can be computed in $ O(n \cdot v(e))$ bit operations, where $ v(e)$ is the number of 1's in the binary representation of e.

References [Enhancements On Off] (What's this?)

  • [1] 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), 63-79. MR 1113370 (92b:94034)
  • [2] 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.
  • [3] E. F. Brickell, D. M. Gordon, K. S. McCurley, and D. B. Wilson, Fast exponentiation with precomputation, Proc. Eurocrypt'92, Balatonfured, Hungary, 1992.
  • [4] J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of $ {b^n} \pm 1, \; b = 2,3,5,6,7,10,11,12$ up to high powers, 2nd ed., Contemp. Math., vol. 22, Amer. Math. Soc., Providence, RI, 1988. MR 996414 (90d:11009)
  • [5] D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), 693-701. MR 1129288 (92i:68068)
  • [6] S. Gao and H. W. Lenstra, Jr., Optimal normal bases, Des. Codes Cryptogr. 2 (1992), 315-323. MR 1194773 (93j:12003)
  • [7] J. von zur Gathen, Efficient and optimal exponentiation in finite fields, Comput. Complexity 1 (1991), 360-394. MR 1172675 (94a:68061)
  • [8] D. H. Lehmer, On certain chains of primes, Proc. London Math. Soc. 14A (Littlewood 80 volume, 1965), 183-186. MR 0177964 (31:2222)
  • [9] R. Lidl and H. Niederreiter, Finite fields, Addison-Wesley, Reading, MA, 1983. (Now distributed by Cambridge University Press.) MR 1429394 (97i:11115)
  • [10] A. J. Menezes, I. F. Blake, X. Gao, R. C. Mullin, S. A. Vanstone, and T. Yaghoobian, Applications of finite fields, Kluwer, Boston-Dordrecht-Lancaster, 1993.
  • [11] R. C. Mullin, I. M. Onyszchuk, S. A. Vanstone, and R. M. Wilson, Optimal normal bases in $ GF({p^n})$, Discrete Appl. Math. 22 (1988/1989), 149-161. MR 978054 (90c:11092)
  • [12] A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292. MR 0292344 (45:1431)
  • [13] D. R. Stinson, Some observations on parallel algorithms for fast exponentiation in $ GF({2^n})$, SIAM J. Comput. 19 (1990), 711-717. MR 1053938 (91k:68097)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T30, 11Y05, 11Y16

Retrieve articles in all journals with MSC: 11T30, 11Y05, 11Y16

Additional Information

Keywords: Finite fields, primitive elements, normal bases
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society