Universalität von $ (+, \ oplus) $ über $ \ mathbb {z} _2 ^ n $

Question

$ \ mathbb {z} _2 ^ n $ Seien Sie das Feld der Bitvektoren der Länge $ n $ und definieren Sie den XOR-Operator $ \ oplus $ und den Additions-Operator $ + $ über dieses Feld, mit $ + $ mit der üblichen Überlaufsemantik (Addition Modulo $ 2 ^ N $ ). .

ist es möglich, jeden Mapping $ F: \ MathBB {Z} _2 ^ n \ rightarrow \ mathbb {z} _2 ^ n $ vollständig in Bezug auf $ \ oplus $ und $ + $ ? Es scheint, als könnte es aufgrund der Nichtlinearität von $ + $ möglich sein.

---

zum Beispiel, wenn wir $ n= 2 $ erhalten würden, und diese $ f (0)= 3, f (1)= 1, f (2)= 3, f (3)= 1 $ , dann konnten wir $ f $ als $ f (x)= x \ oplus (x + 3) $ .

Answer 1

Nein.Beispielsweise können Sie die Funktion $ F (x)= x >> 1 $ nicht ausdrücken.Im Allgemeinen hängt das kleinste Bit von $ F (x) $ nur von dem geringstwertigen Bit von $ x ab$ .Sie können das nachweisen, dass durch strukturelle Induktion die folgenden zwei Eigenschaften verwendet werden: $ (A \ OPLUS B) \ BMOD 2= (A \ BMOD 2) \ OPLUS (B \ BMOD 2) $ $ und $ (A + B) \ BMOD 2= (A \ BMOD 2) + (B \ BMOD 2) \ BMOD 2 $ .

.