XOR交換アルゴリズム
二項演算 XOR をビット列に対して行う場合、次のような特性がある(XOR を ⊗ {\displaystyle \otimes } で表す)。
L1. 交換法則: A ⊗ B = B ⊗ A {\displaystyle A\otimes B=B\otimes A}
L2. 結合法則: ( A ⊗ B ) ⊗ C = A ⊗ ( B ⊗ C ) {\displaystyle (A\otimes B)\otimes C=A\otimes (B\otimes C)}
L3. 単位元の存在: Z = 0 {\displaystyle Z=0} という値があり、任意の A {\displaystyle A} について A ⊗ Z = A {\displaystyle A\otimes Z=A} が成り立つ。
L4. 各要素は逆元を持つ: 任意の A {\displaystyle A} について、 A ⊗ A − 1 = Z {\displaystyle A\otimes A^{-\!1}=Z} となる値 A − 1 {\displaystyle A^{-\!1}} が存在する。 L4a. 実際、各要素は自身の逆元である: A ⊗ A = 0 {\displaystyle A\otimes A=0}
最初の4つの特性はアーベル群の定義である。最後の特性は XOR 特有のものである。
以下の表で、2つのレジスタ R1 と R2 があり、それぞれの初期値が A と B であるとする。この表では、XOR交換アルゴリズムをステップ単位に実施したとき、各ステップで上記特性のどれが適用されるかを示している。