暗号で使われる標数2の体の実装

多項式の加算 2個の多項式 a と b の加算を考えます。多項式の加算は同じ次数の係数同士を足したものでした。 a+b=(a_7 X^7 + \cdots + a_0)+(b_7 X^7 + \cdots + b_0) = (a_7 + b_7)X^7 + \cdots + (a_0+b_0). 各係数は 𝔽_2 の要素なので加算は排他的論理和です。それをビットごとにすればよいので、結局整数として排他的論理和を取ればよいです。引き算もaddと同じですね。 typedef uint8_t K; K add(K a, K b) { return a ^ b; } K sub(K a, K b) { return add(a, b); } 多項式の乗算 まずはナイーブな実装から考えましょう。 多項式 a と b を掛けた結果 c=ab を f=X^8+X^4+X^3+X+1 で割ります。f が