有限体演算

数学において、有限体演算は有限体（有限個の元を含む体）における演算であり、有理数体のような無限個の元を持つ体における演算とは対照的です。

有限体は無限に存在します。それらの元の数は必ずp nの形をとります。ここでpは素数、nは正の整数です。また、同じ大きさの2つの有限体は同型です。素数pは体の標数と呼ばれ、正の整数nは素体上の体の次元と呼ばれます。

有限体は、 BCH コードやリード・ソロモン誤り訂正などの線形ブロック コードの古典的な符号化理論、ラインダール( AES ) 暗号化アルゴリズムなどの暗号化アルゴリズム、トーナメント スケジューリング、実験計画法など、さまざまなアプリケーションで使用されます。

有効多項式表現

p n個の元を持つ有限体はGF( p n )と表記され、有限体理論の創始者であるエヴァリスト・ガロアにちなんでp n位のガロア体とも呼ばれます。 pを素数とするGF( p ) は、単にpを法とする整数の環です。つまり、通常の整数演算を使用して演算 (加算、減算、乗算) を実行し、その後pを法として簡約することができます。たとえば、GF(5) では、4 + 3 = 7は 5 を法として 2 に簡約されます。除算はpを法とする逆数による乗算であり、拡張ユークリッドの互除法を使用して計算できます。

GF(2)は特殊なケースであり、加算は排他的論理和(XOR)、乗算は論理積(AND)です。逆元は 1 のみなので、除算は恒等関数となります。

GF( p n ) の元は、 GF( p ) 上のn 次未満の多項式として表すことができます。演算はm(x)を法として実行されます。ここで、m(x)はGF( p ) 上のn次既約多項式であり、たとえば多項式長除算が使用されます。加算は通常の多項式の加算ですが、係数はpを法として約分されます。乗算も通常の多項式の乗算ですが、係数はpを法として乗算され、多項式は多項式m(x)を法として乗算されます。[ 1 ]多項式係数によるこの表現は単項式基底（別名「多項式基底」）と呼ばれます。

GF( p n )の元には他の表現法も存在します。いくつかは上記の多項式表現と同型ですが、他の表現は全く異なるもの（例えば行列を用いるもの）もあります。正規基底を用いることは、状況によっては利点があるかもしれません。

素数が2の場合、GF( p n )の元は2進数で表現するのが慣例であり、多項式の各項の係数は、対応する元の2進表現の1ビットで表されます。2進数、あるいはそれに相当する16進数には、中括弧（「{」と「}」）などの区切り文字が付加されることが多く、その値が体の基底の係数、つまり体の元を表すことを示します。例えば、以下は、特性2の有限体における同じ値の等価な表現です。

多項式 × 6 + × 4 + × + 1
バイナリ {01010011}
16進数 {53}

原始多項式

有限体を生成するために使用できる 既約多項式（約分多項式と呼ばれることもある）は多数ありますが、それらはすべて体の同じ表現を生成するわけではありません。

有限体GF( q ) （ある素数pと正の整数tに対してq = p t）に係数を持つn次 の単項既約多項式は、そのすべての根がGF( qn )の原始元であるとき、原始多項式と呼ばれる。[ 2 ] [ 3 ]有限体の多項式表現において、これはxが原始元であることを意味する。xが原始元である既約多項式は少なくとも1つ存在する。[ 4 ]言い換えれば、原始多項式では、xのべき乗により体のすべての非零値が生成される。

次の例では、例によってxの意味が変わるため、多項式表現を使用しないことが最善です。 GF(2)上のモニック既約多項式x 8 + x 4 + x 3 + x + 1 は原始的ではありません。λ をこの多項式の根とします（多項式表現ではxになります）、つまりλ 8 + λ 4 + λ 3 + λ + 1 = 0です。ここでλ 51 = 1なので、λ はGF(2 8 )の原始元ではなく、位数 51 の乗法部分群を生成します。[ 5 ] GF(2)上のモニック既約多項式x 8 + x 4 + x 3 + x 2 + 1 は原始的であり、8 つの根すべてがGF(2 8 )の生成元です。

すべてのGF(2 8 )には合計128個の生成元があり（原始元の数を参照）、原始多項式の場合、そのうち8個は既約多項式の根となる。有限体の生成元としてxを持つことは、多くの計算数学的演算において有益である。

足し算と引き算

加算と減算は、これらの多項式のうち 2 つを加算または減算し、その結果を特性値で割って減算することによって実行されます。

標数2の有限体においては、2を法とする加算、2を法とする減算、XORは同一である。したがって、

多項式 ( × 6 + × 4 + × + 1) + ( × 7 + × 6 + × 3 + × ) = × 7 + × 4 + × 3 + 1
バイナリ {01010011} + {11001010} = {10011001}
16進数 {53} + {CA} = {99}

