Skip to main content
SpringerLink
Log in
Book cover

Foundations of Computational Mathematics pp 346–361Cite as

Tests and Constructions of Irreducible Polynomials over Finite Fields

  • Conference paper

Abstract

In this paper we focus on tests and constructions of irreducible polynomials over finite fields. We revisit Rabin’s (1980) algorithm providing a variant of it that improves Rabin’s cost estimate by a log n factor. We give a precise analysis of the probability that a random polynomial of degree n contains no irreducible factors of degree less than O(log n). This probability is naturally related to Ben-Or’s (1981) algorithm for testing irreducibility of polynomials over finite fields. We also compute the probability of a polynomial being irreducible when it has no irreducible factors of low degree. This probability is useful in the analysis of various algorithms for factoring polynomials over finite fields. We present an experimental comparison of these irreducibility methods when testing random polynomials.

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

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Ben-Or, M. Probabilistic algorithms in finite fields. In Proc. 22nd IEEE Symp. Foundations Computer Science (1981), pp. 394 – 398.

    Google Scholar 

  2. Blake, I., Gao, S., AND Lambert, R. Constructive problems for irreducible polynomials over finite fields. In Information Theory and Applications, A. Gulliver and N. Secord, Eds., vol. 793 of Lecture Notes in Computer Science. Springer-Verlag, 1994, pp. 12 – 23.

    Google Scholar 

  3. Blake, I., GAO, S., and Mullin, R. Explicit factorization of x2k + 1 over Fp with prime p ≡ 3 (mod 4). Appi Alg. Eng. Comm. Comp.4 (1993), 89 – 94.

    Article  MathSciNet  MATH  Google Scholar 

  4. Butler, M. On the reducibility of polynomials over a finite field. Quart. J. Math. Oxford 5(1954), 102 – 107.

    Article  MATH  Google Scholar 

  5. Cantor, D., and Kaltofen, E. On fast multiplication of polynomials over arbitrary algebras. Acta. Inform. 28(1991), 693 – 701.

    Article  MathSciNet  MATH  Google Scholar 

  6. Coppersmith, D. Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Info. Theory 30(1984), 587 – 594.

    Article  MathSciNet  MATH  Google Scholar 

  7. Flajolet, P., Gourdon, X., and Panario, D. Random polynomials and polynomial factorization. In Proc. 23rd ICALP Symp. (1996), vol. 1099 of Lecture Notes in Computer Science, Springer-Verlag, pp. 232–243.

    Google Scholar 

  8. Flajolet, P., and Odlyzko, A. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics 3 2(1990), 216 – 240.

    Article  MathSciNet  MATH  Google Scholar 

  9. Gao, S., Von Zur Gathen, J., And Panario, D. Gauss periods and efficient arithmetic in finite fields. Submitted to Journal of Symbolic Computation (extended abstract in Proc. LATIN’95, vol. 911 of Lecture Notes in Computer Science, 311 – 322 ), 1995.

    Google Scholar 

  10. Gao, S., And Mullen, G. Dickson polynomials and irreducible polynomials over finite fields. J. Number Theory 49(1994), 118 – 132.

    Article  MathSciNet  MATH  Google Scholar 

  11. Gao, S., and Panario, D. Density of normal elements. Submitted to Finite Fields and their Applications (abstract in AMS Abstracts 102Fall 1995, # 904-68–227, p. 798 ), 1995.

    Google Scholar 

  12. Von Zur Gathen, J., And Gerhard, J. Arithmetic and factorization of polynomials over F2. In Proc. ISSAC’96, Zürich, Switzerland(1996), L. Y.N., Ed., ACM press, pp. 1 – 9.

    Google Scholar 

  13. Von Zur Gathen, J., and Panario, D. A survey on factoring polynomials over finite fields. Submitted to the special issue of the MAGMA conference in J. Symb. Comp., 1996.

    Google Scholar 

  14. Von Zur Gathen, J., and Shoup, V. Computing Frobenius maps and factoring polynomials. Comput complexity 2(1992), 187 – 224.

    Article  MathSciNet  MATH  Google Scholar 

  15. Golomb, S. W. Shift register sequences. Aegean Park Press, Laguna Hills, California, 1982.

    Google Scholar 

  16. Graham, R., Knuth, D., and Patashnik, O. Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA, 1994.

    MATH  Google Scholar 

  17. Ireland, K., and Rosen, M. A Classical Introduction to Modern Number Theory, 2nd ed. Springer-Verlag, Berlin, 1990.

    MATH  Google Scholar 

  18. Kaltofen, E., and Shoup, V. Subquadratic-time factoring of polynomials over finite fields. In Proc. 27th ACM Symp. Theory of Computing(1995), pp. 398 – 406.

    Google Scholar 

  19. Knopfmacher, J., And Knopfmacher, A. Counting irreducible factors of polynomials over a finite field. SIAM Journal on Discrete Mathematics 112(1993), 103 – 118.

    MathSciNet  MATH  Google Scholar 

  20. Knuth, D. The art of computer programming, vol.2: seminumerical algorithms, 2nd ed. Addison-Wesley, Reading MA, 1981.

    MATH  Google Scholar 

  21. Lidl, R., and Niederreiter, H. Finite fields, vol. 20 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading MA, 1983.

    Google Scholar 

  22. Menezes, A., Blake, I., Gao, X., Mullin, R., Vanstone, S., and Yaghoo-Bian, T. Applications of Finite Fields. Kluwer Academic Publishers, Boston, Dordrecht, Lancaster, 1993.

    MATH  Google Scholar 

  23. Odlyzko, A. Discrete logarithms and their cryptographic significance. In Advances in Cryptology, Proceedings of Eurocrypt 1984 (1985), vol. 209 of Lecture Notes in Computer Science, Springer-Verlag, pp. 224–314.

    Google Scholar 

  24. Odlyzko, A. Asymptotic enumeration methods. In Handbook of Combinatorics, R. Graham, M. Gròtschel, and L. Lovász, Eds. Elsevier, 1996.

    Google Scholar 

  25. Panario, D. Combinatorial and algebraic aspects of polynomials over finite fields. PhD Thesis, in preparation, 1996.

    Google Scholar 

  26. Rabin, M. O. Probabilistic algorithms in finite fields. SIAM J. Comp. 9(1980), 273 – 280.

    Article  MathSciNet  MATH  Google Scholar 

  27. Schönhage, A. Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Inf. 7(1977), 395 – 398.

    Article  MATH  Google Scholar 

  28. Schönhage, A., and Strassen, V. Schnelle Multiplikation großer Zahlen. Computing 7(1971), 281 – 292.

    Article  MATH  Google Scholar 

  29. Sedgewick, R., AND Flajolet, P. An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading MA, 1996.

    MATH  Google Scholar 

  30. Shepp, L., and Lloyd, S. Ordered cycle lengths in a random permutation. Trans. Amer. Math. Soc. 121(1966), 340 – 357.

    Article  MathSciNet  MATH  Google Scholar 

  31. Shoup, V. Fast construction of irreducible polynomials over finite fields. J. Symb. Comp. 17(1995), 371–391.

    Article  MathSciNet  Google Scholar 

  32. Shoup, V. A new polynomial factorization algorithm and its implementation. J. Symb. Comp. 20(1996), 363–397.

    Article  MathSciNet  Google Scholar 

  33. Shparlinski, . Finding irreducible and primitive polynomials. Appl. Alg. Eng. Comm. Comp. 4(1993), 263–268.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Authors
  1. Shuhong Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel Panario
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics, City University of Hong Kong, Tat Cheet Avenue, 83 Tat Chee Avenue, Kowloon, Hong Kong

    Felipe Cucker

  2. Departament d’Economia, Universitat Pompeu Fabra, Ramon Trias Fargas 25-27, 08005, Barcelona, Spain

    Felipe Cucker

  3. I.B.M. T.J. Watson Center, 10598, Yorktown Heights, New York, USA

    Michael Shub

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gao, S., Panario, D. (1997). Tests and Constructions of Irreducible Polynomials over Finite Fields. In: Cucker, F., Shub, M. (eds) Foundations of Computational Mathematics. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-60539-0_27

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-60539-0_27

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-61647-4

  • Online ISBN: 978-3-642-60539-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation