Universalité de $ (+, \ oplus) $ sur $ \ mathbb {z} _2 ^ n $

Question

let $ \ mathbb {z} _2 ^ n $ soit le champ de bitvecteurs de longueur $ n $ et définir l'opérateur XOR $ \ oplus $ et l'opérateur d'addition $ + sur ce champ, avec $ + $ ayant la sémantique de débordement habituelle (prenez l'addition modulo $ 2 ^ n $ ).

est-il possible d'exprimer n'importe quel mappage $ f: \ mathbb {z} _2 ^ n \ mathbb {z} _2 ^ n $ entièrement en termes de $ \ oplus $ et $ + $ ? Il semble que cela puisse être possible en raison de la non linéarité de $ + $ .

---

Par exemple, si on nous a donné $ n= 2 $ et que $ f (0)= 3, f (1)= 1, f (2)= 3, f (3)= 1 $ , nous pourrions construire $ f $ comme $ f (x)= x \ oplus (x + 3) $ .

Answer 1

Nope.Par exemple, vous ne pouvez pas exprimer la fonction $ f (x)= x >> 1 $ .En général, le bit le moins significatif de $ f (x) $ dépend uniquement du bit le moins significatif de x $ x$ .Vous pouvez prouver que par induction structurelle, en utilisant les deux propriétés suivantes: $ (a \ oplus b) \ bmod 2= (A \ bmod 2) \ oplus (b \ bmod 2) $ et $ (A + B) \ bmod 2= (A \ bmod 2) + (b \ bmod 2) \ bmod 2 $ .