多項式の通常の加算では、和には 2 x 6という項が含まれます。この項は 0 x 6となり、答えを 2 で割った結果、省略されます。

以下は、いくつかの多項式の通常の代数和と特性 2 の有限体和の両方を含む表です。

1ページ目2ページp 1 + p 2下...
K[ x ]GF(2 n )
× 3 + × + 1 × 3 + × 22 × 3 + × 2 + × + 1 × 2 + × + 1
× 4 + × 2× 6 + × 2× 6 + × 4 + 2 × 2× 6 + × 4
x + 1 × 2 + 1 × 2 + × + 2 × 2 + ×
× 3 + ×× 2 + 1 × 3 + × 2 + × + 1 × 3 + × 2 + × + 1
× 2 + ×× 2 + ×2 × 2＋2 ×0

コンピュータサイエンスのアプリケーションでは、特性 2 の有限体 (GF(2 n )ガロア体とも呼ばれる) の演算が簡略化されるため、これらの体はアプリケーションで特によく選ばれます。

乗算

有限体における乗算は、有限体を定義するために用いられる既約な約分多項式を法とする乗算です。（つまり、約分多項式を除数として乗算を行った後に、その積を剰余として除算を行ったものです。）記号「•」は、有限体における乗算を表すために使用できます。

ラインダール（AES）有限体

ラインダール（AESとして標準化）は、256個の元を持つ標数2の有限体（ガロア体GF(2 ^8 )とも呼ばれる）を用いる。乗算には以下の約分多項式を用いる。

× 8 + × 4 + × 3 + × + 1。

例えば、ラインダールの体では{53} • {CA} = {01}となる。

( × 6 + × 4 + × + 1)( × 7 + × 6 + × 3 + × )
＝( × 13 + × 12 + × 9 + × 7 ) + ( × 11 + × 10 + × 7 + × 5 ) + ( × 8 + × 7 + × 4 + × 2 ) + ( × 7 + × 6 + × 3 + × )
＝× 13 + × 12 + × 9 + × 11 + × 10 + × 5 + × 8 + × 4 + × 2 + × 6 + × 3 + ×
＝× 13 + × 12 + × 11 + × 10 + × 9 + × 8 + × 6 + × 5 + × 4 + × 3 + × 2 + ×

そして

x 13 + x 12 + x 11 + x 10 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + x 2 + x mod x 8 + x 4 + x 3 + x 1 + 1
＝(11111101111110 モッド 100011011)
＝{3F7E mod 11B} = {01}
＝1（小数）

後者は、長除法で示すことができます（タスクに適しているため、2 進表記法を使用して示します。例では、小学校の長除法で使用するような算術減算ではなく、排他的論理和が適用されていることに注意してください）。 

 11111101111110 (mod) 100011011 ^100011011  01110000011110 ^ 100011011  0110110101110 ^100011011  010101110110 ^100011011  00100011010 ^100011011  000000001

（要素{53}と{CA}は、積が1なので、互いの逆数です。）

この特定の有限体における乗算は、「農民のアルゴリズム」の修正版を用いて行うこともできます。各多項式は上記と同じ2進表記法を用いて表されます。各（既約）多項式の項には0次から7次までしか取り得ないため、8ビットで十分です。

このアルゴリズムは、それぞれ 8 ビット表現を保持する3 つの変数(コンピュータ プログラミングの意味で) を使用します。aとbは被乗数で初期化され、p は積を累積し、0 に初期化する必要があります。

アルゴリズムの開始時と終了時、そして各反復処理の開始時と終了時において、この不変条件は成立します。つまり、a b + pは積です。これはアルゴリズムの開始時には明らかに成立します。アルゴリズムの終了時には、aまたはb はゼロになるため、pには積が含まれます。

  • 以下のループを8回（ビットごとに1回ずつ）実行します。反復処理の前に、 aまたはbが0になった時点で停止しても問題ありません。
    1. bの右端のビットが設定されている場合、積pとaの値の排他的論理和を求めます。これは多項式加算です。
    2. b を1ビット右にシフトし、右端のビットを破棄し、左端のビットの値を0にします。これにより、多項式がxで割られ、x 0 の項が破棄されます。
    3. aの左端のビットが 1 に設定されているかどうかを追跡し、この値をcarry と呼びます。
    4. 1ビット左にシフトし、左端のビットを破棄し、右端のビットを0にします。これにより多項式はx倍になりますが、 x 7の係数を表す繰り上がりを考慮する必要があります。
    5. キャリーの値が1の場合、 16進数（2進数では00011011）と排他的、またはaでなければなりません。これは、高次項を除いた既約多項式に相当します。概念的には、既約多項式の高次項とキャリーを2を法として0に加算します。0x1b0x1b
  • pは現在製品を持っています

このアルゴリズムは、 a、b、pの長さと値を0x1b適切に変更することで、特性 2 の他の体上の乗算に簡単に一般化できます。

乗法逆数

有限体の元aの逆数は、いくつかの方法で計算できます。

実装のコツ

ジェネレータベースのテーブル

小さなガロア体上のガロア体計算アルゴリズムを開発する場合、一般的なパフォーマンス最適化アプローチは、生成子gを見つけて、次の恒等式を使用することです。

1つのb＝グラムロググラム⁡（1つのb）＝グラムロググラム⁡（1つの）+ロググラム⁡（b）{\displaystyle ab=g^{\log _{g}(ab)}=g^{\log _{g}(a)+\log _{g}(b)}}

乗算を、log g ( a ) 関数とg y関数のテーブル参照と整数加算演算のシーケンスとして実装します。これは、すべての有限体が生成元を含むという性質を利用しています。ラインダール体の例では、多項式x + 1 (または {03}) はそのような生成元の一つです。多項式が生成元であるための必要条件は、既約であることですが、これは十分条件ではありません。

実装では、積もゼロになるため、 aまたはbがゼロになる特殊なケースをテストする必要があります。

同じ戦略を使用して、恒等式を使用して逆数を決定することもできます。

1つの−1＝グラムロググラム⁡（1つの−1）＝グラム−ロググラム⁡（1つの）＝グラム|グラム|−ロググラム⁡（1つの）{\displaystyle a^{-1}=g^{\log _{g}\left(a^{-1}\right)}=g^{-\log _{g}(a)}=g^{|g|-\log _{g}(a)}}

ここで、生成元の位数| g | は、体の非零元の数です。GF(2 8 )の場合、これは2 8 − 1 = 255です。つまり、ラインダールの例では、( x + 1) 255 = 1 となります。つまり、これは2つのルックアップテーブルと整数減算で実行できます。この考え方をべき乗に適用すると、次のような利点もあります。

1つのn＝グラムロググラム⁡（1つのn）＝グラムnロググラム⁡（1つの）＝グラムnロググラム⁡（1つの）（モッド|グラム|）{\displaystyle a^{n}=g^{\log _{g}\left(a^{n}\right)}=g^{n\log _{g}(a)}=g^{n\log _{g}(a){\pmod {|g|}}}}

これには2つのテーブル参照、つまり整数乗算と整数剰余演算が必要です。ここでも、a = 0という特殊なケースに対するテストを実行する必要があります。

しかし、暗号実装においては、多くのマイクロプロセッサのキャッシュアーキテクチャがメモリアクセスのタイミングを変動させるため、注意が必要です。その結果、タイミング攻撃に対して脆弱な実装となる可能性があります。

繰り上がりのない乗算

2進体GF(2n)では、体の乗算はCLMUL命令セットなどのキャリーレス乗算を使用して実装でき、 n≤64に適しています。乗算では、1つのキャリーレス乗算を使用して積（最大2n −1ビット）を生成し、別のキャリーレス乗算を使用して体多項式の事前計算された逆数で商 = ⌊積/（体多項式）⌋を生成し、商と体多項式を乗算し、最後にxor：結果 = 積 ⊕（（体多項式）⌊積/（体多項式）⌋）。最後の3つのステップ（pclmulqdq、pclmulqdq、xor）は、x86 pclmulqdq命令を使用してCRCを高速に計算するためのバレット縮小ステップで使用されます。[ 8 ]

合成指数

kが合成数であるとき、二進体 GF(2 k ) からそのいずれかの部分体の拡大体、つまりk = m nである GF((2 m ) n )への同型が存在する。これらの同型のいずれかを利用すると、拡大の次数が小さくなるため数学的な考慮を簡素化できるが、その代償として要素がより大きな部分体上で表現されるようになる。[ 9 ]ハードウェア実装のゲート数を削減するために、このプロセスには GF(2 8 ) から GF(((2 2 ) 2 ) 2 )への写像など、複数のネストが含まれる場合がある。 [ 10 ]

プログラム例

Cプログラミングの例

以下は、ロシア農民乗算アルゴリズムを使用して、たとえばラインダールアルゴリズムやリードソロモンで使用される、順序 2 8の特性 2 有限体の数を加算および乗算するCコードです。 

/* GF(2^8)有限体上の2つの数を加算する */ uint8_t gadd ( uint8_t a , uint8_t b ) { return a ^ b ; }/* GF(2^8) 有限体で、モジュロ多項式関係 x^8 + x^4 + x^3 + x + 1 = 0 によって定義される 2 つの数を乗算します* (他の方法は、キャリーレス乗算の後にモジュラー減算を行うことです) */ uint8_t gmul ( uint8_t a , uint8_t b ) { uint8_t p = 0 ; /* 乗算の積の累算器 */ while ( a != 0 && b != 0 ) { if ( b & 1 ) /* b の多項式に定数項がある場合は、対応する a を p に追加します */ p ^= a ; /* GF(2^m) での加算は、多項式係数の XOR です */if ( a & 0x80 ) /* GF 法: a に非ゼロの項 x^7 がある場合、x^8 になるときに約分される必要があります */ a = ( a << 1 ) ^ 0x11b ; /* 原始多項式 x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) を減算 (XOR) します – 変更することはできますが、約分不可能である必要があります */ else a <<= 1 ; /* a*x と同等 */ b >>= 1 ; } return p ; }

この例には、キャッシュ、タイミング、および分岐予測のサイドチャネルリークがあり、暗号化での使用には適していません。

Dプログラミングの例

このDプログラムは、Rijndael の有限体で数値を乗算し、PGM画像を生成します。 

/**多項式 x^8 + x^4 + x^3 + x + 1 で定義される GF(2^8) 有限体内の 2 つの数を乗算します。*/ ubyte gMul ( ubyte a , ubyte b ) pure nothrow { ubyte p = 0 ;foreach (不変のubyteカウンタ; 0 .. 8 ) { p ^= -( b & 1 ) &a a ; auto mask = -(( a >> 7 ) & 1 ); // 0b1_0001_1011 は x^8 + x^4 + x^3 + x + 1 です。a = cast ( ubyte )(( a << 1 ) ^ ( 0b1_0001_1011 & mask )); b >>= 1 ; }pを返す; }void main ( ) { import std.stdio , std.conv ; enum width = ubyte.max + 1 , height = width ;​​​​​auto f = File ( "rijndael_finite_field_multiplication.pgm" , "wb" ); f . writefln ( "P5\n%d %d\n255" , width , height ); foreach ( immutable y ; 0 .. height ) foreach ( immutable x ; 0 .. width ) { immutable char c = gMul ( x . to ! ubyte , y . to ! ubyte ); f . write ( c ); } }

この例では、サイド チャネルを回避するために分岐やテーブル検索は使用されていないため、暗号化に適しています。

参照

参考文献

  1. ^ハンカーソン、ヴァンストーン、メネゼス 2004、28ページ
  2. ^このような多項式はGF( q ) には根がないので、その根は GF( q ) の拡大体に存在する必要があります。
  3. ^マレン & パナリオ 2013、p. 17
  4. ^実験のデザインと分析. John Wiley & Sons, Ltd. 2005年8月8日. pp.  716– 720. doi : 10.1002/0471709948.app1 .
  5. ^ Lidl & Niederreiter 1983、p. 553
  6. ^ Fan, Haining. 「トレースベースのGF(2 n )逆変換アルゴリズム」(PDF) . 2025年4月21日時点のオリジナルよりアーカイブ。 2025年1月10日閲覧。{{cite web}}: CS1 maint: bot: 元のURLステータス不明（リンク）
  7. ^ Grošek, O.; Fabšič, T. (2018), 「有限体における長除算による逆乗の計算」(PDF) , Journal of Electrical Engineering , 69 (5): 400– 402, Bibcode : 2018JEE....69..400G , doi : 10.2478/jee-2018-0059 , S2CID 115440420 
  8. ^ 「PCLMULQDQ命令を使用した汎用多項式の高速CRC計算」(PDF) . www.intel.com . 2009 . 2020年8月8日閲覧。
  9. ^ 「セキュアストレージアプリケーションのための大規模FiniteFieldsGF(2n)の効率的なソフトウェア実装」（PDF） www.ccs.neu.edu 2020年8月8日閲覧。
  10. ^ "bpdegnan/aes" . GitHub .

出典

  • リドル、ルドルフ。 Niederreiter、Harald (1983)、有限体、Addison-Wesley、ISBN 0-201-13519-1（1984年にケンブリッジ大学出版局から再発行ISBN 0-521-30240-4）。
  • マレン、ゲイリー・L.; パナリオ、ダニエル (2013)、『有限体ハンドブック』、CRC Press、ISBN 978-1-4398-7378-6
  • ハンカーソン、ダレル、ヴァンストーン、アルフレッド・メネゼス（2004年）、楕円曲線暗号ガイド、シュプリンガー、ISBN 978-0-387-21846-5
「 https://en.wikipedia.org/w/index.php?title=有限体算術&oldid =1307996085」より取得