持ち運び不要の製品

2つの2進数の繰り上がりのない積は、これらの数の繰り上がりのない乗算 の結果です。この演算は、繰り上がり がより重要な位置に適用されずに破棄される点を除けば、概念的には長乗算のように機能します。これは、有限体上の演算、 特にGF ( 2 )上の多項式環であるGF(2)[ X ]からの多項式の乗算をモデル化するために使用できます。

この演算は、キャリー破棄加算が排他的論理和と同等であるため、 XOR 乗算とも呼ばれます。

2つの数とが与えられ、これらの数のビットが で表されると、これら2つの数の繰り上がりのない積は と定義され、各ビットは次のように入力数のビットの積の排他的論理和として計算されます。 ^[1]${\displaystyle \textstyle a=\sum _{i}a_{i}2^{i}}$${\displaystyle \textstyle b=\sum _{i}b_{i}2^{i}}$${\displaystyle a_{i},b_{i}\in \{0,1\}}$${\displaystyle \textstyle c=\sum _{i}c_{i}2^{i}}$${\displaystyle c_{i}}$

${\displaystyle c_{i}=\bigoplus _{j=0}^{i}a_{j}b_{ij}}$

すべての数値が 2 進数で与えられ、 a = 10100010 ₂およびb = 10010110 ₂であるとします。この場合、これらの繰り上がりのない乗算は、基本的に、繰り上がりを無視して長い乗算を実行した場合に得られる結果になります。

                  1 0 1 0 0 0 1 0 = 1 ...
   ----------|---|----------|--
   1 0 0 1 0 1 1 0|0 0 0 0 0 0 0
       1 0 0 1 0 1 1 0|0 0 0 0 0
               1 0 0 1 0 1 1 0|0
   ------------------------------
   1 0 1 1 0 0 0 1 1 1 0 1 1 0 0
             ^ ^

したがって、 aとbの繰り上がりのない積はc = 101100011101100 ₂になります。数aで設定されているすべてのビットに対して、数bは、 aのビットの位置によって示されるビット数だけ左にシフトされます。次に、これらのシフトされたバージョンはすべて、通常の長い乗算で使用される通常の加算ではなく、排他的論理和を使用して結合されます。これは で示される列に見られ^、通常の加算では左側の列への繰り上がりが発生しますが、ここでは発生しません。

キャリーレス積は、体GF(2)上の多項式の乗算として見ることもできます。これは、排他的論理和がこの体における加算に対応するためです。

上記の例では、数値aとbは多項式に対応しています。

${\displaystyle A=\sum _{i}a_{i}X^{i}=X^{7}+X^{5}+X^{1}\qquad B=\sum _{i}b_{i}X^{i}=X^{7}+X^{4}+X^{2}+X^{1}}$

そしてこれらの積は

${\displaystyle C=A\cdot B=\sum _{i}c_{i}X^{i}=X^{14}+X^{12}+X^{11}+X^{7}+X^{6}+X^{5}+X^{3}+X^{2}}$

これは上で計算された数値cがエンコードしたものです。GF (2) の演算のおかげで、どのようにエンコードされるかに注目してください。これは例でマークされた列に対応します。 ${\displaystyle (X^{7}\cdot X^{1})+(X^{1}\cdot X^{7})\equiv 0}$${\displaystyle (X^{7}\cdot X^{2})+(X^{5}\cdot X^{4})\equiv 0}$^

^{GF(2 n} )、すなわち位数が2のべき乗である有限体の元は、通常、GF(2)[ X ]の多項式として表される。 このような2つの体元の乗算は、対応する多項式の乗算と、それに続く体の構成から得られる何らかの既約多項式に関する簡約で構成される。多項式が2進数としてエンコードされている場合、この計算の最初のステップを実行するために、繰り上がりのない乗算を使用できる。

このような分野は、暗号化や一部のチェックサムアルゴリズムに応用されています。

最近のx86プロセッサはCLMUL 命令セットをサポートしており、この操作を実行するためのハードウェア命令を提供します。

これは、 RISC-Vビット操作ISA 拡張Zbc: キャリーレス乗算 の一部でもあります。

他のターゲットの場合、上記の計算をソフトウェア アルゴリズムとして実装することが可能であり、多くの暗号化ライブラリには有限体算術演算の一部として実装が含まれます。

長い乗算から繰り上がりを取り除いた結果としての繰り上がりのない積の定義は、 2 以外の基数にも容易に適用できます。ただし、結果は基数によって異なるため、基数は演算の重要な部分です。この演算は一般に 2 進数で動作するコンピューターで使用されるため、実際に使用されるのは上記の 2 進数形式です。

他の素数位数の有限体上の多項式には応用がありますが、そのような多項式の係数を単一の数の桁として扱うことはあまり一般的ではないため、そのような多項式の乗算は繰り上がりのない数の乗算とは見なされません。

• CLMUL命令セット、x86 ISA拡張
• 有限体演算
• ガロア/カウンターモード