0
$\begingroup$

I am trying to understand the AES-256 encryption algorithm as it would be implemented on a gated quantum computer (actually, a simulator), and I am having some trouble understanding the theory behind it. The papers I read start with the ring of polynomials given by $F_2[x]/(1 + x + x^3 + x^6 + x^8)$. What is the significance of the polynomial $1 + x + x^3 + x^6 + x^8$? And how does this relate to $GF(2^8)$?

$\endgroup$
4

1 Answer 1

1
$\begingroup$

To answer the specific question, $F_2[x]/(1 + x + x^3 + x^6 + x^8)$ is isomorphic to $GF(2^8)$. See here for more info.

The polynomial $g(x) = 1 + x + x^3 + x^6 + x^8$ is irreducible over $F_2$, so the quotient is a field. The degree of the polynomial is 8, so it is a degree 8 algebraic extension of $F_2$. In other words, it is $F_{2^8}$.

Elements in $F_2[x]/(g(x))$ are equivalence classes of polynomials modulo $g(x)$.

This is a standard way to construct finite-degree algebraic field extensions.

By the way, I think AES actually has $x^4$ instead of $x^6$ in the polynomial. Not sure if that was a typo in your question or if you read it somewhere.

$\endgroup$
3
  • $\begingroup$ This was very helpful. I've been trying to factor the polynomial unsuccessfully over $𝐹_2$, so it's good to know that it is irreducible. How does one prove that that a specific polynomial is irreducible in $F_2$? I have very little intuition for $𝐹_2$. Also: you are indeed correct, the polynomial has $x^4$ instead of $x^6$. Is there a reason AES chose $1 + x + x^3 + x^4 + x^6$ instead of some other irreducible polynomail? $\endgroup$ Mar 25, 2022 at 7:41
  • 1
    $\begingroup$ @RobertSingleton you can use Rabin's test for irreducibility. The choice of polynomial is just part of the standard. $\endgroup$ Mar 25, 2022 at 8:13
  • 1
    $\begingroup$ You can find how to see that AES polynomial(s) is irreducible here. The selection reason of low weight irreducible it this that reduces the calculation costs in the Finite Field. $\endgroup$
    – kelalaka
    Mar 25, 2022 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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