12-degree prime extension field tower

# はじめに（Introduction）

BLS12-381で使用されている、12次素拡大体タワー（12-degree prime extension field tower）の計算式を求めてみようと思います。

簡単にいうと、[Pairing over BLS12-381, Part 1: Fields](https://research.nccgroup.com/2020/07/06/pairing-over-bls12-381-part-1-fields/)に書かれている実装方法の式が気になったので解いてみたというものです。

ちなみに、「12次素拡大体タワー」という訳は私が勝手に訳したものなので、正確な訳し方を知っていたら教えてください。

# 体（Field）

体（Field）について確認してみます。
※：本投稿では体の厳密な証明まではしません。

$\ a,b,c\ $は$\ S\ $に含まれるときに以下が成り立つ。

- (**A1**)$\ a+b\ $も$\ S\ $に含まれる。＜加法に閉じている＞
- (**A2**)$\ a+(b+c)=(a+b)+c\ $が成り立つ。＜加法の結合法則＞
- (**A3**)$\ a+0=0+a\ $が成り立つような元$0$が存在する。＜加法単位元＞
- (**A4**)$\ a+(-a)=(-a)+a=0\ $が成り立つような元$-a$が存在する。＜加法逆元＞
- (**A5**)$\ a+b=b+a\ $が成り立つ。＜加法の交換法則＞
- (**M1**)$\ a\times b\ $も$\ S\ $に含まれる。＜乗法に閉じている＞
- (**M2**)$\ a\times (b\times c)=(a\times b)\times c\ $が成り立つ。＜乗法の結合法則＞
- (**M3**)$\ a\times (b+c)=a\times b+a\times c\ $と$\ (a+b)\times c=a\times c+b\times c\ $が成り立つ。＜乗法と加法の分配法則＞
- (**M4**)$\ a\times b=b\times a\ $が成り立つ。＜乗法の交換法則＞
- (**M5**)$\ a\times 1=1\times a\ $が成り立つような元$1$が存在する。＜乗法単位元＞
- (**M6**)$\ a\times b=0\ $ならば、$\ a=0\ $または$\ b=0\ $である。＜零因子＞
- (**M7**)$\ a\ne 0\ $の時、$\ a\times a^{-1}=a^{-1}\times a=1 \ $となる元$\ a^{-1}\ $が存在する。＜乗法逆元＞


「[cryptography-and-network-security_-principles-and-practice-7th-global-edition.pdf](http://www.cs.vsb.cz/ochodkova/courses/kpb/cryptography-and-network-security_-principles-and-practice-7th-global-edition.pdf)」のP.147を参照

# 12次素拡大体タワー（12-degree prime extension field tower）

$F_{q^{1}},F_{q^{2}},F_{q^{6}},F_{q^{12}}$を作成していきます。
以下の図のような構成となっているので、タワー（tower）と呼んでいると思われます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/16920032-349e-60bb-c622-d2f46f996e1a.png)

[ここによれば](https://github.com/zcash/librustzcash/blob/6e0364cd42a2b3d2b958a54771ef51a8db79dd29/pairing/src/bls12_381/README.md)、拡大体タワーは以下のように構成されています：
1. $F_{q^2}$ は、$F_q(u)/(u^2-\beta)$ 、$\beta=-1$として構成されています。
1. $F_{q^6}$ は、$F_{q^2}(v)/(v^3-\xi)$ 、$\xi=u+1$として構成されています。
1. $F_{q^{12}}$ は、$F_{q^6}(w)/(w^2-\gamma)$ 、$\gamma=v\$ として構成されています。

※：宙ぶらりんなブランチの資料なので本家はどこなのか・・・

# Fq1

$F_{q^{1}}$は、剰余演算です。
位数（法）が素数であれば、乗法逆元を必ず持ちます。
BLS12-381の場合、位数は以下となります。
$p=\texttt{0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab}$
したがって、$F_{q^{1}}=\\{0,1,2,\cdots,p-2,p-1\\}$となります。
$a_0,b_0 \in F_{q^{1}}$とすると、加法、減法、乗法、乗法逆元は以下となります。
- （$+$）$\ a_0+b_0\ \mod p$
- （$-$）$\ a_0-b_0\ \mod p$
- （$\times$）$\ a_0\times b_0\ \mod p\ $
- （inv）$\ a_0^{-1}\equiv a_0^{p-2} \mod p$

※：invは乗法逆元です。
ここでは、乗法逆元をフェルマーの小定理を使っていますが、
元のBlogではバイナリ拡張ユークリッドの互除法（Binary Extended Euclidean Algorithm）を使って導いています。
プログラムでは除算のコストが高いですが、二分の一はビットシフトを使えばコストを低くできるので、除算なし（ビットシフトだけ）で実現すると計算コストがかなり抑えられるはずです。

https://ja.wikipedia.org/wiki/%E5%89%B0%E4%BD%99%E6%BC%94%E7%AE%97

https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86

https://en.wikipedia.org/wiki/Binary_GCD_algorithm

# Fq2

$F_{q^2}$ は、$F_{q^1}(u)/(u^2-\beta)$ 、$\beta=-1$として構成されています。

これは$F_{q^1}(u)=\alpha_0+\alpha_1u+\alpha_2u^2+\cdots$のような関数を$u^2+1$で割った余りを考えます。
$u^2+1$で割った余りなので、１次式が出てきます。

$a_0,a_1,b_0,b_1 \in F_{q^1}$としたとき、$a_0+a_1u\ ,\ b_0+b_1u \in F_{q^2}\ $となります。
$F_{q^2}$ は、$F_{q^1}$ を２つ持つので、$F_{q^2} (a_1,a_0)$ のようにあらわす事にします。

$a_0,a_1,b_0,b_1 \in F_{q^{1}}$とすると、加法、減法、乗法、乗法逆元、`mul_nonres`は以下となります。
- （$+$）$\ F_{q^2} (a_1,a_0)+F_{q^2} (b_1,b_0) = F_{q^2} (a_1+b_1,a_0+b_0)$
- （$-$）$\ F_{q^2} (a_1,a_0)-F_{q^2} (b_1,b_0) = F_{q^2} (a_1-b_1,a_0-b_0)$
- （$\times$）$\ F_{q^2} (a_1,a_0)\times F_{q^2} (b_1,b_0) = F_{q^2} (a_0b_1+a_1b_0,a_0b_0-a_1b_1)$
- （inv）$\ F_{q^2} (a_1,a_0)^{-1} = F_{q^2} (-a_1\times \text{factor},a_0\times \text{factor})\ $
     - $\text{factor}=(a_0a_0+a_1a_1)^{-1}$
- （mul_nonres）$(u+1)\times \ F_{q^2} (a_1,a_0) = F_{q^2} (a_0+a_1,a_0-a_1)$

### 単位元

```math
\begin{align*}
F_{q^2}(0,1) &=1 + 0u =1 \\
F_{q^2}(0,0) &=0 + 0u = 0 \\
\end{align*}
```

### 加法（＋）

```math
\begin{align*}
F_{q^2} (a_0,a_1)+F_{q^2} (b_0,b_1) &=a_0 + a_1u+b_0 + b_1u \\
& =(a_0+b_0)+(a_1+b_1)u \\
& =F_{q^2} (a_1+b_1,a_0+b_0)\\
\end{align*}
```

### 減法（－）

```math
\begin{align*}
\ F_{q^2} (a_0,a_1)-F_{q^2} (b_0,b_1) &=a_0 + a_1u-(b_0 + b_1u) \\
& =(a_0-b_0)+(a_1-b_1)u \\
& =F_{q^2} (a_1-b_1,a_0-b_0)\\
\end{align*}
```

### 乗法（×）


```math
\begin{align*}
F_{q^2} (a_0,a_1)\times F_{q^2} (b_0,b_1) &= (a_0 + a_1u)\times(b_0 + b_1u)\\
&=a_0b_0+a_0b_1u+a_1b_0u+a_1b_1u^2\\
\end{align*}
```

$u^2$の項があるので$u^2+1$で割る事が出来ます。
多項式の除算は以下のようになるので、余りだけを考えるならば、$u^2=-1$を代入すれば良いわけです。
$F(u)=G(u)(u^2+1)+c_0+c_1u$
※：実直に多項式の割り算をしてみても、結果は同じはずです。

```math
\begin{align*}
F_{q^2} (a_0,a_1)\times F_{q^2} (b_0,b_1) &= a_0b_0+a_0b_1u+a_1b_0u+a_1b_1u^2 \\
&= a_0b_0+a_0b_1u+a_1b_0u+a_1b_1(-1)\\
&=(a_0b_0-a_1b_1)+(a_0b_1+a_1b_0)u\\
\end{align*}
```

### 乗法逆元(inv)
乗法が$1=F_{q^2} (0,1)$となる$F_{q^2} (b_0,b_1)$を考えます。

```math
\begin{align*}
F_{q^2} (a_0,a_1)\times F_{q^2} (b_0,b_1) &=(a_0b_0-a_1b_1)+(a_0b_1+a_1b_0)u \\
a_0b_0-a_1b_1&=1\qquad\cdots(1)\\
a_0b_1+a_1b_0&=0\qquad\cdots(2)\\
(1)\times a_0+(2)\times a_1&\text{を計算します。}\\
a_0a_0b_0-a_0a_1b_1+a_0a_1b_1+a_1a_1b_0&=a_0\\
(a_0a_0+a_1a_1)b_0&=a_0\\
b_0&=\frac{a_0}{a_0a_0+a_1a_1}\\
(2)\text{に代入します。}&\\
a_0b_1+a_1\frac{a_0}{a_0a_0+a_1a_1}&=0\\
b_1&=\frac{-a_1}{a_0a_0+a_1a_1}\\
\text{factor}&=(a_0a_0+a_1a_1)^{-1}\\
F_{q^2} (a_1,a_0)^{-1} &= F_{q^2} (-a_1\times \text{factor},a_0\times \text{factor})\\
\end{align*}
```


### `mul_nonres`
この計算式は後で使用するので先に用意しておきます。

```math
\begin{align*}
(u+1)\times \ F_{q^2} (a_1,a_0)&=(u+1)(a_0+a_1u) \\
&=a_0u+a_1u^2+a_0+a_1u \\
&u^2=-1\text{を代入}\\
&=a_0u+a_1(-1)+a_0+a_1u \\
&=(a_0-a_1)+(a_0+a_1)u \\
&=F_{q^2} (a_0+a_1,a_0-a_1) \\
\end{align*}
```

# Fq6

$F_{q^6}$ は、$F_{q^2}(v)/(v^3-\xi)$ 、$\xi=u+1$として構成されています。

今回は$v^3$という２次式の余りを考えるので２次式が余りとなります。

$a_0,a_1,a_2,b_0,b_1,b_2 \in F_{q^2}$としたとき、$a_0+a_1v+a_2v^2\ ,\ b_0+b_1v+b_2v^2 \in F_{q^6}\ $となります。
$F_{q^6}$ は、$F_{q^2}$ を３つ持つので、$F_{q^6} (a_2,a_1,a_0)$ のようにあらわす事にします。

$a_0,a_1,a_2,b_0,b_1,b_2 \in F_{q^{2}}$とすると、加法、減法、乗法、乗法逆元、`mul_nonres`は以下となります。
- （$+$）$\ F_{q^6} (a_2,a_1,a_0)+F_{q^6} (b_2,b_1,b_0) = F_{q^6} (a_2+b_2,a_1+b_1,a_0+b_0)$
- （$-$）$\ F_{q^6} (a_2,a_1,a_0)-F_{q^6} (b_2,b_1,b_0) = F_{q^6} (a_2-b_2,a_1-b_1,a_0-b_0)$
- （$\times$）$\ F_{q^6} (a_2,a_1,a_0)\times F_{q^6} (b_2,b_1,b_0) = F_{q^6} (t_2,t_1+t_4,t_0+t_3)$
    - $t_0= a_0b_0$
    - $t_1= a_0b_1+a_1b_0$
    - $t_2= a_0b_2+a_1b_1+a_2b_0$
    - $t_3= \text{mul_nonres}(a_1b_2+a_2b_1)\ $
    - $t_4= \text{mul_nonres}(a_2b_2)\ $
- （inv）$\ F_{q^6} (a_2,a_1,a_0)^{-1} = F_{q^6} (t_2\times \text{factor},t_1\times \text{factor},t_0\times \text{factor})\ $
    - $t_0= a_0a_0 - \text{mul_nonres}(a_1a_2)$
    - $t_1= \text{mul_nonres}(a_2a_2)-a_0a_1$
    - $t_2= a_1a_1-a_0a_2$
    - $\text{factor}= (a_0t_o+\text{mul_nonres}(a_2t_1)+\text{mul_nonres}(a_1t_2))^{-1}$
- （mul_nonres）$v\times \ F_{q^6} (a_2,a_1,a_0) = F_{q^6} (a_1,a_0,\text{mul_nonres}(a_2))$

### 単位元

```math
\begin{align*}
F_{q^6}(0,0,1) &=1 + 0v + 0v^2 =1 \\
F_{q^6}(0,0,0) &=0 + 0v + 0v^2 =0 \\
\end{align*}
```

### 加法（＋）

```math
\begin{align*}
F_{q^6} (a_0,a_1,a_2)+F_{q^6}(b_0,b_1,b_2)&=a_0+a_1v+a_2v^2+b_0+b_1v+b_2v^2 \\
&=(a_0+b_0) + (a_1+b_1)v+(a_2+b_2)v^2 \\
&=F_{q^6} (a_2+b_2,a_1+b_1,a_0+b_0) \\
\end{align*}
```

### 減法（－）

```math
\begin{align*}
F_{q^6} (a_0,a_1,a_2)-F_{q^6}(b_0,b_1,b_2)&=a_0+a_1v+a_2v^2-(b_0+b_1v+b_2v^2) \\
&=(a_0-b_0) + (a_1-b_1)v+(a_2-b_2)v^2 \\
&=F_{q^6} (a_2-b_2,a_1-b_1,a_0-b_0) \\
\end{align*}
```

### 乗法（×）


```math
\begin{align*}
F_{q^6} (a_0,a_1,a_2)\times F_{q^2} (b_0,b_1,b_2) = &(a_0+a_1v+a_2v^2)\times(b_0+b_1v+b_2v^2) \\
=&a_0b_0+a_0b_1v+a_0b_2v^2\\
&+a_1b_0v+a_1b_1v^2+a_1b_2v^3\\
&+a_2b_0v^2+a_2b_1v^3+a_2b_2v^4 \\
\end{align*}
```

$v^3,v^4$の項があるので、$v^3-(u+1)$で割る事ができます。
さきほどと同様に、$v^3=u+1$を代入します。

```math
\begin{align*}
F_{q^6} (a_0,a_1,a_2)\times F_{q^2} (b_0,b_1,b_2)=&a_0b_0+a_0b_1v+a_0b_2v^2\\
&+a_1b_0v+a_1b_1v^2+a_1b_2v^3\\
&+a_2b_0v^2+a_2b_1v^3+a_2b_2v^4 \\
=&a_0b_0+a_0b_1v+a_0b_2v^2 \\
&+a_1b_0v+a_1b_1v^2+(u+1)a_1b_2\\
&+a_2b_0v^2+(u+1)a_2b_1+(u+1)a_2b_2v \\
=&\{a_0b_0+(u+1)a_1b_2+(u+1)a_2b_1\}\\
&+\{a_0b_1+a_1b_0+(u+1)a_2b_2\}v\\
&+(a_0b_2+a_1b_1+a_2b_0)v^2 \\
=&\{a_0b_0+(u+1)(a_1b_2+a_2b_1)\} \\
&+\{a_0b_1+a_1b_0+(u+1)a_2b_2\}v \\
&+(a_0b_2+a_1b_1+a_2b_0)v^2 \\
\end{align*}
```


$(u+1)\times F_{q^2}\ $は、$F_{q^2}$の`mul_nonres`なので、以下のようにあらわせます。

```math
\begin{align*}
F_{q^6} (a_0,a_1,a_2)\times F_{q^2} (b_0,b_1,b_2)=&\{a_0b_0+\text{mul_nonres}(a_1b_2+a_2b_1)\}\\
&+\{a_0b_1+a_1b_0+\text{mul_nonres}(a_2b_2)\}v\\
&+(a_0b_2+a_1b_1+a_2b_0)v^2
\end{align*}
```

$t_0,t_1,t_2,t_3,t_4$を以下のようにおきます。

```math
\begin{align*}
t_0=& a_0b_0 \\
t_1=& a_0b_1+a_1b_0 \\
t_2=& a_0b_2+a_1b_1+a_2b_0 \\
t_3=& \text{mul_nonres}(a_1b_2+a_2b_1)\\
t_4=& \text{mul_nonres}(a_2b_2)\\
F_{q^6} (a_0,a_1,a_2)\times F_{q^2} (b_0,b_1,b_2)=&(t_0+t_3)+(t_1+t_4)v+(t_2)v^2\\
=& F_{q^6} (t_2,t_1+t_4,t_0+t_3)
\end{align*}
```

となります。

### 乗法逆元(inv)
乗法が$1=F_{q^6} (0,0,1)$となる$F_{q^6} (b_0,b_1,b_2)$を考えます。

```math
\begin{align*}
F_{q^6} (a_0,a_1,a_2)\times F_{q^2} (b_0,b_1,b_2)=&a_0b_0+(u+1)a_1b_2+(u+1)a_2b_1\\
&+\{a_0b_1+a_1b_0+(u+1)a_2b_2\}v \\
&+(a_0b_2+a_1b_1+a_2b_0)v^2 \\
\end{align*}
```

各係数が以下となります。

```math
\begin{align*}
a_0b_0+(u+1)a_1b_2+(u+1)a_2b_1&=1&\qquad\cdots(1) \\
a_0b_1+a_1b_0+(u+1)a_2b_2&=0&\qquad\cdots(2) \\
a_0b_2+a_1b_1+a_2b_0&=0&\qquad\cdots(3) \\
\end{align*}
```


$b_0$を消します。

```math
\begin{align*}
a_2\times(2)-a_1\times (3)&\\
a_0a_2b_1+a_1a_2b_0+(u+1)a_2a_2b_2-(a_0a_1b_2+a_1a_1b_1+a_1a_2b_0)=&0\\
(a_0a_2-a_1a_1)b_1+\{(u+1)a_2a_2-a_0a_1\}b_2=&0\\
(a_0a_2-a_1a_1)b_1+\{\text{mul_nonres}(a_2a_2)-a_0a_1\}b_2=&0&\qquad\cdots(4)\\
\\
a_2\times(1)-a_0\times (3)&\\
a_0a_2b_0+(u+1)a_1a_2b_2+(u+1)a_2a_2b_1-(a_0a_0b_2+a_0a_1b_1+a_0a_2b_0)=&a_2\\
\{(u+1)a_2a_2-a_0a_1\}b_1+\{(u+1)a_1a_2-a_0a_0\}b_2=&a_2\\
\{\text{mul_nonres}(a_2a_2)-a_0a_1\}b_1+\{\text{mul_nonres}(a_1a_2)-a_0a_0\}b_2=&a_2&\qquad\cdots(5)\\
\end{align*}
```

ここで、$t_0,t_1,t_2$を以下のようにおきます。

```math
\begin{align*}
t_0=& a_0a_0 - \text{mul_nonres}(a_1a_2)\\
t_1=& \text{mul_nonres}(a_2a_2)-a_0a_1\\
t_2=& a_1a_1-a_0a_2\\
\end{align*}
```

```math
\begin{align*}
-t_2b_1+t_1b_2&=0&\qquad\cdots(4')\\
t_1b_1-t_0b_2&=a_2&\qquad\cdots(5')\\
\end{align*}
```

$b_2$を求めます。

```math
\begin{align*}
t_1\times (4') + t_2\times (5')& \\
-t_1t_2b_1+t_1t_1b_2+t_1t_2b_1-t_0t_2b_2=&a_2t_2\\
(t_1t_1-t_0t_2)b_2=&a_2t_2\\
b_2=&\frac{a_2}{t_1t_1-t_0t_2}t_2\\
\end{align*}
```

$b_2$を$(4')$に代入して、$b_1$を求めます。

```math
\begin{align*}
-t_2b_1+t_1\frac{a_2}{t_1t_1-t_0t_2}t_2=&0 \\
b_1=&\frac{a_2}{t_1t_1-t_0t_2}t_1 \\
\\
\end{align*}
```

$b_2,b_1$を$(3)$に代入して、$b_0$を求めます。

```math
\begin{align*}
a_0\frac{a_2}{t_1t_1-t_0t_2}t_2+a_1\frac{a_2}{t_1t_1-t_0t_2}t_1+a_2b_0=&0\\
b_0=&\frac{a_2}{t_1t_1-t_0t_2}\times \frac{-a_0t_2-a_1t_1}{a_2}\\
\\
\end{align*}
```

分子の$t_1,t_2$を戻します。

```math
\begin{align*}
b_0=&\frac{a_2}{t_1t_1-t_0t_2}\times \frac{-a_0(a_1a_1-a_0a_2)-a_1(\text{mul_nonres}(a_2a_2)-a_0a_1)}{a_2}\\
=&\frac{a_2}{t_1t_1-t_0t_2}\times \frac{-a_0a_1a_1+a_0a_0a_2-\text{mul_nonres}(a_1a_2a_2)+a_0a_1a_1}{a_2}\\
=&\frac{a_2}{t_1t_1-t_0t_2}\times \frac{a_0a_0a_2-\text{mul_nonres}(a_1a_2a_2)}{a_2}\\
=&\frac{a_2}{t_1t_1-t_0t_2}\times (a_0a_0-\text{mul_nonres}(a_1a_2))\\
=&\frac{a_2}{t_1t_1-t_0t_2}t_0\\
\end{align*}
```

共通(`factor`)の$\frac{a_2}{t_1t_1-t_0t_2}$を整理します。
分母の$t_1t_1-t_0t_2$の$t_0,t_1,t_2$を戻します、`mul_nonres`も$(u+1)$に戻します。

```math
\begin{align*}
t_1t_1-t_0t_2=&(\text{mul_nonres}(a_2a_2)-a_0a_1)(\text{mul_nonres}(a_2a_2)-a_0a_1) \\
&-(a_0a_0 - \text{mul_nonres}(a_1a_2))(a_1a_1-a_0a_2) \\
=&((u+1)a_2a_2-a_0a_1)((u+1)a_2a_2-a_0a_1)-(a_0a_0 - (u+1)a_1a_2)(a_1a_1-a_0a_2) \\
=&(u+1)(u+1)a_2a_2a_2a_2-(u+1)a_0a_1a_2a_2-(u+1)a_0a_1a_2a_2+a_0a_0a_1a_1 \\
&-a_0a_0a_1a_1+a_0a_0a_0a_2+(u+1)a_1a_1a_1a_2-(u+1)a_0a_1a_2a_2 \\
=&a_2\{(u+1)(u+1)a_2a_2a_2-(u+1)a_0a_1a_2-(u+1)a_0a_1a_2 \\
&+a_0a_0a_0+(u+1)a_1a_1a_1-(u+1)a_0a_1a_2\}\\
=&a_2[a_0\{a_0a_0-(u+1)a_1a_2\}+(u+1)a_2\{(u+1)a_2a_2-a_0a_1\}+(u+1)a_1\{a_1a_1-a_0a_2\}]\qquad\\
=&a_2\{a_0t_0+(u+1)a_2t_1+(u+1)a_1t_2\} \\
=&a_2\{a_0t_0+\text{mul_nonres}(a_2t_1)+\text{mul_nonres}(a_1t_2)\} \\
\end{align*}
```

分母を戻します。

```math
\begin{align*}
\text{factor}=& \frac{a_2}{a_2\{a_0t_0+\text{mul_nonres}(a_2t_1)+\text{mul_nonres}(a_1t_2)\} } \\
=& (a_0t_o+\text{mul_nonres}(a_2t_1)+\text{mul_nonres}(a_1t_2))^{-1} \\
F_{q^6} (a_2,a_1,a_0)^{-1} =& F_{q^6} (t_2\times \text{factor},t_1\times \text{factor},t_0\times \text{factor})\\ \end{align*}
```


### `mul_nonres`

```math
\begin{align*}
v\times \ F_{q^6} (a_2,a_1,a_0) =& a_0v + a_1v^2 + a_2v^3 \\
v^3=u+1\text{を代入}& \\
v\times \ F_{q^6} (a_2,a_1,a_0) =&(u+1)a_2+ a_0v + a_1v^2 \\
=&\text{mul_nonres}(a_2)+ a_0v + a_1v^2 \\
=& F_{q^6} (a_1,a_0,\text{mul_nonres}(a_2))\\
\end{align*}
```

# Fq12

$F_{q^{12}}$ は、$F_{q^6}(w)/(w^2-\gamma)$ 、$\gamma=v\$ として構成されています。

$a_0,a_1,b_0,b_1 \in F_{q^6}$としたとき、$a_0+a_1w\ ,\ b_0+b_1w \in F_{q^{12}}\ $となります。
$F_{q^{12}}$ は、$F_{q^6}\ $ を２つ持つので、$F_{q^{12}} (a_1,a_0)$ のようにあらわす事にします。

$a_0,a_1,b_0,b_1 \in F_{q^{6}}$とすると、加法、減法、乗法、乗法逆元は以下となります。
- （$+$）$\ F_{q^{12}} (a_1,a_0)+F_{q^{12}} (b_1,b_0) = F_{q^{12}} (a_1+b_1,a_0+b_0)$
- （$-$）$\ F_{q^{12}} (a_1,a_0)-F_{q^{12}} (b_1,b_0) = F_{q^{12}} (a_1-b_1,a_0-b_0)$
- （$\times$）$\ F_{q^{12}} (a_1,a_0)\times F_{q^{12}} (b_1,b_0) = F_{q^{12}} (a_1b_0+a_0b_1,a_0b_0+ \text{mul_nonres}(a_1b_1))$
- （inv）$\ F_{q^{12}} (a_1,a_0)^{-1} = F_{q^{12}} (-a_1\times \text{factor},a_0\times \text{factor})\ $
    - $\text{factor}= \\{a_0a_0-\text{mul_nonres}(a_1a_1)\\} ^{-1}$

### 単位元

```math
\begin{align*}
F_{q^{12}}(0,1) &=1 + 0w =1 \\
F_{q^{12}}(0,0) &=0 + 0w  =0 \\
\end{align*}
```

### 加法（＋）

```math
\begin{align*}
F_{q^{12}} (a_0,a_1)+F_{q^{12}} (b_0,b_1) &=a_0 + a_1w+b_0 + b_1w\\
&=(a_0+b_0)+(a_1+b_1)w \\
&=F_{q^{12}} (a_1+b_1,a_0+b_0)\\
\end{align*}
```

### 減法（－）

```math
\begin{align*}
F_{q^{12}} (a_0,a_1)-F_{q^{12}} (b_0,b_1) &=a_0 + a_1w-(b_0 + b_1w) \\
&=(a_0-b_0)+(a_1-b_1)w \\
&=F_{q^{12}} (a_1-b_1,a_0-b_0)\\
\end{align*}
```

### 乗法（×）

```math
\begin{align*}
F_{q^{12}} (a_0,a_1)\times F_{q^{12}} (b_0,b_1) =& (a_0 + a_1w)\times(b_0 + b_1w)\\
=&a_0b_0+a_0b_1w+a_1b_0w+a_1b_1w^2 \\
\end{align*}
```

$w^2$の項があるので$(w^2-v)$で割る事が出来ます。
さきほどと同様に、$w^2=v$を代入します。

```math
\begin{align*}
F_{q^{12}} (a_0,a_1)\times F_{q^{12}} (b_0,b_1) =& a_0b_0+a_0b_1w+a_1b_0w+a_1b_1w^2 \\
=& a_0b_0+a_0b_1w+a_1b_0w+a_1b_1v \\
=&(a_0b_0+a_1b_1v)+(a_0b_1+a_1b_0)w \\
\end{align*}
```

$v\times F_{q^6}\ $は、$F_{q^6}$の`mul_nonres`なので、以下のようにあらわせます。

```math
\begin{align*}
F_{q^{12}} (a_0,a_1)\times F_{q^{12}} (b_0,b_1) =&(a_0b_0+\text{mul_nonres}(a_1b_1))+(a_0b_1+a_1b_0)w \\
 =& F_{q^{12}}  (a_1b_0+a_0b_1,a_0b_0+ \text{mul_nonres}(a_1b_1))\\
\end{align*}
```


### 乗法逆元(inv)
乗法が$1=F_{q^{12}} (0,1)$となる$F_{q^{12}} (b_1,b_0)$を考えます。

```math
\begin{align*}
F_{q^2} (a_1,a_0)\times F_{q^2} (b_1,b_0) =(a_0b_0-a_1b_1)+(a_0b_1+a_1b_0)w\\
\end{align*}
```

```math
\begin{align*}
a_0b_0+\text{mul_nonres}(a_1b_1)=&1&\qquad\cdots(1)\\
a_0b_1+a_1b_0=&0&\qquad\cdots(2)\\
\end{align*}
```

```math
\begin{align*}
(1)\times a_1-(2)\times a_0& \\
a_0a_1b_0+\text{mul_nonres}(a_1a_1b_1)-(a_0a_0b_1+a_0a_1b_0)=&a_1\\
-(a_0a_0-\text{mul_nonres}(a_1a_1))b_1=&a_1\\
b_1=&\frac{-a_1}{a_0a_0-\text{mul_nonres}(a_1a_1)}\\
\end{align*}
```

$b_1$を$(2)$に代入します。

```math
\begin{align*}
a_0\frac{-a_1}{a_0a_0-\text{mul_nonres}(a_1a_1)}+a_1b_0=0 \\
b_0=\frac{a_0}{a_0a_0-\text{mul_nonres}(a_1a_1)} \\
\end{align*}
```

```math
\begin{align*}
\text{factor}= \{a_0a_0-\text{mul_nonres}(a_1a_1)\} ^{-1} \\
F_{q^{12}} (a_1,a_0)^{-1} = F_{q^{12}} (-a_1\times \text{factor},a_0\times \text{factor}) \\
\end{align*}
```



# まとめ（Conclusion）

[Pairing over BLS12-381, Part 1: Fields](https://research.nccgroup.com/2020/07/06/pairing-over-bls12-381-part-1-fields/)に書かれている、$F_{q^1},F_{q^2},F_{q^6},F_{q^{12}}$の式を求める事ができました。
「体(field）」として表すのであれば、左右の演算や分配法則など検証する箇所はまだまだありますが、
正直、疲れたのでこのあたりで終わりにしようと思います。

何度も見直しましたが、間違っている箇所があればお知らせください。