## CIS 628 Introduction to Cryptography## Barbara Nostrand, Ph.D.## Electrical Engineering and Computer Science |

If provided with an irreducible polynomial, how can you prove that it is indeed irreducible?

For E.g. : the polynomial *x*^{8} + *x*^{4} + *x*^{3} + *x* + 1 (Hex: x'11B')

There are several of ways to prove irreducibility. The first is to try as factors
all polynomials of degree up to *n*/2:

The second is to try as factors all irreducible polynomials of degree up to *n*/2.
For *n*=8 these are:

*x*

*x* + 1

*x*^{2} + *x* + 1

*x*^{3} + *x* + 1

*x*^{3} + *x*^{2} + 1

*x*^{4} + *x* + 1

*x*^{4} + *x*^{3} + 1

*x*^{4} + *x*^{3} + *x*^{2} + *x* + 1

You can short-cut this by using the fact that * f(x)* is a divisor of

Another way to prove irreducibility is to count the number of distinct
irreducible factors. Create the square matrix *Q* of coefficients of
even powers of α reduced modulo the polynomial:
α^{(2*i)}, 0 ≤ i ≤ 7 (which you have already computed):

[1 0 0 0 0 0 0 0] <--> αThen the number of distinct irreducible factors of Q is the same as the dimension of the nullspace of^{0}[0 0 1 0 0 0 0 0] <--> α^{2}[0 0 0 0 1 0 0 0] <--> α^{4}Q= [0 0 0 0 0 0 1 0] <--> α^{6}[1 1 0 1 1 0 0 0] <--> α^{8}[0 0 1 1 0 1 1 0] <--> α^{10}[1 1 0 1 0 1 0 1] <--> α^{12}[0 1 0 1 1 0 0 1] <--> α^{14}

[0 0 0 0 0 0 0 0] [0 1 1 0 0 0 0 0] [0 0 1 0 1 0 0 0]This is a standard thing to do in linear algebra. It turns out that the left nullspace has dimension 1, generated by the vector:Q+ I = [0 0 0 1 0 0 1 0]. [1 1 0 1 0 0 0 0] [0 0 1 1 0 0 1 0] [1 1 0 1 0 1 1 1] [0 1 0 1 1 0 0 0]

[1 0 0 0 0 0 0 0].That implies that

Take whichever approach suits your taste.

Last modified: 2008 MAR 24 bnostran@syr.edu