Using modular polynomial arithmetic, perform the following multiplication over P

Michelle Arroyo

Michelle Arroyo

Answered question

2021-11-09

Using modular polynomial arithmetic, perform the following multiplication over GF(23) with the irreducible polynomial x3+x+1.
Convert the final result to decimal.
111×110

Answer & Explanation

Walker Funk

Walker Funk

Beginner2021-11-10Added 13 answers

Irreducible polynomial is a polynomial that cannot be factorized into lower degree polynomials For the set of all polynomials over GF(2), let's now consider polynomial arithmetic modulo the irreducible polynomial x3+x+1.
When an algebric operation results in a polynomial whose degree equals or exceeds that of the irreducible polynomial, we will take for our result the remainder modulo the irreducible polynomial.
For example,
(x2+x+1)×(x2+1)bmod(x3+x+1)
=(x4+x3+x2)+(x2+x+1)bmod(x3+x+1)
=(x4+x3+x+1)bmod(x3+x+1)
=x2x
=x2+x
Since 1+1=0 in GF(2). That's what caused the x2 term to disappear in the second expression on the right hand side of the equality sign.
With multiplications modulo (x3+x+1), we have only the following eight polynomials in the set of polynomials over GF(2):
0
1
x
x2
x+1
x2+1
x2+2
x2+x+1
We will refer to this set as GF(23) where the exponent of 2, which in this case is 3, is the degree of the modulus polynomial.
We can think of xi as being merely a place-holder for a bit i.e., we can think of the polynomials as bit strings corresponding to the coefficients that can only be 0 or 1, each power of x representing a specific position in a bit string. So the 23 polynomials of GF(23) can therefore be represented by the bit strings:
0----000
1-----001
x-----010
x2-----100
x+1-----011
x2+1------101
x2+x----110
x2+x+1------111
If we wish, we can give a decimal representation to each of the above bit patterns. The decimal values between 0 and 7, both limits inclusive, would have to obey the addition and multiplication rules corresponding to the underlying finite field.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?