有限体演算

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

有限体は無限に存在します。それらの元の数は必然的にp ^{n の}形をとります。ここでpは素数、 nは正の整数で、同じサイズの 2 つの有限体は同型です。素数p は体の標数と呼ばれ、正の整数n は素体上の体の次元と呼ばれます。

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

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

特殊なケースとしてはGF(2)があり、加算は排他的論理和（XOR）で乗算はANDです。可逆な要素は1だけなので、除算は恒等関数です。

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

GF( p ⁿ )の要素には他の表現もあります。いくつかは上記の多項式表現と同型ですが、他の表現はまったく異なります (たとえば、行列を使用)。正規基底を使用すると、状況によっては利点がある場合があります。

素数が 2 の場合、GF( p ⁿ )の元を2 進数で表すのが慣例です。多項式の各項の係数は、対応する元の 2 進表現の 1 ビットで表されます。中括弧 (「{」と「}」) または同様の区切り文字は、通常、2 進数またはその 16 進数に追加され、値が体の基底の係数を与え、体の元を表すことを示します。たとえば、次の表現は、特性 2 の有限体における同じ値の同等の表現です。

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

有限体 GF( q ) （ある素数pと正の整数tに対してq = p ^t ）に係数を持つn次モニック 既約多項式は、その根がすべてGF( q ⁿ ) の原始元である場合に原始多項式と呼ばれます。^{[2] [3]}有限体の多項式表現では、これはxが原始元であることを意味します。 xが原始元である既約多項式が少なくとも 1 つ存在します。^[4]言い換えると、原始多項式では、xの累乗によって体のすべての非ゼロ値が生成されます。

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

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

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

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

多項式の通常の加算では、合計に 2 x ^{6 の}項が含まれます。この項は 0 x ⁶になり、答えが 2 を法として減算されると削除されます。

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

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

有限体における乗算は、有限体を定義するために使用される既約な約数多項式を法とする乗算です。(つまり、約数多項式を除数として使用して乗算を行った後に除算を行い、余りが積になります。) 有限体における乗算を表すために、記号「•」が使用される場合があります。

Rijndael (AES として標準化) は、256 個の要素を持つ特性 2 の有限体を使用します。これはガロア体 GF(2 ⁸ )とも呼ばれます。乗算には次の約分多項式を使用します。

x ⁸ + x ⁴ + x ³ + x + 1。

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

そして

