Universalidad de $ (+, \ oplus) $ sobre $ \ mathbb {z} _2 ^ n $

Question

Let $ \ mathbb {z} _2 ^ n $ Be el campo de los bitvectores de longitud $ n $ y definir el operador XOR $ \ oplus $ y el operador de la adición $ + $ sobre este campo, Con $ + $ con la semántica de desbordamiento habitual (tome la adición modulo $ 2 ^ n $ ).

es posible expresar cualquier mapeo $ \ mathbb {z} _2 ^ n \ rudotrow \ mathbb {z} _2 ^ n $ enteramente en términos de $ \ oplus $ y $ + $ ? Parece que podría ser posible debido a la no linealidad de $ + $ .

---

Por ejemplo, si nos dieron $ n= 2 $ y ese $ f (0)= 3, f (1)= 1, F (2)= 3, F (3)= 1 $ , luego podríamos construir $ f $ como $ f (x)= x \ oplus (x + 3) $ .

Answer 1

nope.Por ejemplo, no puede expresar la función $ f (x)= x >> 1 $ .En general, el bit menos significativo de $ f (x) $ depende solo del bit menos significativo de $ x$ .Puede probar que por inducción estructural, utilizando las siguientes dos propiedades: $ (A \ oplus b) \ bmod 2= (A \ bmod 2) \ oplus (B \ bmod 2) $ y $ (a + b) \ bmod 2= (A \ bmod 2) + (b \ bmod 2) \ bmod 2 $ .