Skip to main content
3 of 3
edited title
user avatar
user avatar

How to compute the inverse of a polynomial under $GF(2^8)$?

It's well known that AES cryptography algorithm uses Galois Field $GF(2^8)$ multiplication to process the step MixColumn, and each column of the 4x4 matrix on encrypting should multiply the polynomial $3X^3 + X^2 + X + 2$ which is usually notated as an array $\{\tt 0x03, 0x01, 0x01, 0x02\}$, while on decrypting, the matrix should multiply the inverse of the polynominal mentioned above, namely $\texttt{0x0B}X^3 + \texttt{0x0D}X^2 + \texttt{0x09}X + \texttt{0x0E}$ which can also notated as an array $\{\tt 0x0B, 0x0D, 0x09, 0x0E\}$.

Now I wonder If only one polynomial is known, e.g. $\{\tt 0x03, 0x01, 0x01, 0x02\}$, how can I compute its inverse mod $(X^4 + 1)$, namely $\{\tt 0x0B, 0x0D, 0x09, 0x0E\}$, and vice versa.