2
$\begingroup$

I am doing some self-study in the area of Cryptography. I am using the Third Edition of the book "Cryptography Theory and Practice" by Douglas R. Stinson. Based upon the information on page 105, in the field $F_{2^8}$, I believe the following two polynomials are multiplicative inverses.

$x^6 + x^4 + x + 1$
$x^7 + x^6 + x^3 + x$

If they are and I multiply them together, I should get the irreducible polynomial for the field right? Here is what I get when I multiply the two polynomials together in $F_{2^8}$. \begin{eqnarray*} (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x) &=& (x^6)(x^7 + x^6 + x^3 + x) + \\ && (x^4)(x^7 + x^6 + x^3 + x) \\ &+& (x + 1)(x^7 + x^6 + x^3 + x) \\ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x) &=& (x^{13} + x^{12} + x^9 + x^7) + \\ && (x^{11} + x^{10} + x^7 + x^5) \\ &+& (x + 1)(x^7 + x^6 + x^3 + x) \\ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x) &=& (x^{13} + x^{12} + x^9 + x^7) + \\ && (x^{11} + x^{10} + x^7 + x^5) + \\ && (x^8 + x^7 + x^4 + x^2) + (x^7 + x^6 + x^3 + x) \\ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x) &=& x^{13} + x^{12} + x^{11} + x^9 + x^{10} + x^5 + \\ && x^8 + x^7 + x^4 + x^2 + x^7 + x^6 + x^3 + x \\ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x) &=& x^{13} + x^{12} + x^{11} + \\ && x^{10} + x^9 + x^8 + x^6 + x^5 + x^3 + x \\ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x) &=& x^{5} + x^{4} + x^{3} + x^{2} + x^9 + x^8 + x^6 + x^5 + x^3 + x \\ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x) &=& x^{4} + x^{3} + x^{2} + x^9 + x^8 + x^6 + x^3 + x \\ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x) &=& x^{4} + x^{3} + x^{2} + x + x^8 + x^6 + x^3 + x \\ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x) &=& x^8 + x^6 + x^4 + x^2 \\ \end{eqnarray*} This is not the irreducible polynomial. What am I missing?

Thanks

Bob

$\endgroup$
  • 2
    $\begingroup$ You are not correctly reducing the polynomial after multiplication. To get a polynomial in $\mathbb{F}_{2^8}$ from one with terms of degree of eight or more you have to divide it by the irreducible polynomial (you can't just mod 8 the terms degrees). $\endgroup$ – puzzlepalace Mar 20 '17 at 21:17
  • $\begingroup$ You have reduce the polynomial in step 6 using "long division modulo 2" as shown here. $\endgroup$ – Occams_Trimmer Mar 20 '17 at 21:29
  • $\begingroup$ "If they are and I multiply them together, I should get the irreducible polynomial for the field right?" Wrong. $\endgroup$ – fkraiem Mar 21 '17 at 7:00
  • 3
    $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$ – fkraiem Mar 21 '17 at 7:01
2
$\begingroup$

In the page $104$ you can see: $$F_{2^8}=\frac{Z_2[x]}{x^8+x^4+x^3+x+1}.$$ this means that irreducible polynomial that generate the $F_{2^8}$ is $x^8+x^4+x^3+x+1$. so, in multiplications, you should note that $x^8=-x^4-x^3-x-1=x^4+x^3+x+1$. Therefore $x^{8+i}=x^8\cdot x^i=x^{4+i}+x^{3+i}+x^{1+i}+x^i$.

| improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.