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
DOI: https://doi.org/10.1090/S0025-5718-03-01515-1
Published electronically: February 3, 2003
MathSciNet review: 1986817
Full-text PDF

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 (1957).
    On certain trinomial equations in finite fields.
    Annals of Mathematics 66(1), 170-178. MR 19:394d
  • 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. ELWIN R. BERLEKAMP (1968).
    Algebraic Coding Theory.
    McGraw-Hill, New York. MR 38:6873
  • 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 & VICTOR ZINOVIEV (1998).
    Codes, Bent Functions and Permutations Suitable For DES-like Cryptosystems.
    Designs, Codes and Cryptography 15, 125-156. MR 99k:94030
  • 6. L. CARLITZ (1970).
    Factorization of a special polynomial over a finite field.
    Pacific Journal of Mathematics 32(3), 603-614. MR 41:1693
  • 7. C. CAZACU & D. SIMOVICI (1973).
    A New Approach of Some Problems Concerning Polynomials Over Finite Fields.
    Information and Control 22, 503-511. MR 48:3925
  • 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 & VICTOR ZINOVIEV (1999).
    On the Minimum Distances of Non-Binary Cyclic Codes.
    Designs, Codes and Cryptography 17, 81-85. MR 2000h:94050
  • 10. KÅRE DALEN (1955).
    On a theorem of Stickelberger.
    Mathematica Scandinavica 3, 124-126. MR 17:130a
  • 11. ERIK DE WIN, ANTOON BOSSELAERS, SERVAAS VANDENBERGHE, PETER DE GERSEM & JOOS VANDEWALLE (1996).
    A Fast Software Implementation for Arithmetic Operations in $GF(2^n)$.
    In Advances in Cryptology: Proceedings of ASIACRYPT 1996, Kyongju, Korea, KWANGJO KIM, editor, number 1163 in Lecture Notes in Computer Science, 65-76. Springer-Verlag.
    ISSN 0302-9743.
    ftp://ftp.esat.kuleuven.ac.be/pub/cosic/dewin/asia96p103.ps.gz. MR 98g:94001
  • 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 & TETSURO KOJIMA (1996).
    Irreducible Quadratic Factors of $x^{(q^n+1)/2}+ax+b$ over $\mathbb{F} _q$.
    Finite Fields and Their Applications 2(2), 204-213.
    ISSN 1071-5797. MR 97a:11196
  • 14. H. FREDRICKSEN & R. WISNIEWSKI (1981).
    On Trinomials $x^n+x^2+1$ and $x^{8 l \pm 3}+x^k+1$ Irreducible over $GF(2)$.
    Information and Control 50, 58-63. MR 84i:12013
  • 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 & MICHAEL NÖCKER (1997).
    Exponentiation in Finite Fields: Theory and Practice.
    In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: AAECC-12, Toulouse, France, TEO MORA & HAROLD MATTSON, editors, number 1255 in Lecture Notes in Computer Science, 88-113. Springer-Verlag.
    ISSN 0302-9743. MR 99c:68123
  • 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 (1967).
    Shift Register Sequences.
    Holden-Day Series in Information Systems. Holden-Day, Inc., San Francisco, California.
    With portions co-authored by Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales. MR 39:3906
  • 20. SOLOMON W. GOLOMB & GUANG GONG (1999).
    Periodic Binary Sequences with the ``Trinomial Property''.
    IEEE Transactions on Information Theory 45(4), 1276-1279. MR 2000g:94026
  • 21. TOR HELLESETH, CHUNMING RONG & DANIEL SANDBERG (1999).
    New Families of Almost Perfect Nonlinear Power Mappings.
    IEEE Transactions on Information Theory 45(2), 475-485. MR 2000c:11201
  • 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. I. KAPLANSKY (1972).
    Fields and Rings.
    University of Chicago Press, Chicago. MR 50:2139
  • 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 & SCOTT A. VANSTONE (1997).
    Handbook of Applied Cryptography.
    CRC Press, Boca Raton FL. MR 99g:94015
  • 26. AKIHIRO MUNEMASA (1998).
    Orthogonal Arrays, Primitive Trinomials, and Shift-Register Sequences.
    Finite Fields and Their Applications 4(3), 252-260. MR 99m:94029
  • 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 (1971).
    Proof of a Conjecture of S. Chowla.
    Journal of Number Theory 3, 210-212. MR 43:3235; MR 45:3362
  • 30. RICHARD SCHROEPPEL, HILARIE ORMAN, SEAN O'MALLEY & OLIVER SPATSCHECK (1995).
    Fast Key Exchange with Elliptic Curve Systems.
    In Advances in Cryptology: Proceedings of CRYPTO '95, Santa Barbara CA, DON COPPERSMITH, editor, number 963 in Lecture Notes in Computer Science, 43-56. Springer.
    ISSN 0302-9743.
    http://theory.lcs.mit.edu/ dmjones/hbp/crypto/crypto95.html. MR 98a:94029
  • 31. STEVE SEIDEN (2001).
    Can a Computer Proof be Elegant?
    SIGACT News 60(1), 111-114.
  • 32. ERNST S. SELMER (1956).
    On the irreducibility of certain trinomials.
    Mathematica Scandinavica 4, 287-302. MR 19:7f
  • 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 (1962).
    Factorization of polynomials over finite fields.
    Pacific Journal of Mathematics 12, 1099-1106. MR 26:2432
  • 35. UZI VISHNE (1997).
    Factorization of Trinomials over Galois Fields of Characteristic $2$.
    Finite Fields and Their Applications 3(4), 370-377. MR 98i:11106
  • 36. NEAL ZIERLER (1970).
    On $x^n+x+1$ over $GF(2)$.
    Information and Control 16, 502-505. MR 42:5955
  • 37. NEAL ZIERLER & JOHN BRILLHART (1969).
    On Primitive Trinomials (Mod $2$), II.
    Information and Control 14, 566-569. MR 39:5521

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

American Mathematical Society