Evaluation of polynomial modulo in GF(2)I'm new to this forum and I have a question about about modular arithmetics. My background is in computational chemistry and I work now as a software developer. For my work I need to learn about cryptography and I'm reading the book "Cryptography Made Simple" by Nigel P. Smart.In paragraph 1.2 on Finite Fields, the author gives an example of polynomial modulo in F 2 ( x ) / f ( x ) F 2 ( x ) as such: ( 1 + x + x 2 ) ( x + x 3 ) ( mod x 4 + 1 ) = x 2 + 1 However, when I do the evaluation myself I get a different result, which is confirmed by using the PolynomialMod function in Mathematica. I will show the steps I took below. First of all I expand the multiplication and evaluate modulo 2: x 5 + x 4 + 2 x 3 + x 2 + x ( mod 2 ) = x 5 + x 4 + x 2 + xThen: x 5 + x 4 + x 2 + x ( mod x 4 + 1 ) x ( x 4 + 1 ) + x 4 + x 2 ( mod x 4 + 1 ) x ( x 4 + 1 ) + ( x 4 + 1 ) + x 2 − 1 ( mod x 4 + 1 )Which finally results in: ( x + 1 ) ( x 4 + 1 ) + x 2 − 1 ( mod x 4 + 1 ) = x 2 − 1 I put in attachment a screenshot 1 from Mathematica to confirm it matches my result. Initially I thought it was an error in the book, but in a following section the author gives another example: ( x 3 + 1 ) ( x 4 + 1 ) ( mod x 7 + x + 1 ) = x 4 + x 3 + x Again, evaluating the expression manually I obtain: ( x 3 + 1 ) ( x 4 + 1 ) ( mod x 7 + x + 1 ) = x 4 + x 3 − x Which is confirmed once more by Mathematica, see screenshot 2.Does anyone know if there is a reason behind the difference in the results? Any help would be much appreciated.

Question

Evaluation of polynomial modulo in GF(2)I&#039;m new to this forum and I have a question about about modular arithmetics. My background is in computational chemistry and I work now as a software developer. For my work I need to learn about cryptography and I&#039;m reading the book &quot;Cryptography Made Simple&quot; by Nigel P. Smart.In paragraph 1.2 on Finite Fields, the author gives an example of polynomial modulo in             F        2    (  x  )      /    f  (  x  )            F        2    (  x  ) as such:  (  1  +  x  +      x    2    )  (  x  +      x    3    )    (  mod        x    4    +  1  )  =                    x        2            +      1      However, when I do the evaluation myself I get a different result, which is confirmed by using the PolynomialMod function in Mathematica. I will show the steps I took below. First of all I expand the multiplication and evaluate modulo 2:      x    5    +      x    4    +  2      x    3    +      x    2    +  x    (  mod    2  )  =      x    5    +      x    4    +      x    2    +  xThen:      x    5    +      x    4    +      x    2    +  x    (  mod        x    4    +  1  )  x  (      x    4    +  1  )  +      x    4    +      x    2      (  mod        x    4    +  1  )  x  (      x    4    +  1  )  +  (      x    4    +  1  )  +      x    2    −  1    (  mod        x    4    +  1  )Which finally results in:  (  x  +  1  )  (      x    4    +  1  )  +      x    2    −  1    (  mod        x    4    +  1  )  =                    x        2            −      1      I put in attachment a screenshot 1 from Mathematica to confirm it matches my result. Initially I thought it was an error in the book, but in a following section the author gives another example:  (      x    3    +  1  )  (      x    4    +  1  )    (  mod        x    7    +  x  +  1  )  =                    x        4            +              x        3            +      x      Again, evaluating the expression manually I obtain:  (      x    3    +  1  )  (      x    4    +  1  )    (  mod        x    7    +  x  +  1  )  =                    x        4            +              x        3            −      x      Which is confirmed once more by Mathematica, see screenshot 2.Does anyone know if there is a reason behind the difference in the results? Any help would be much appreciated.

Ricardo Weiss · Accepted Answer

Explanation:I believe that there is no (-1), (2) in binary mode GF(2) so, any time you encounter a (-1), (2) put it (1), (0) respectively. Because   1  ≡  −  1    (  mod    2  ) and   2  ≡  0    (  mod    2  )

Kyler Oconnor · Accepted Answer

Step 1There is no difference; for both of the remainder calculations, your result and the solution you compared it to are the same polynomial.What you are missing is that 1 and -1 are the same number when working over GF(2). A common manifestation of this is that addition and subtraction are the same operation when working in any ring of characteristic 2.Step 2In particular, the following equation is true:      x    2    +  1  =      x    2    −  1

Evaluation of polynomial modulo in GF(2). In paragraph 1.2 on Finite Fields, the author gives an example of polynomial modulo in F_2(x)/f(x)F_2(x) as such: (1+x+x^2)(x+x^3) (mod x^4+1)=x^2+1

Answered question

Answer & Explanation

New Questions in Algebra II