Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

Irreducible trinomials over finite fields


Author: Joachim von zur Gathen
Journal: Math. Comp. 72 (2003), 1987-2000
MSC (2000): Primary 11T06; Secondary 12Y05, 68W30
Published electronically: February 3, 2003
MathSciNet review: 1986817
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A necessary condition for irreducibility of a trinomial over a finite field, based on classical results of Stickelberger and Swan, is established. It is applied in the special case $\mathbb{F} _{3}$, and some experimental discoveries are reported.


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

  • 1. A. A. Albert, On certain trinomial equations in finite fields, Ann. of Math. (2) 66 (1957), 170–178. MR 0087691
  • 2. M. BEN-OR (1981).
    Probabilistic algorithms in finite fields.
    In Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science, Nashville TN, 394-398.
  • 3. Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
  • 4. ANNE CANTEAUT & ERIC FILIOL (2001).
    Ciphertext only reconstruction of stream ciphers based on combination generators.
    In Proceedings of Fast Software Encryption (FSE 2000), B. SCHNEIER, editor, number 1978 in Lecture Notes in Computer Science. Springer-Verlag, New York. http://link.springer.de/link/service/series/0558/bibs/1978/19780165.htm
  • 5. Claude Carlet, Pascale Charpin, and Victor Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr. 15 (1998), no. 2, 125–156. MR 1658423, 10.1023/A:1008344232130
  • 6. L. Carlitz, Factorization of a special polynomial over a finite field, Pacific J. Math. 32 (1970), 603–614. MR 0257038
  • 7. C. Cazacu and D. Simovici, A new approach of some problems concerning polynomials over finite fields, Information and Control 22 (1973), 503–511. MR 0325578
  • 8. P. CHARPIN, A. TIETÄVÄINEN & VICTOR ZINOVIEV (1997).
    On binary cyclic codes with minimum distance $d=3$.
    Problems of Information Transmission 33(4), 287-296.
  • 9. Pascale Charpin, Aimo Tietäväinen, and Victor Zinoviev, On the minimum distances of non-binary cyclic codes, Des. Codes Cryptogr. 17 (1999), no. 1-3, 81–85. MR 1714371, 10.1023/A:1008354504832
  • 10. Kåre Dalen, On a theorem of Stickelberger, Math. Scand. 3 (1955), 124–126. MR 0071460
  • 11. Kwangjo Kim and Tsutomu Matsumoto (eds.), Advances in cryptology—ASIACRYPT ’96, Lecture Notes in Computer Science, vol. 1163, Springer-Verlag, Berlin, 1996. MR 1486044
  • 12. L. E. DICKSON (1906).
    Criteria for the irreducibility of functions in a finite field.
    Bulletin of the American Mathematical Society 13(1), 1-8.
  • 13. Dennis R. Estes and Tetsuro Kojima, Irreducible quadratic factors of 𝑥^{(𝑞ⁿ+1)/2}+𝑎𝑥+𝑏 over 𝐹_{𝑞}, Finite Fields Appl. 2 (1996), no. 2, 204–213. MR 1384160, 10.1006/ffta.1996.0013
  • 14. H. Fredricksen and R. Wisniewski, On trinomials 𝑥ⁿ+𝑥²+1 and 𝑥^{8𝑙±3}+𝑥^{𝑘}+1 irreducible over 𝐺𝐹(2), Inform. and Control 50 (1981), no. 1, 58–63. MR 665139, 10.1016/S0019-9958(81)90144-3
  • 15. SHUHONG GAO, JOACHIM VON ZUR GATHEN, DANIEL PANARIO & VICTOR SHOUP (2000).
    Algorithms for Exponentiation in Finite Fields.
    Journal of Symbolic Computation 29(6), 879-889.
    http://www.idealibrary.com/servlet/doi/10.1006/jsco.1999.0309. MR 2002e:68152
  • 16. Joachim von zur Gathen and Michael Nöcker, Exponentiation in finite fields: theory and practice, Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 1997) Lecture Notes in Comput. Sci., vol. 1255, Springer, Berlin, 1997, pp. 88–113. MR 1634108, 10.1007/3-540-63163-1_8
  • 17. JOACHIM VON ZUR GATHEN & MICHAEL NÖCKER (2002).
    Exponentiation using addition chains for finite fields.
    In preparation.
  • 18. RICHARD M. GOLDSTEIN & NEAL ZIERLER (1968).
    On Trinomial Recurrences.
    IEEE Transactions on Information Theory IT-14(1), 150-151.
  • 19. Solomon W. Golomb, Shift register sequences, With portions co-authored by Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales, Holden-Day, Inc., San Francisco, Calif.-Cambridge-Amsterdam, 1967. MR 0242575
  • 20. Solomon W. Golomb and Guang Gong, Periodic binary sequences with the “trinomial property”, IEEE Trans. Inform. Theory 45 (1999), no. 4, 1276–1279. MR 1686268, 10.1109/18.761284
  • 21. Tor Helleseth, Chunming Rong, and Daniel Sandberg, New families of almost perfect nonlinear power mappings, IEEE Trans. Inform. Theory 45 (1999), no. 2, 474–485. MR 1677012, 10.1109/18.748997
  • 22. IEEE (2000).
    IEEE Standard Specifications for Public-Key Cryptography.
    Technical Report IEEE Std 1363-2000, Institute of Electrical and Electronics Engineers, Inc., 3 Park Avenue, New York, NY 10016-5997, USA.
  • 23. Irving Kaplansky, Fields and rings, 2nd ed., The University of Chicago Press, Chicago, Ill.-London, 1972. Chicago Lectures in Mathematics. MR 0349646
  • 24. PIERRE LOIDREAU (2000).
    On the Factorization of Trinomials over ${\mathbb F}_3$.
    Technical Report 3918, Institut national de recherche en informatique et en automatique (INRIA).
    http://www.inria.fr/RRRT/RR-3918.html.
  • 25. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR 1412797
  • 26. Akihiro Munemasa, Orthogonal arrays, primitive trinomials, and shift-register sequences, Finite Fields Appl. 4 (1998), no. 3, 252–260. MR 1640769, 10.1006/ffta.1998.0213
  • 27. OYSTEIN ORE (1934).
    Contributions to the theory of finite fields.
    Transactions of the American Mathematical Society 36, 243-274.
  • 28. A.-E. PELLET (1878).
    Sur la décomposition d'une fonction entière en facteurs irréductibles suivant un module premier $p$.
    Comptes Rendus de l'Académie des Sciences Paris 86, 1071-1072.
  • 29. Rimhak Ree, Proof of a conjecture of S. Chowla, J. Number Theory 3 (1971), 210–212. MR 0277502
    Rimhak Ree, Erratum to: “Proof of a conjecture of S. Chowla”, J. Number Theory 4 (1972), 223. MR 0294293
  • 30. Richard Schroeppel, Hilarie Orman, Sean O’Malley, and Oliver Spatscheck, Fast key exchange with elliptic curve systems, Advances in cryptology—CRYPTO ’95 (Santa Barbara, CA, 1995) Lecture Notes in Comput. Sci., vol. 963, Springer, Berlin, 1995, pp. 43–56. MR 1445566, 10.1007/3-540-44750-4_4
  • 31. STEVE SEIDEN (2001).
    Can a Computer Proof be Elegant?
    SIGACT News 60(1), 111-114.
  • 32. Ernst S. Selmer, On the irreducibility of certain trinomials, Math. Scand. 4 (1956), 287–302. MR 0085223
  • 33. L. STICKELBERGER (1897).
    Über eine neue Eigenschaft der Diskriminanten algebraischer Zahlkörper.
    Verhandlungen des ersten Internationalen Mathematiker-Kongresses, Zürich, 182-193.
  • 34. Richard G. Swan, Factorization of polynomials over finite fields, Pacific J. Math. 12 (1962), 1099–1106. MR 0144891
  • 35. Uzi Vishne, Factorization of trinomials over Galois fields of characteristic 2, Finite Fields Appl. 3 (1997), no. 4, 370–377. MR 1478835, 10.1006/ffta.1997.0191
  • 36. Neal Zierler, On 𝑥ⁿ+𝑥+1 over 𝐺𝐹(2), Information and Control 16 (1970), 502–505. MR 0271072
  • 37. Neal Zierler and John Brillhart, On primitive trinomials (𝑚𝑜𝑑2). II, Information and Control 14 (1969), 566–569. MR 0244204

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11T06, 12Y05, 68W30

Retrieve articles in all journals with MSC (2000): 11T06, 12Y05, 68W30


Additional Information

Joachim von zur Gathen
Affiliation: Fakultät für Elektrotechnik, Informatik, Mathematik, Universität Paderborn, D-33095 Paderborn, Germany
Email: gathen@upb.de

DOI: https://doi.org/10.1090/S0025-5718-03-01515-1
Received by editor(s): March 29, 2001
Received by editor(s) in revised form: April 17, 2002
Published electronically: February 3, 2003
Article copyright: © Copyright 2003 American Mathematical Society