後者は、長除法で示すことができます(タスクに適しているため、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がゼロのときに停止しても問題ありません。
  1. bの右端のビットが設定されている場合は、積pとaの値を排他的論理和します。これは多項式加算です。
  2. b を1 ビット右にシフトし、右端のビットを破棄して、左端のビットの値を 0 にします。これにより、多項式がxで除算され、x ⁰項が破棄されます。
  3. aの左端のビットが 1 に設定されているかどうかを追跡し、この値をcarry と呼びます。
  4. 1ビット左にシフトし、左端のビットを破棄して、新しい右端のビットを 0 にします。これにより、多項式がxで乗算されますが、 x ⁷の係数を表す繰り上がりを考慮する必要があります。
  5. キャリーの値が 1 の場合、排他的または16進数0x1b(2 進数では 00011011) になります。0x1bこれは、高項が削除された既約多項式に対応します。概念的には、既約多項式の高項とキャリーを2 を法として 0 に加算します。
• pは現在製品を持っています

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

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

• 積が 1 になるまで、体内のすべての数値をaに掛け合わせます。これは総当たり検索です。
• GF( p ⁿ )の非ゼロ元は乗法に関して有限群を形成するので、 a ^{p n −1} = 1（a ≠ 0の場合）となり、したがってaの逆元はa ^{p n −2}となる。
• 拡張ユークリッドの互除法を使用します。
• 有限体の対数表と指数表を作成し、 p ⁿ − 1から対数を減算し 、その結果を指数化します。
• 有限体のモジュラー乗法逆表を作成し、検索を実行します。
• 反転がより簡単な複合フィールドにマッピングし、それを元に戻します。
• 特別な整数（素数位数の有限体の場合）または特別な多項式（非素数位数の有限体の場合）を構築し、それをで割ることによって。 [ ^6]

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

${\displaystyle ab=g^{\log _{g}(ab)}=g^{\log _{g}(a)+\log _{g}(b)}}$

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

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

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

${\displaystyle a^{-1}=g^{\log _{g}\left(a^{-1}\right)}=g^{-\log _{g}(a)}=g^{|g|-\log _{g}(a)}}$

ここで、生成子の位数| g | は、体の非ゼロ元の数です。GF(2 ⁸ ) の場合、これは2 ⁸ − 1 = 255です。つまり、Rijndael の例では、( x + 1) ²⁵⁵ = 1です。したがって、これは 2 つのルックアップ テーブルと整数減算で実行できます。この考え方を累乗に使用すると、次のような利点もあります。

${\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(2 ⁿ )の場合、体の乗算はCLMUL命令セットなどのキャリーレス乗算を使用して実装でき、 n ≤ 64に適しています。乗算では、1つのキャリーレス乗算を使用して積（最大2 n − 1ビット）を生成し、別のキャリーレス乗算を使用して体多項式の事前計算された逆数で商 = ⌊積/（体多項式）⌋を生成し、商と体多項式を乗算し、最後に排他的論理和：結果 = 積 ⊕ （（体多項式） ⌊積/（体多項式）⌋）。最後の3つのステップ（pclmulqdq、pclmulqdq、xor）は、x86 pclmulqdq命令を使用してCRCを高速に計算するためのバレット削減ステップで使用されます。^[7]

kが合成数である場合、 2 進体 GF(2 ^k ) からそのサブフィールドの 1 つの拡大体への同型、つまりk = m nの GF((2 ^m ) ⁿ )が存在する。これらの同型のいずれかを使用すると、拡大の次数が小さくなるため、数学的な考慮を簡素化できるが、その代償として、要素がより大きなサブフィールド上で表現されるようになる。^{[8]ハードウェア実装のゲート数を減らすために、プロセスには GF(2 8} ) から GF(((2 ² ) ² ) ² ) へのマッピングなど、複数のネストが含まれる場合がある。^[9]

以下は、ロシア農民乗算アルゴリズムを使用して、たとえば Rijndael アルゴリズムや Reed–Solomon で使用される、順序 2 ⁸の特性 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プログラムは、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 ); } }    
      
         
              
                 
            
        

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

• ツェッヒの対数

• リドル、ルドルフ。 Niederreiter、Harald (1983)、有限体、Addison-Wesley、ISBN 0-201-13519-1（1984年にケンブリッジ大学出版局より再発行、ISBN 0-521-30240-4）。 
• マレン、ゲイリー L.; パナリオ、ダニエル (2013)、有限体ハンドブック、CRC プレス、ISBN 978-1-4398-7378-6
• ハンカーソン、ダレル、ヴァンストーン、アルフレッド・メネゼス（2004）、楕円曲線暗号ガイド、シュプリンガー、ISBN 978-0-387-21846-5

• Gordon, G. (1976). 「有限体の任意の非ゼロ要素の最小多項式を見つけるための非常に簡単な方法」. Electronics Letters . 12 (25): 663–664. Bibcode :1976ElL....12..663G. doi :10.1049/el:19760508.
• da Rocha, VC; Markarian, G. (2006). 「有限体の任意の要素のトレースを探す簡単な方法」. Electronics Letters . 42 (7): 423–325. Bibcode :2006ElL....42..423D. doi :10.1049/el:20060473.
• トレンホルム、サム。 「AEのガロア体」。
• Planck, James S. (2007)。「C/C++ での高速ガロア体演算ライブラリ」
• Wikiversity: プログラマのためのリード・ソロモン – 有限体演算