3次拡大体の演算

初めに

2次拡大体の基本やより一般の2次拡大体では2次拡大体の演算を扱いました。
次は3次拡大体に移ります。ペアリングの計算では2次、3次（4次）、6次、12次拡大体などを扱います。式は複雑になりますが考え方は2次拡大体と変わりません。

3次拡大体

$K$ を体とし、$\xi \in K$ を3乗根が $K$ に存在しない定数とします。実際には $\xi$ は計算が容易な小さい値を選びます。
このとき $L=K[X]/(X^3-\xi)$ は $K$ の3次拡大体となります。
$X$ に関する $K$ 係数の多項式全体を $X^3-\xi$ で割った余りなので2次式で表現できます。$v$ を3乗すると $\xi$ になる値として $x=a + b v + cv^2 \in L$ と表記します。
ベクトル的に $(a, b, c)$ と書くこともあります。
以下、$x=a+b v + c v^2$, $y=d + e v + f v^2 \in L$ とします。

加減算

$x \pm y = (a \pm d) + (b \pm e)v + (c \pm + f)v^2$ です。それぞれの成分ごとに加減算すればよいです。

乗算

$v^3=\xi \in K$ となることに注意して通常の多項式のように計算すればよいです。

$$x y = (ad + (bf + ce)\xi) + ((ae + bd) + cf \xi)v + ((af + cd)+be)v^2.$$

ただこのまま計算すると $K$ における乗算が9回必要です。
そこで2次拡大体におけるKaratsuba法の様に乗算回数を減らす方法を考えます。

$$\begin{align*} bf + ce &= (b + c)(e + f) - be - cf,\\ ae + bd &= (a + b)(e + d) - ad - be,\\ af + cd &= (a + c)(d + f) - ad - cf. \end{align*}$$

と式変形します。そうすると $ad$, $be$, $cf$ と $(b+c)(e+f)$, $(a+b)(e+d)$, $(a+c)(d+f)$ の6個の乗算で済み、3回減らせました。

平方

2乗算はどうなるでしょうか。

$$x^2 = (a^2 + 2bc \xi) + (c^2 \xi + 2ab)v + (b^2 + 2ac)v^2.$$

です。このままでは6回乗算が必要です。最後の $v^2$ の係数を

$$b^2+2ac=(a+b+c)^2 - a^2 - 2bc - c^2 - 2ab$$

と変形すると $(a+b+c)^2$ だけ求めれば後の乗算はそれまでに計算しているので全部で5回となり、1回減らせます。
このあたりの式変形は試行錯誤して慣れればすぐできるようになります。

逆数

$x = a + bv + cv^2$ として $y=1/x$ を計算します。
2次拡大体のときは分子・分母に $a-bv$ を掛けて分母が元の体 $K$ の値になるように変形しました。
3次拡大体では $a - bv - cv^2$ を掛けてもうまくいきません。どうすればよいでしょうか。
ここで次の等式を使います。

$$X^3+Y^3+Z^3 - 3 X Y Z = (X + Y + Z)(X^2 + Y^2 + Z^2 - XY - YZ - ZX).$$

大学受験の難しめの数学の問題でたまに出てきますね。

$X=a$, $Y=bv$, $Z=c v^2$ とします。$x=X+Y+Z$ に何かを掛けて $K$ の元となるようにしたいのです。
$v$ は3乗すると$v^3=\xi \in K$ なので $p=X^2 + Y^2 + Z^2 - XY - YZ - ZX$ を掛けるとよいです。
つまり、

$$y=1/x = p / (x p).$$

分母は

$$\begin{align*} x p &= X^3 + Y^3 + Z^3 - 3 XYZ = a^3 + (bv)^3 + (c v^2)^3 - 3 a bv c v^2\\ &= a^3 + b^3 \xi + c^3 \xi^2 - 3 a b c \xi \\ &=a^3 + b(b^2-3ac)\xi + c^3 \xi^2 \in K. \end{align*}$$

となりました。従って $K$ の中で $xp$ の逆数を求めて $p$ に掛ければOKです。
演算回数を減らせるか考察しましょう。

$p = a^2 + b^2 v^2 + c^2 \xi v - abv - bc \xi - ac v^2 = (a^2 - bc \xi) + (c^2 \xi - ab)v + (b^2 - ac)v^2.$

ここに登場する項に合わせて $xp$ を式変形すると

$xp = (a^2 - bc \xi)a + ((c^2 \xi - ab)c + (b^2 - ac)b)\xi.$

とできました。$p$ の各成分を求めたら、$xp$ は比較的容易に計算できることが分かりました。

まとめ

（BN曲線やBLS曲線の）ペアリングの実装に3次拡大体は必須なのですが、このあたりの導出を丁寧に解説したテキストはあまり見かけないので書いてみました。