サイオステクノロジーの菊地啓哉です。思ったより間が空いてしまったのですが、前回の記事の続きになります。

ECDSA や zk-STARK などでは有限体がベースにあるので、前回の体の話から、有限体の話に進んでいこうと思います。

自分が有限体について調べた時には、体の拡大に急に既約多項式が出てきて飲み込みにくいところがあったので、そのあたりに少しだけ間の内容を入れています。

数学に詳しくないエンジニアの体入門
数学に詳しくないエンジニアの有限体

1 巡回群
2 有限体
3 有理数と平方根
4 mod 3 の体を拡大する
5 おわりに

巡回群

前回も少し触れましたが、巡回群についてご紹介したいと思います。この群は、ただ1つの元で生成される群で、 mod n（nで割った余り）の中での足し算もこれの具体例の1つとなります。

例えば、単位元 e、生成元 g、要素数 4 の巡回群 G について考えると、 g ○ g = g² のように演算 ○ の繰り返しを累乗のように表現するなら G の元は

のように表すことができます。これは整数の足し算の4で割った余りが元の数の4で割った余り同士の足し算（をさらに4で割った余り）と同じです。

13（4で割ると余り1）+ 22（4で割ると余り2） = 35（4で割ると余り3）
6（4で割ると余り2）+ 35（4で割ると余り3） = 41（4で割ると余り1）

有限体

有限体の性質

体のうち、元が有限個のものを有限体（ゆうげんたい、Finite Field）と呼びます。話がとても難しくなってしまうので導出はしませんが以下のような性質を持ちます。

3点目については、有限群の性質から導けます。1点目と2点目は実力不足で分かりやすくまとめられなさそうなので諦めました（これは3点目のフェルマーの小定理にかけているわけではありません）。

有限体の例

mod 3 の足し算、掛け算で体を考えます。ここでは、mod 3 であることを忘れないように、下添え字の 3 をつけます。可換であることを踏まえて通常の計算と異なるのは、以下の3つです。

mod 3 だということを考えれば特に問題無いかと思います。

とても簡単ですが、「体の元から零元を除くと乗法に関して巡回群となる」について確認しておくと、

となるので、零元を除くと、乗法に関して元の数が2の巡回群となっていることがわかります。

なんで、こんな元の数が少ない体にしたかと言えば、後でこの体を拡大します。

有限体で方程式を解く

前回の記事で、体の中で方程式を解くのが普通にやってるのと同じと書いたので、実数の世界で -2 と 1/2 が解の二次方程式を mod 3 の体で解いてみたいと思います。この二次方程式は次のように書けます。

これは、特に上に書いた計算を利用することで、1₃ + 2₃ = 0₃ 、2₃ * 2₃ – 1₃ = 1₃ – 1₃ = 0₃ なので、 x = 1₃, 2₃ と解くことができます。こういった具合に、有理数係数の方程式は割と有限体の方程式にそのまま考え直すことができます。ただし、0除算があってはいけないので、この mod 3 の体で考えるには分母が3の倍数の解があると上手くいきません。

この方程式の両辺を 2₃ 倍して、式を展開してみましょう

当然と言えば当然ですが、最後の式を見ると、解と係数の関係が成り立っていることも見て取れると思います。

Bitcoin や Ethereum では、secp256k1 と呼ばれる楕円曲線（のパラメータ）を採用しているようで、そこでは有限体の元の数 p は 2²⁵⁶ – 2³² – 2⁹ – 2⁸ – 2⁷ – 2⁶ – 2⁴ – 1 という、とても大きな値を使っています。

完全に余談ですが、ECDSAで楕円曲線上の点と点の足し算を定義して、その繰り返しとしてスカラー倍を定めているのに、表記によってはいつのまにか、スカラー倍の部分が分数で表現されていたりするのは、繰り返しの数を表す係数側が有限体の元であり、逆数は逆元を意味しているので、分数を計算すれば自然数になることなどを前提としていますね。

せっかく有限体の話を書いてきたので、要素数が素数の有限体を拡大するところに触れたいと思います。その前に少し寄り道をします。

有理数と平方根

前回の記事の群の例を見ていただくとわかると思いますが、群となれない理由としてありがちなのは、”逆元が存在すること”が満たされない、かなと思います。

中学で平方根（ルート）を学習された/されることと思いますが、そこで分母の有理化というものがあったと思います。逆元の存在とか、演算が閉じていることとか、そんなことと絡めて授業を受けたという方は恐らくいらっしゃらないとは思いますが、「2乗すると有理数になる」、「分母に平方根があっても分母を有理化できる」など、乗法について体となかなか相性の良い性質を持っています。有理数 a, b と素数 p で a +b√p で表されるような数について掛け算と割り算は以下のようになります。（ここでは素数である必要性はないのですが、 √p が確実に有理数でないようにわかりやすく素数としています）

どちらの計算結果も「有理数 a, b と素数 p を用いて a +b√p で表される形」になっています。このことから、「なんか、平方根を使っていい感じの体を作れそうな空気」が出てきます。足し算引き算も問題無さそうなのはおわかりかと思いますのでスキップします。

mod 3 の体を拡大する

先ほどの mod 3 で考えていた体に √2 に相当する数 β を仲間に加えてみます。ここで、 β*β = β² = 2₃ です。また、 β 自体が mod 3 でどうなるかは考えず、その係数で mod 3 を考えます。別の表現をするなら、 1₃ + 2₃ = 0₃ の両辺に β を掛けて次の式が得られます。

この集合は、mod 3 の体の元 a, b を用いて、 a+bβ で表すことのできる 9個の元を作れることがわかります。また、この集合が体になることがわかります。

逆元がわかりにくいところだと、

となります。あと、有限体の性質のうち、零元を除いて乗法が巡回群となるということについて、ちょっと計算してみると、

のように、 1₃ + β を生成元にできることがわかります。（上の結果を見て想像できるように他にも生成元にできる元があります）

ここでは、 mod 3 の有限体に β² = 2₃ となる元 β を加えて、新しい体を作りました。

これと同じように一般的には、既約多項式という「より低次の多項式で因数分解できない多項式」を使って、”既約多項式 = 0”で定義される新しい元（ α とします）を定め、体を拡大します。また、その時、拡大前の体の元の数を p 、既約多項式の次数を n とすると、各 α^k (k=0, 1, …, n-1) の係数が p 種類取り得るので、作られる体の元の数は pⁿ となります。今回の例の β であれば、 β² = 2₃ の右辺が 0 になるように変形して既約多項式は β² + 1₃ となります。

先の例よりも次数が上の具体例として、これまで扱ってきた mod 3 の体に α³ + 2₃ α + 1₃ = 0₃ で定められる α を追加すると、四則演算によって、 a + b α + cα² で表される 3³ 個の元ができ、それらによって、体が作られます。ここで、 a, b, c は mod 3の体の元で、1つ前の体と比べると、 cα² が増えた分、元の数が3倍になっています。 α の多項式の次数が2次以下となるのは α³ = -2₃ α – 1₃ なので、 α の3次以上の項は次数を落とすことができることからわかります。