有限体の計算

コンピュータで利用されている暗号方式としてRSA暗号や楕円曲線暗号が挙げられますが，これらの演算には有限体という数論的な計算が必要不可欠となっています．

数論と言っても，とある素数を法として設定し，その数未満で計算することができます．

突然，「法」とかよくわからない言葉が出てきますが，例えば，法が_p_ = 7のとき，有限体は集合として_{0,1,2,3,4,5,6}_と表すことができます．

これは割り算の余りと同じで，

14 / 7 = 2 余り 0

となり，あまりは0です．14 → 15にしてみるとどうでしょう．あまりは１になります． 15→…→20とすると，あまりは2,3,…,6となり，有限体の集合を表すことができます．

コンピュータで利用される暗号は有限体が重要と最初に述べました．このことから，余りの計算は現代のインターネットの安全性を保つために必要不可欠となっているのです．(詳しくは別の記事に書きます)

今回は，有限体の計算手法についてメモとして残して置きます．

有限体の足し算は単純に考えると

z ← (x + y) % p
return z

のようにプログラムを書けば計算が可能となります．

しかし，暗号で利用される_p_は256bit等と非常に大きいので，単純に考えて余りを求めるだけにビット数分程度のクロックサイクルを要します．ちなみに，足し算や引き算は一桁クロックサイクルで実行できることがほとんどです．

そのため，高速化を図るには次のようにします．

z ← x + y
If z > p then z ← z - p
retun z

とすることで，高速な足し算と引き算で有限体の足し算を実装することが可能となります．

同じように引き算も，%を使ってプログラムを書くのではなく，x-yを実行したときに負の値になった場合に法を足せば同じ値になります．

z ← x - y
If 0 > z then z ← z + p
retun z