Characterization for a family of infinitely many irreducible Equally Spaced Polynomials | SpringerLink
Skip to main content
Springer Nature Link
Log in

Characterization for a family of infinitely many irreducible Equally Spaced Polynomials

  • Conference paper
  • First Online:
Algorithms (SIGAL 1990)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 450))

Included in the following conference series:

  • 189 Accesses

Abstract

This paper shows a necessary and sufficient condition for a family of infinitely many Equally Spaced Polynomial (ESP's) to be irreducible over GF(2) and the uniqueness of irreducible ESP's over GF(2), i.e., there exist no distinct irreducible ESP's of the same degree. It is worth noting that these results in this paper completely characterize all irreducible ESP's.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Asano, Y., Itoh, T., Tsujii, S., “Generalized Fast Algorithm for Computing Multiplicative Inverses in GF(2m)”, Electronics Letters, Vol.25, No.10, May 1989, pp.664–665.

    Google Scholar 

  2. Itoh, T., “Algorithms for Finite Fields Arithmetics and Their Applications to Public-Key Cryptosystems,” Doctor Thesis, Tokyo Institute of Technology, August 1988.

    Google Scholar 

  3. Imai, H. and Matsumoto, T., “Algebraic Method for Constructing Asymmetric Cryptosystems,” Proc. of AAECC-3, Grenoble France, July 1985.

    Google Scholar 

  4. Itoh, T and Tsujii, S., “A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) Using Normal Bases,” Information and Computation, Vol.78, No.3, September 1988, pp.171–177.

    Article  Google Scholar 

  5. Itoh, T. and Tsujii, S., “Structure of Parallel Multipliers for a Class of Fields GF(2m),”, Information and Computation, Vol.83, No.1, October 1989, pp.21–40.

    Article  Google Scholar 

  6. Itoh, T. and Tsujii, S., “Effective Recursive Algorithm for Computing Multiplicative Inverses in GF(2m),” Electronics Letters, Vol.24, No.6, March 1988, pp.334–335.

    Google Scholar 

  7. McEliece, R.J., “A Public-Key Cryptosystem Based on Algebraic Coding Theory,” DSN Progress Report 42–44, January/February 1978, pp.114–116.

    Google Scholar 

  8. McEliece, R.J., “Finite Fields for Computer Scientists and Engineers,” Kluwer Academic Publisher, 1987.

    Google Scholar 

  9. MacWilliams, F.J. and Sloane, N.J.A., “The Theory of Error-Correcting Codes,” North-Holland, New York, 1977.

    Google Scholar 

  10. Massey, J.L. and Omura, J.K., patent Application of “Computational method and apparatus for finite field arithmetic,” submitted in 1981.

    Google Scholar 

  11. Mullin, R.C., Onyszchuk, I.M., Vanstone, S.A., and Wilson, R.M., “Optimal Normal Bases in GF(p n),” Discrete Applied Mathematics, Vol.22, No.2, 1988/89, pp.149–161.

    Article  Google Scholar 

  12. Oorschot, P.C. and Vanstone, S.A., “A Geometric Approach to Root Finding in GF(q m),” IEEE Trans. on Informa. Theory, Vol.35, No.2, March 1989, pp.444–453.

    Article  Google Scholar 

  13. Pincin, A., “A New Algorithm for Multiplication in Finite Fields,” IEEE Trans. on Comput., Vol.38, No.7, July 1989, pp.1045–1049.

    Article  Google Scholar 

  14. Sugimura T. and Suetsugu, Y., “A Consideration on Existence Condition of Irreducible Cyclotomic Polynomial and Its Property,” Technical Report of the IEICE, ISEC89-45, March 1990, pp.37–45.

    Google Scholar 

  15. Tsujii, S., Kurosawa, K., Itoh, T., Fujioka, A., and Matsumoto, T., “A Public-Key Cryptosystem Based on the Difficulty of Solving a System of Non-linear Equations,” Electronics Letters, Vol.23, No.11, May 1987, pp.558–560.

    Google Scholar 

  16. Wang, C.C., “Exponentiation in Finite Fields,” Doctor Thesis, UCLA, 1985.

    Google Scholar 

  17. Wang, C.C., Truong, T.K., Shao, I.S., Deutsch, L.J., and Reed, I.S., “VLSI Architecture for Computing Multiplications and Inverses in GF(2m),” IEEE Trans. on Comput., Vol.34, No.8, August 1985, pp.709–715.

    Google Scholar 

  18. Wah, P.K.S. and Wang, M.Z., “Realization and Application of Massey-Omura Lock,” Proc. of International Zurich Seminar, 1989, pp.175–182.

    Google Scholar 

  19. Zierler, N., “On Primitive Trinomials (mod 2),” Information and Control, Vol.12, 1968, pp.541–554.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Processing The Graduate School at Nagatsuta, Tokyo Institute of Technology, 4259 Nagatsuta, Midori-ku, 227, Yokohama, Japan

    Toshiya Itoh

Authors
  1. Toshiya Itoh
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Tetsuo Asano Toshihide Ibaraki Hiroshi Imai Takao Nishizeki

Rights and permissions

Reprints and permissions

Copyright information

© 1990 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Itoh, T. (1990). Characterization for a family of infinitely many irreducible Equally Spaced Polynomials. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52921-7_67

Download citation

  • DOI: https://doi.org/10.1007/3-540-52921-7_67

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-52921-7

  • Online ISBN: 978-3-540-47177-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation