New Trinomials Xⁿ + X + 1 and Xⁿ + X ² + 1 Irreducible over GF(2)

• Autorzy: Bartosik P. , Paszkiewicz A.
• Języki publikacji: EN

Abstrakty

EN

We extend the limit of investigations for trinomials irreducible over GF(2), having the form Xⁿ + g(X), where deg (g(X)) = 1 or deg (g(X)) = 2 and complete the existing list of irreducible trinomials with that form by a dozen of new elements. We checked all degrees n below 500000 while searching for that polynomials. A large part of computations were performed by a new programming package developed especially for computations in finite fields with characteristic two. This package is a bit more than twice faster than Shoup's NTL package for trinomials and about six times faster than NTL in the case of pentanomials. We also complete the list of Mersenne irreducible polynomials for which a trinomial does not exist by pentanomials and irreducible polynomials which are lexicographicaly youngest.

Słowa kluczowe

EN

finite fields; binary fields; sparse irreducible polynomials over finite fields; primitive polynomials; irreducible trinomials

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2009
• Tom: Vol. 55, No 2
• Strony: 355--361
• Opis fizyczny: Bibliogr. 14 poz., wykr.

Twórcy

autor

Bartosik P.

autor

Paszkiewicz A.

• Institute of Telecommunications, Warsaw University of Technology,

Bibliografia

• 1. P. Bartosik, A. Paszkiewicz: A study on irreducible polynomials of high degrees over GF(2), tools and results, Telecommunication Review, Telecommunication News, 12(2008), pp. 1059-1065, (in polish).
• 2. E. R. Berlekamp: Algebraic coding theory, McGraw-Hill, New York, 1968.
• 3. R. Blahut: Theory and Practice of Error Control Codes, Addison-Wesley Publishing Company, Reading, Massachusetts, Repr. with Correction 1984.
• 4. I. F. Blake, S. Gao, R. J. Lambert: Construction and Distribution Problems for Irreducible Trinomials over Finite Fields; in D. Gollman (ed.) Applications of Finite Fields, Clarendon Press, Oxford (1996) pp. 19-32.
• 5. H. Fredricksen and R. Wisniewski: On trinomials xn + x2 + 1 and x8j±2 + xk + 1 Irreducible over GF(2), Inform, and Control 30, 58-63 (1981).
• 6. S. W. Golomb: Shift Register Sequences, Holden Day, San Francisco, 1967, Reprinted by Aegean Park.
• 7. A. J. Menezes et al.: Handbook of Applied Cryptography, CRC Press, Boca Raton, New York 1997.
• 8. A. Paszkiewicz: Some observations concerning irreducible trinomials and pentanomials over Z2, Tatra Mountains Publications 32 (2005), pp. 129-142.
• 9. A. Paszkiewicz: On some properties of irreducible trinomials over small number fields, (a paper being recently in press).
• 10. A. Paszkiewicz: Irreducible pentanomials and their applications to effective implementations of arithmetic in binary fields, (this issue).
• 11. G. Seroussi: Table of Low-Weight Binary Irreducible Polynomials. Hewlett-Packard, HPL, pp. 98-135, August 1998.
• 12. R. G. Swan: Factorization of polynomials over finie fields, Pacific J. Math. 12, 1099-1106.
• 13. N. Zierler: On xn + x + 1 over GF(2), Inform, and Control 16, 502+505 (1970).
• 14. NIST. FIPS 186-2 draft. Digital Signature Standard (DSS), 2000.