$（+、\ Oplus）$ over $ \ mathbb {z} _2 ^ n $

Question

$ \ mathbb {z} _2 ^ n $ 長さのビットベクトルのフィールドになる $ n $ とXOR演算子 $ + $ を定義します。 通常のオーバーフローセマンティクスを持つ（追加モジュロ $ 2 ^ n $ ）を持つ。

マッピング $ f：\ mathbb {z} _2 ^ ^ n \ rightarrow \ mathbb {z} _2 ^ n $ ^ n $ $ \ oplus $ と $ + $ ？ $ + $ の非線形性のために可能かもしれないようです。

---

たとえば、 $ n= 2 $ を指定した場合、その $ f（0）= 3、f （1）= 1、f（2）= 3、f（3）= 1 $ 、次に $ f $ を $ f（x）= x \ oplus（x + 3）$ 。

Answer 1

いいえ。たとえば、関数 $ f（x）= x >> 1 $ を表現することはできません。一般に、 $ f（x）$ の最下位ビットは、 $ xの最下位ビットにのみ異なります。$ 。次の2つのプロパティを使用して、構造の誘導によって証明できます。 $（A \ Oplus b）\ bmod 2=（a \ bmod 2）\ Oplus（b \ bmod 2）$と $（a + b）\ bmod 2=（a \ bmod 2）+（b \ bmod 2）\ bmod 2 $ 。