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 $\mathbb{F}_2(x)/f(x)\mathbb{F}_2(x)$ as such:
$$(1+x+x^2)(x+x^3)\pmod{x^4+1}={\color{red}{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+2x^3+x^2+x\pmod{2}=x^5+x^4+x^2+x$$
Then:
$$x^5+x^4+x^2+x\pmod{x^4+1}$$ $$x(x^4+1)+x^4+x^2\pmod{x^4+1}$$ $$x(x^4+1)+(x^4+1)+x^2-1\pmod{x^4+1}$$
Which finally results in:
$$(x+1)(x^4+1)+x^2-1\pmod{x^4+1}={\color{blue}{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)\pmod{x^7+x+1}={\color{red}{x^4+x^3+x}}$$
Again, evaluating the expression manually I obtain:
$$(x^3+1)(x^4+1)\pmod{x^7+x+1}={\color{blue}{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.
Thank you and apologies for the lengthy post!
Valerio
There 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 $\mathrm{GF}(2)$. A common manifestation of this is that addition and subtraction are the same operation when working in any ring of characteristic $2$.
In particular, the following equation is true: $$ x^2 + 1 = x^2 - 1 $$