World Journal of Engineering Research and Technology

Ahmed Asimi*

ABSTRACT

In cryptography, more particularly for the linear Feedback Shift Register (LFSR) of length n, the irreducibility of the polynomial xn+x+1 over F2 is very important to generate a binary pseudorandom sequence corresponding to the nonzero initial state vector derived from the secret key, because it is well known[9] that any LFSR of length n whose characteristic polynomial is a primitive polynomial over F2 will generate a periodic sequence of period 2n 1 for any nonzero initial state vector. In this paper, we start with the study of the reducibility and the parity of the number of irreducible factors of the polynomial P(x) = xn+x+1 in F2[x]. We show that 1) If n = 2 or n = 3, the polynomial P(x) is irreducible over F2; 2) If n _ 2 mod 3 and n > 3, the polynomial P(x) is reducible over F2; 3) If n _ 0 or 2 or 3 or 5 mod 8 and n > 3, the polynomial P(x) has an even number of irreducible factors over F2, then P(x) is reducible over F2; 4) If n _ 1 or 4 or 6 or 7 or 9 or 15 or 22 mod 24 and n > 3 then P(x) has an odd number of irreducible factors over F2; 5) If P(x) = xn + x + 1 is irreducible over F2 then n _ 1 or 4 or 6 or 7 or 9 or 15 or 22 mod 24 and n > 3. The converse is not true. We close this paper by proposing two programs, in Python language, to build irreducible and primitive polynomials, P(x) = xn + x + 1, over F2. For example, we build all irreducible polynomials, xn +x+1, over F2 of degree at less greater than 1000 and primitive polynomials of

[Full Text Article] [Download Certificate]