Polynomials and Linear Algebra

Polynomial multiplication modulo  can be written as a multiplication of a matrix in  with a vector in .

Product  can be written as:

Since each  is a polynomial of degree less than  it can be thought of as a vector in . The multiplication  can therefore be seen as a linear combination (with weights  ) of these  vectors, and thus can be represented as a matrix-vector multiplication.

For example, the product

can be written as

When treating polynomials  as vectors and matrices, it will be convenient to use the following notation  and  :

Here are some example matrices  for a polynomial  for several  's of degree 4 .

The only two polynomials  for which  holds are