Mathematics of Computation

Author(s): Joachim von zur Gathen.
Journal: Math. Comp. 72 (2003), 1987-2000.
MSC (2000): Primary 11T06; Secondary 12Y05, 68W30
Posted: February 3, 2003
Retrieve article in: PDF DVI PostScript

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.

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 .
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 .
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 and $x^{8 l \pm 3}+x^k+1$ Irreducible over .
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 .
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 .
Finite Fields and Their Applications 3(4), 370-377. MR 98i:11106
36.: NEAL ZIERLER (1970).
On over .
Information and Control 16, 502-505. MR 42:5955
37.: NEAL ZIERLER & JOHN BRILLHART (1969).
On Primitive Trinomials (Mod ), II.
Information and Control 14, 566-569. MR 39:5521

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS