Expert: Paul Klarreich - 10/4/2011

Question
Hello!  I am a graduate student in software engineering, and am taking a class in computer security.  We are examining the implementation of various encryption algorithms, and this has me smack up against dealing with polynomials in abstract algebra.

I must admit...I have not worked with algebraic, let alone abstract algebraic math for over 20 years....and I simply can't find anything online to help.  Then I found this site, so I thought I'd give it a shot ;-)

We are looking at manipulating polynomials where the coefficients are in GF(2). For example, right now I am trying to figure out the following:

x6+ x4+x2+x+1 mod x3+x+1

To my understanding, this should be a division operation?  Something like:

x3+x+1 / x6+ x4+x2+x+1 ?

I just *really* need guidance on how to divide these polys. I am sure this is much simpler than I am making it...but all my web searching seem to bump me into very technical treatments of polynomial division....which is way over my abilities.

So, any guidance would be *awesome*.

Thanks for your time,

Andrew

Answer
Questioner:Andrew Troelsen
Country:Minnesota, United States
Category:Advanced Math
Private:No
Subject:Abstract Algebra
Question:

Hello!  I am a graduate student in software engineering, and am taking a class in computer security.  We are examining the implementation of various encryption algorithms, and this has me smack up against dealing with polynomials in abstract algebra.

I must admit...I have not worked with algebraic, let alone abstract algebraic math for over 20 years....and I simply can't find anything online to help.  Then I found this site, so I thought I'd give it a shot ;-)

We are looking at manipulating polynomials where the coefficients are in GF(2). For example, right now I am trying to figure out the following:

x6+x4+x2+x+1 mod x3+x+1

To my understanding, this should be a division operation?  Something like:

x3+x+1 / x6+ x4+x2+x+1 ?

I just *really* need guidance on how to divide these polys. I am sure this is much simpler than I am making it...but all my web searching seem to bump me into very technical treatments of polynomial division....which is way over my abilities.
......................................................
It has been a long time, but this is some 'ring and field theory' stuff -- the ring (or is it a field? I can't recall) of polynomials mod some P(x).

The example itself is fairly routine -- just do the long division:

x3+x+1 into x6+ x4+x2+x+1  and keep the remainder, which will be a polynomial of degree <= 2.
=======================================================
WARNING: USE COURIER FONT TO VIEW THIS -- lots of spaces.
===================================================

x3+0x^2+x+1 ) x6 +  0x5 + x4 + 0x3 +  x2 + x + 1  (

OR, just writing the coefficients:

1  0  1  1 )  1  0  1  0   1   1   1 (  1  0  0 -1 =  x3 - 1  (quotient)
         1  0  1  1
         ------------  subtract
         0  0 -1   1   bring down
         0  0  0   0
         ------------  subtract
         0  -1   1   1   bring down
         0   0   0   0
         ------------  subtract
         -1   1   1   1    bring down
         -1   0  -1  -1
         ----------------  subtract
         1   2   2, which is  1x2 + 2x + 2,
and is your remainder.

Checking the algebra:

(x3 - 1)(x3 + x + 1) = x6 + x4 + x3 - x3 - x - 1 =

x6 + x4         - x - 1
Now add   x2   + 2x + 2
------------------------  equals
x6 + x4 + x2    + x + 1, your original 'dividend' polynomial.

After all that, your result is:

x6 + x4 + x2 + x + 1 == x2 + 2x + 2  mod x3 + x + 1