Irreducible trinomials over finite fields

von zur Gathen, Joachim

doi:10.1090/S0025-5718-03-01515-1

Irreducible trinomials over finite fields
HTML articles powered by AMS MathViewer

by Joachim von zur Gathen PDF

Math. Comp. 72 (2003), 1987-2000 Request permission

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

Saunders MacLane and O. F. G. Schilling, Infinite number fields with Noether ideal theories, Amer. J. Math. 61 (1939), 771–782. MR 19, DOI 10.2307/2371335
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.
Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
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
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, DOI 10.1023/A:1008344232130
L. Carlitz, Factorization of a special polynomial over a finite field, Pacific J. Math. 32 (1970), 603–614. MR 257038
C. Cazacu and D. Simovici, A new approach of some problems concerning polynomials over finite fields, Information and Control 22 (1973), 503–511. MR 325578
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.
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, DOI 10.1023/A:1008354504832
Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23–45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
Kwangjo Kim and Tsutomu Matsumoto (eds.), Advances in cryptology—ASIACRYPT ’96, Lecture Notes in Computer Science, vol. 1163, Springer-Verlag, Berlin, 1996. MR 1486044, DOI 10.1007/BFb0034829
L. E. Dickson (1906). Criteria for the irreducibility of functions in a finite field. Bulletin of the American Mathematical Society 13(1), 1–8.
Dennis R. Estes and Tetsuro Kojima, Irreducible quadratic factors of $x^{(q^n+1)/2}+ax+b$ over $\textbf {F}_q$, Finite Fields Appl. 2 (1996), no. 2, 204–213. MR 1384160, DOI 10.1006/ffta.1996.0013
H. Fredricksen and R. Wisniewski, On trinomials $x^{n}+x^{2}+1$ and $x^{8l\pm 3}+x^{k}+1$ irreducible over $\textrm {GF}(2)$, Inform. and Control 50 (1981), no. 1, 58–63. MR 665139, DOI 10.1016/S0019-9958(81)90144-3
M. Gontcharoff, Sur quelques séries d’interpolation généralisant celles de Newton et de Stirling, Uchenye Zapiski Moskov. Gos. Univ. Matematika 30 (1939), 17–48 (Russian, with French summary). MR 0002002
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, DOI 10.1007/3-540-63163-1_{8}
Joachim von zur Gathen & Michael Nöcker (2002). Exponentiation using addition chains for finite fields. In preparation.
Richard M. Goldstein & Neal Zierler (1968). On Trinomial Recurrences. IEEE Transactions on Information Theory IT-14(1), 150–151.
Solomon W. Golomb, Shift register sequences, Holden-Day, Inc., San Francisco, Calif.-Cambridge-Amsterdam, 1967. With portions co-authored by Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales. MR 0242575
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, DOI 10.1109/18.761284
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, DOI 10.1109/18.748997
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.
Irving Kaplansky, Fields and rings, 2nd ed., Chicago Lectures in Mathematics, University of Chicago Press, Chicago, Ill.-London, 1972. MR 0349646
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.
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
Akihiro Munemasa, Orthogonal arrays, primitive trinomials, and shift-register sequences, Finite Fields Appl. 4 (1998), no. 3, 252–260. MR 1640769, DOI 10.1006/ffta.1998.0213
Oystein Ore (1934). Contributions to the theory of finite fields. Transactions of the American Mathematical Society 36, 243–274.
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.
Richard Kershner, The number of circles covering a set, Amer. J. Math. 61 (1939), 665–671. MR 43, DOI 10.2307/2371320
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, DOI 10.1007/3-540-44750-4_{4}
Steve Seiden (2001). Can a Computer Proof be Elegant? SIGACT News 60(1), 111–114.
Saunders MacLane and O. F. G. Schilling, Infinite number fields with Noether ideal theories, Amer. J. Math. 61 (1939), 771–782. MR 19, DOI 10.2307/2371335
L. Stickelberger (1897). Über eine neue Eigenschaft der Diskriminanten algebraischer Zahlkörper. Verhandlungen des ersten Internationalen Mathematiker-Kongresses, Zürich, 182–193.
Richard G. Swan, Factorization of polynomials over finite fields, Pacific J. Math. 12 (1962), 1099–1106. MR 144891
Uzi Vishne, Factorization of trinomials over Galois fields of characteristic $2$, Finite Fields Appl. 3 (1997), no. 4, 370–377. MR 1478835, DOI 10.1006/ffta.1997.0191
Neal Zierler, On $x^{n}+x+1$ over $\textrm {GF}(2)$, Information and Control 16 (1970), 502–505. MR 271072
Neal Zierler and John Brillhart, On primitive trinomials $(\textrm {mod}\ 2)$. II, Information and Control 14 (1969), 566–569. MR 244204