Irreducible Pentanomials and their Applications to Effective Implementations of Arithmetic in Binary Fields

• Autorzy: Paszkiewicz A.
• Języki publikacji: EN

Abstrakty

EN

There are only few main classes of irreducible polynomials which are used for designing arithmetic in Galois Fields with characteristic two. These are: irreducible trinomials, pentanomials, all-one polynomials (AOP) and equally spaced irreducible polynomials (ESP). The most critical and time consuming arithmetical operations in Galois Fields are multiplication and modular reduction. A special structure of the modular polynomial defining the arithmetic allows significant speedup of these operations. The best class of binary irreducible polynomials are trinomials, but for about one half of degrees below 30000 an irreducible trinomial does not exist. By exhaustive computation we established that for all degrees n between 4 and 30000 an irreducible pentanomial always exists. Therefore using irreducible pentanomials for defining the arithmetic of Galois Fields have practical interest. In the paper we investigate a function describing the number of binary irreducible pentanomials of a given degree n greater than 3 and study its properties. We also analyze the complexity of a circuit (the number of XOR and AND gates) implementing multiplication in the finite field represented by general irreducible pentanomials.

Słowa kluczowe

EN

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

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

Twórcy

autor

Paszkiewicz A.

• Institute of Telecommunications, Warsaw University of Technology,

Bibliografia

• 1. E. R. Berlekamp: Algebraic coding theory, McGraw-Hill, New York, 1968.
• 2. R. Blahut: Theory and Practice of Error Control Codes, Addison-Wesley Publishing Company, Reading, Massachusetts, Repr. with Correction 1984.
• 3. 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.
• 4. M. Borowski: Application of the Rivest-Chor Cipher for Securing Information in Special Telecommunication Networks, PhD Thesis, MUT, Warszawa 1995 (in polish).
• 5. D. Coppersmith: Fast Evaluation of Logarithms in Fields of Characteristic Two, IEEE Trans. Inform. Theory, vol. IT-30, pp. 587-594, 1984.
• 6. A. J. Menezes et al.: Handbook of Applied Cryptography, CRC Press, Boca Raton, New York 1997.
• 7. A. Paszkiewicz: Some observations concerning irreducible trinomials and pentanomials over Z2, Tatra Mountains Publications 32 (2005), pp. 129-142.
• 8. F. Rodriguez-Henriques, C. K. Koc: Parallel Multipliers Based on Special Irreducible Polynomials, IEEE Trans. On Computer, 52(12), Dec. 2003, pp. 1535-1542.
• 9. M. Sadowski: Analysis and Implementation of the Coppersmith's Algorithm for Finding Discrete Logarithms in GF(2n), Master Thesis, WUT, Warszawa, 2006 (in polish).
• 10. G. Seroussi: Table of Low-Weight Binary Irreducible Polynomials. Hewlett-Packard, HPL, pp. 98-135, August 1998.
• 11. NIST. FIPS 186-2 draft, Digital Signature Standard (DSS), 2000