---
title: Galois field (Finite Field)
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# Galois field (Finite Field)
- 定義
- $Z_p$ with prime p
- 表示為 $GF(p)$
- 若表示為 $GF(p^n)$ 則跟多項式有關，請見下面章節

# Polynomial Arithmetic
$\displaystyle f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0=\sum_{i=0}^{n} a_ix^i$

## with coefficients mod p
Coefficients are in $GF(p^n)$
$p$ means coefficients are in $Z_p$
$n$ means there are $n$ terms ($x^{n-1}+x^{n-2}+...x+c$)

for example, $GF(2^3)$ has these items:
- $0x^2+0x+0$
- $0x^2+0x+1$
- $0x^2+1x+0$
- $0x^2+1x+1$
- $1x^2+0x+0$
- $1x^2+0x+1$
- $1x^2+1x+0$
- $1x^2+1x+1$

for example
let $f(x)=x^3+x^2$ and $g(x)=x^2+x+1$
- ordinary
- $f(x)+g(x)=x^3+2x^2+x+1$
- $f(x)\times g(x)=x^5+2x^4+2x^3+x^2$
- in $GF(2^6)$
- $f(x)+g(x)=x^3+x+1$
- $f(x)\times g(x)=x^5+x^2$

## Polynomial Division
$\begin{split}&f(x)=q(x)g(x)+r(x)\\
&\to r(x)=f(x)\ mod\ g(x)
\end{split}$

- If have no remainder
- say $g(x)$ **divides** $f(x)$
- If $g(x)$ has no divisors other than itself and 1
- say it is **irreducible** (or prime) polynomial

## Polynomial Inverse

如此一來，只要找到是 prime 的 $n$ 階方程式
就能計算 $f(x)$ 的乘法反元素 $f(x)\in GF(2^n)$
因為元素跟反元素為 1-1 mapping，故可以用此性質作為替換的依據
$GF(2^8)$ 應用在 AES，用來當作 sbox