# Galois Field in Cryptography¶

## Official Document¶

https://sites.math.washington.edu/~morrow/336_12/papers/juan.pdf

## Explanations¶

### 多项式模的计算方法(Example1)¶

We take the irreducible polynomial modulo $m(p)$ to be $p^8+p^6+p^5+p^1+p^0$.

To calculate $84·13\ (mod\ m(p))$，we go through the following steps:

\begin{align*} 84 · 13 & = ((2^6 + 2^4 + 2^2 ) · (2^3 + 2^2 + 2^0 ))\ (mod\ m(p))\\ & = (2^9 + 2^8 + 2^7 + 2 · 2^6 + 2^5 + 2 · 2^4 + 2^2 )\ (mod\ m(p))\\ & = (2^9 + 2^8 + 2^7 + 2^5 + 2^2 )\ (mod\ m(p)) \end{align*}

Take $2^9 + 2^8 + 2^7 + 2^5 + 2^2$ 's coefficients out as $1110100100$ , $p^8+p^6+p^5+p^1+p^0$ 's as $101100011$, then we use long division to compute the reduced polynomial as follows:

\require{enclose} \begin{array}{rll} 11 && \hbox{$...Quotient$ ($2^1+2^0$) } \\[-3pt] 101100011 \enclose{longdiv}{1110100100}\kern-.2ex \\[-3pt] \underline{101100011\phantom{0}} && \hbox{$Apply\ XOR\ Operation$} \\[-3pt] {101100010}\kern.2ex \\[-3pt] \underline{\phantom{0}101100011} \\[-3pt] \phantom{0}1 && \hbox{$...Remainder$ ($2^0$)} \\[-3pt] \end{array}

which denotes that $84·13\ \div m(p) = 2^1+2^0 ··· 2^0$. This also indicates that $84$ and $13$ are multiplicative inverse pairs to $m(p)$.

### 求逆(Example2)¶

Suppose we don't know the multiplicative inverse of 84 to $m(p)​$. Then to calculate the multiplicative inverse we will use Extended Euclidean Algorithm. Unlike long division, we need to keep track of the auxiliary when we work with Extended Euclidean Algorithm as follows:

Remainder Quotient Auxiliary
$2^8+2^6+2^5+2^1+2^0$ / 0
$2^6+2^4+2^2$ / 1
$2^5+2^4+2^1+2^0$ $2^2$ $2^2$
$2^0$ $2^1+2^0$ $2^3+2^2+2^1$

The first two rows in the Remainder column are always the modulo polynomial followed by the polynomial we wish to invert. The first two rows in the Auxiliary are always 0 and $2^0$ . The remainder and the quotient in row n is then calculated from the division of the remainders in row n − 1 and n − 2 while the auxiliary in row n is given by the sum of the auxiliary in row n − 2 and the product of the quotient in row n and the auxiliary in row n − 1 until the last remainder equals to $2^0$. The final entry in Auxiliary happens to be the multiplicative inverse of the product, thus the multiplicative inverse of 84 is $2^3 + 2^2 + 2^0 = 13$ which agrees with the preceding example.

2018/8/16