對單個十六進製字元進行異或運算的 16*16 網格中唯一可能的 Cayley 表的數量是多少？
幾天前，我設計並 s-box 然後推導出以下 Cayley 表，其中包含以下範圍內的十六進制數字的所有可能 XOR 輸出 $ {2^4} $ 並且很好奇在 16*16 網格中存在多少這樣的“有效”可能配置，以及表格在哪裡仍然是 Abelian 並且具有對稱對角線，例如這個？（除了旋轉這個）。（見下面的更新：XOR Cayley 表告訴我們給定範圍的密文空間是什麼？）。
換句話說，當使用上/左邊緣作為座標查找值或下/右邊緣並且沒有值重複時，可以設計多少種 16*16 表來顯示任何單個十六進製字元的 XOR 結果對於任何給定的行或列（即使其成為 Cayley 表）不止一次。
$$ \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \oplus \ & \text{0} & \text{5} & \text{10} & \text{15} & \text{1} & \text{4} & \text{11} & \text{14}& \text{2} & \text{7} & \text{8} & \text{13}& \text{3} & \text{6} & \text{9} & \text{12}\ \hline \text{0} &0 &5 &A &F &1 &4 &B &E &2 &7 &8 &D &3 &6 &9 &C\ \hline \text{5} &5 &0 &F &A &4 &1 &E &B &7 &2 &D &8 &6 &3 &C &9\ \hline \text{10} &A &F &0 &5 &B &E &1 &4 &8 &D &2 &7 &9 &C &3 &6\ \hline \text{15} &F &A &5 &0 &E &B &4 &1 &D &8 &7 &2 &C &9 &6 &3\ \hline \text{1} &1 &4 &B &E &0 &5 &A &F &3 &6 &9 &C &2 &7 &8 &D\ \hline \text{4} &4 &1 &E &B &5 &0 &F &A &6 &3 &C &9 &7 &2 &D &8\ \hline \text{11} &B &E &1 &4 &A &F &0 &5 &9 &C &3 &6 &8 &D &2 &7\ \hline \text{14} &E &B &4 &1 &F &A &5 &0 &C &9 &6 &3 &D &8 &7 &2\ \hline \text{2} &2 &7 &8 &D &3 &6 &9 &C &0 &5 &A &F &1 &4 &B &E\ \hline \text{7} &7 &2 &D &8 &6 &3 &C &9 &5 &0 &F &A &4 &1 &E &B\ \hline \text{8} &8 &D &2 &7 &9 &C &3 &6 &A &F &0 &5 &B &E &1 &4\ \hline \text{13} &D &8 &7 &2 &C &9 &6 &3 &F &A &5 &0 &E &B &4 &1\ \hline \text{3} &3 &6 &9 &C &2 &7 &8 &D &1 &4 &B &E &0 &5 &A &F\ \hline \text{6} &6 &3 &C &9 &7 &2 &D &8 &4 &1 &E &B &5 &0 &F &A\ \hline \text{9} &9 &C &3 &6 &8 &D &2 &7 &B &E &1 &4 &A &F &0 &5\ \hline \text{12}& C &9 &6 &3 &D &8 &7 &2 &E &B &4 &1 &F &A &5 &0\ \hline \end{array} $$ $$ \text{ designed by Steven Hatzakis 2019} $$
**注意：**我見過另一個這樣的表，其中查找值是線性的（https://i.stack.imgur.com/eIe24.png並在此處提到https://math.stackexchange.com/questions/116736/cayley -table-with-the-identity-along-a-diagonal/3260978#3260978）。此外，下表不需要額外的查找頂行和左列，因為可以使用 16*16 表本身的第一列和頂列（但我添加它們是為了方便/可讀性）。
此外，可以使用右側和底部邊緣執行查找（即，如果使用頂部/左側進行查找 $ {5 \oplus 4 = 1} $ ，該座標答案共享給 $ {8 \oplus 9 = 1 } $ 使用底部/右側時）。
理論上有多少這樣的 Caley XOR 表可能具有 16*16 表的這種品質？
PS 出於加密目的，這樣的表配置可能是一個潛在的 256 個字元的十六進製字元串和/或與 s-box 設計有關係，所以我認為這個問題值得在這裡探討。
更新：如果我們將 1717 表中最左邊的列視為可能的鍵空間 $ {2^4} $ 最上面的行作為消息空間 $ {2^4} $ , 結果是 $ {2^8} $ 1616 表中的密文代表單個十六進製字元的所有可能的異或組合？如果是這樣，為什麼總共只有 51 個唯一的（如果我們將一個的唯一性定義為為三個彼此異或的變數編寫給定 XOR 方程的六種可能方法，例如這個：${
- $ {8 \oplus c = 4} $ , $ {(Message \oplus Private Key = Ciphertext)} $
- $ {c \oplus 8 = 4} $ , $ {( Private Key \oplus Message = Ciphertext)} $
- $ {c \oplus 4 = 8} $ , $ {(Private Key \oplus Ciphertext = Message)} $
- $ {4 \oplus c = 8} $ , $ {(Ciphertext \oplus Private Key = Message)} $
- $ {4 \oplus 8 = c} $ , $ {(Ciphertext \oplus Message = Private Key)} $
- $ {8 \oplus 4 = c} $ , $ {(Message \oplus Ciphertext = Private Key)} $
這裡是 4 位 XOR 函式的映射/真值表，以顏色編碼顯示了 51 個方程和關係：
**注意：**我數了 51，但 0 XOR 0 = 0 在內表上顯示的方式與排除用於查找的額外第 17 列/行時所有其他值的方式不同，如下所示。
$$ \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \oplus \ \ \hline \text{} &0 &5 &A &F &1 &4 &B &E &2 &7 &8 &D &3 &6 &9 &C\ \hline \text{} &5 &0 &F &A &4 &1 &E &B &7 &2 &D &8 &6 &3 &C &9\ \hline \text{} &A &F &0 &5 &B &E &1 &4 &8 &D &2 &7 &9 &C &3 &6\ \hline \text{} &F &A &5 &0 &E &B &4 &1 &D &8 &7 &2 &C &9 &6 &3\ \hline \text{} &1 &4 &B &E &0 &5 &A &F &3 &6 &9 &C &2 &7 &8 &D\ \hline \text{} &4 &1 &E &B &5 &0 &F &A &6 &3 &C &9 &7 &2 &D &8\ \hline \text{} &B &E &1 &4 &A &F &0 &5 &9 &C &3 &6 &8 &D &2 &7\ \hline \text{} &E &B &4 &1 &F &A &5 &0 &C &9 &6 &3 &D &8 &7 &2\ \hline \text{} &2 &7 &8 &D &3 &6 &9 &C &0 &5 &A &F &1 &4 &B &E\ \hline \text{} &7 &2 &D &8 &6 &3 &C &9 &5 &0 &F &A &4 &1 &E &B\ \hline \text{} &8 &D &2 &7 &9 &C &3 &6 &A &F &0 &5 &B &E &1 &4\ \hline \text{} &D &8 &7 &2 &C &9 &6 &3 &F &A &5 &0 &E &B &4 &1\ \hline \text{} &3 &6 &9 &C &2 &7 &8 &D &1 &4 &B &E &0 &5 &A &F\ \hline \text{} &6 &3 &C &9 &7 &2 &D &8 &4 &1 &E &B &5 &0 &F &A\ \hline \text{} &9 &C &3 &6 &8 &D &2 &7 &B &E &1 &4 &A &F &0 &5\ \hline \text{}& C &9 &6 &3 &D &8 &7 &2 &E &B &4 &1 &F &A &5 &0\ \hline \end{array} $$
理論上有多少這樣的 Caley XOR 表可能具有 16*16 表的這種品質？
定義我們想要計算的內容至關重要。我將約束讀作
一張桌子 $ r $ 內部法的行列 $ \boxplus $ 上 $ \Bbb Z_r $ （非負整數小於 $ r $ )，行和列的順序相同。更確切地說：
表有 $ r $ 線條和 $ r $ 列 $ r^2 $ 條目 $ T_{x,y} $ , 加上 $ r $ 標籤 $ L_i $ . 表格條目、行號和列號在 $ \Bbb Z_r $ . $$ \begin{array}{c|ccccc} \boxplus&L_0&L_1&L_2&\ldots&L_{(r-1)}\ \hline L_0&T_{0,0}&T_{1,0}&T_{2,0}&\ldots&T_{(r-1),0}\ L_1&T_{0,1}&T_{1,1}&T_{2,1}&\ldots&T_{(r-1),1}\ L_2&T_{0,2}&T_{1,2}&T_{2,2}&\ldots&T_{(r-1),2}\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\ L_{(r-1)}&T_{0,(r-1)}&T_{1,(r-1)}&T_{2,(r-1)}&\ldots&T_{(r-1),(r-1)} \end{array} $$
標籤 $ L_i $ 是一個排列 $ \Bbb Z_r $ .
每當 $ L_x=u $ 和 $ L_y=v $ , 表和內律 $ \boxplus $ 是這樣的： $ u\boxplus v\ =\ T_{x,y} $ .
那內部法 $ \boxplus $ 是 $ \oplus $ （異或或異或）。等效地，
$ \boxplus $ 有中性 $ 0 $ : $ \forall u\in\Bbb Z_r, u\boxplus 0\ =\ 0\boxplus u\ =\ u $ .
$ \boxplus $ 是關聯的： $ \forall u,v,w\in\Bbb Z_r,\ (u\boxplus v)\boxplus w\ =\ u\boxplus (v\boxplus w) $ .
$ \boxplus $ 是可逆的： $ \forall u\in\Bbb Z_r,\exists v\in\Bbb Z_r,\ u\boxplus v =\ v\boxplus u =\ 0 $ .
$ \boxplus $ 是可交換的： $ \forall u,v\in\Bbb Z_r,\ u\boxplus v=v\boxplus u $ .
$ \boxplus $ 是內捲的： $ \forall u\in\Bbb Z_r,\ u\boxplus u=0 $ .
該表在次對角線上是對稱的： $ \forall x,y\in\Bbb Z_r $ , $ T_{x,y}=T_{(r-1-y),(r-1-x)} $ .
$ L_0=0 $ .
約束 1 和 2.4 意味著 $ T $ 在主對角線上是對稱的。約束 2.5 進一步暗示這條對角線是所有 $ 0 $ .
假設 1，約束 2.1 到 2.3 是 $ \boxplus $ 作為一個團體法 $ \Bbb Z_r $ . 2.4 專門針對一個對稱群。2.5 進一步專攻法律 $ \oplus $ 並暗示 $ r $ 是二的冪。
假設 1 和 2.1，約束 4 意味著 $ L $ 也是的頂行和左列 $ T $ . 約束 3 進一步暗示它是底部和右側的行，向後閱讀。
我們限制在 $ r=2^n $ , $ n>0 $ . 給定約束 1 和 2，約束 3 嚴格等價於： $$ \forall s\in\Bbb Z_r,\ L_s\oplus L_{(r-s-1)}\ =\ L_0\oplus L_{r-1} $$
因此，要構造任何可能的表：
放 $ L_0\gets0 $ ;
自由選擇 $ L_{r-1} $ 之間 $ r-1 $ 標籤值不是 $ 0 $ ;
為了 $ s $ 從 $ 1 $ 至 $ r/2 $ ， 選擇 $ L_{r-1-s} $ 和 $ L_s $ 如下：
- 自由選擇 $ L_{r-1-s} $ 之間 $ r-2m $ 標記先前未選擇的值；
- 放 $ L_s\gets L_0\oplus L_{r-1}\oplus L_{r-1-s} $ ;
計算 $ r^2 $ 價值觀 $ T_{x,y}\gets L_x\oplus L_y $ .
可能分配的數量是選擇數量的乘積（我們對右半部分的 $ L $ ; 左半邊的任務都被強制了）。這個數字是 $ (r-1) $ 乘以偶數的乘積 $ r-2 $ 向下 $ 2 $ . 那是 $ (r/2-1)!,2^{r/2-1},(r-1) $ .
對於問題 $ r=16 $ , 給 $ 7!\times2^7\times15, = ,9676800 $ 可能的任務。
我寫了一個簡短的 C 程序來生成這些表，線上嘗試。要生成的表由從 0 到 9676799 的索引指定。這裡有 8 個範例（故意包括索引為 1971611 時的問題；這是最後一次向右滾動）。
\| 0 6 5 B 1 4 7 3 A E D 8 2 C F 9 \| 0 1 D 7 B E A 4 6 8 C 9 5 F 3 2 \| 0 9 B F C 7 E 2 8 4 D 6 5 1 3 A \| 0 5 1 B 4 D A C F 9 E 7 8 2 6 3 \| 0 D 8 F A 7 5 9 2 E C 1 4 3 6 B \| 0 D 1 2 B E C 7 3 8 A F 6 5 9 4 \| 0 5 A F 1 4 B E 2 7 8 D 3 6 9 C \| 0 9 2 1 8 E 6 F A 3 B D 4 7 C 5 -+-------------------------------- -+-------------------------------- -+-------------------------------- -+-------------------------------- -+-------------------------------- -+-------------------------------- -+-------------------------------- -+-------------------------------- 0| 0 6 5 B 1 4 7 3 A E D 8 2 C F 9 0| 0 1 D 7 B E A 4 6 8 C 9 5 F 3 2 0| 0 9 B F C 7 E 2 8 4 D 6 5 1 3 A 0| 0 5 1 B 4 D A C F 9 E 7 8 2 6 3 0| 0 D 8 F A 7 5 9 2 E C 1 4 3 6 B 0| 0 D 1 2 B E C 7 3 8 A F 6 5 9 4 0| 0 5 A F 1 4 B E 2 7 8 D 3 6 9 C 0| 0 9 2 1 8 E 6 F A 3 B D 4 7 C 5 6| 6 0 3 D 7 2 1 5 C 8 B E 4 A 9 F 1| 1 0 C 6 A F B 5 7 9 D 8 4 E 2 3 9| 9 0 2 6 5 E 7 B 1 D 4 F C 8 A 3 5| 5 0 4 E 1 8 F 9 A C B 2 D 7 3 6 D| D 0 5 2 7 A 8 4 F 3 1 C 9 E B 6 D| D 0 C F 6 3 1 A E 5 7 2 B 8 4 9 5| 5 0 F A 4 1 E B 7 2 D 8 6 3 C 9 9| 9 0 B 8 1 7 F 6 3 A 2 4 D E 5 C 5| 5 3 0 E 4 1 2 6 F B 8 D 7 9 A C D| D C 0 A 6 3 7 9 B 5 1 4 8 2 E F B| B 2 0 4 7 C 5 9 3 F 6 D E A 8 1 1| 1 4 0 A 5 C B D E 8 F 6 9 3 7 2 8| 8 5 0 7 2 F D 1 A 6 4 9 C B E 3 1| 1 C 0 3 A F D 6 2 9 B E 7 4 8 5 A| A F 0 5 B E 1 4 8 D 2 7 9 C 3 6 2| 2 B 0 3 A C 4 D 8 1 9 F 6 5 E 7 B| B D E 0 A F C 8 1 5 6 3 9 7 4 2 7| 7 6 A 0 C 9 D 3 1 F B E 2 8 4 5 F| F 6 4 0 3 8 1 D 7 B 2 9 A E C 5 B| B E A 0 F 6 1 7 4 2 5 C 3 9 D 8 F| F 2 7 0 5 8 A 6 D 1 3 E B C 9 4 2| 2 F 3 0 9 C E 5 1 A 8 D 4 7 B 6 F| F A 5 0 E B 4 1 D 8 7 2 C 9 6 3 1| 1 8 3 0 9 F 7 E B 2 A C 5 6 D 4 1| 1 7 4 A 0 5 6 2 B F C 9 3 D E 8 B| B A 6 C 0 5 1 F D 3 7 2 E 4 8 9 C| C 5 7 3 0 B 2 E 4 8 1 A 9 D F 6 4| 4 1 5 F 0 9 E 8 B D A 3 C 6 2 7 A| A 7 2 5 0 D F 3 8 4 6 B E 9 C 1 B| B 6 A 9 0 5 7 C 8 3 1 4 D E 2 F 1| 1 4 B E 0 5 A F 3 6 9 C 2 7 8 D 8| 8 1 A 9 0 6 E 7 2 B 3 5 C F 4 D 4| 4 2 1 F 5 0 3 7 E A 9 C 6 8 B D E| E F 3 9 5 0 4 A 8 6 2 7 B 1 D C 7| 7 E C 8 B 0 9 5 F 3 A 1 2 6 4 D D| D 8 C 6 9 0 7 1 2 4 3 A 5 F B E 7| 7 A F 8 D 0 2 E 5 9 B 6 3 4 1 C E| E 3 F C 5 0 2 9 D 6 4 1 8 B 7 A 4| 4 1 E B 5 0 F A 6 3 C 9 7 2 D 8 E| E 7 C F 6 0 8 1 4 D 5 3 A 9 2 B 7| 7 1 2 C 6 3 0 4 D 9 A F 5 B 8 E A| A B 7 D 1 4 0 E C 2 6 3 F 5 9 8 E| E 7 5 1 2 9 0 C 6 A 3 8 B F D 4 A| A F B 1 E 7 0 6 5 3 4 D 2 8 C 9 5| 5 8 D A F 2 0 C 7 B 9 4 1 6 3 E C| C 1 D E 7 2 0 B F 4 6 3 A 9 5 8 B| B E 1 4 A F 0 5 9 C 3 6 8 D 2 7 6| 6 F 4 7 E 8 0 9 C 5 D B 2 1 A 3 3| 3 5 6 8 2 7 4 0 9 D E B 1 F C A 4| 4 5 9 3 F A E 0 2 C 8 D 1 B 7 6 2| 2 B 9 D E 5 C 0 A 6 F 4 7 3 1 8 C| C 9 D 7 8 1 6 0 3 5 2 B 4 E A F 9| 9 4 1 6 3 E C 0 B 7 5 8 D A F 2 7| 7 A 6 5 C 9 B 0 4 F D 8 1 2 E 3 E| E B 4 1 F A 5 0 C 9 6 3 D 8 7 2 F| F 6 D E 7 1 9 0 5 C 4 2 B 8 3 A A| A C F 1 B E D 9 0 4 7 2 8 6 5 3 6| 6 7 B 1 D 8 C 2 0 E A F 3 9 5 4 8| 8 1 3 7 4 F 6 A 0 C 5 E D 9 B 2 F| F A E 4 B 2 5 3 0 6 1 8 7 D 9 C 2| 2 F A D 8 5 7 B 0 C E 3 6 1 4 9 3| 3 E 2 1 8 D F 4 0 B 9 C 5 6 A 7 2| 2 7 8 D 3 6 9 C 0 5 A F 1 4 B E A| A 3 8 B 2 4 C 5 0 9 1 7 E D 6 F E| E 8 B 5 F A 9 D 4 0 3 6 C 2 1 7 8| 8 9 5 F 3 6 2 C E 0 4 1 D 7 B A 4| 4 D F B 8 3 A 6 C 0 9 2 1 5 7 E 9| 9 C 8 2 D 4 3 5 6 0 7 E 1 B F A E| E 3 6 1 4 9 B 7 C 0 2 F A D 8 5 8| 8 5 9 A 3 6 4 F B 0 2 7 E D 1 C 7| 7 2 D 8 6 3 C 9 5 0 F A 4 1 E B 3| 3 A 1 2 B D 5 C 9 0 8 E 7 4 F 6 D| D B 8 6 C 9 A E 7 3 0 5 F 1 2 4 C| C D 1 B 7 2 6 8 A 4 0 5 9 3 F E D| D 4 6 2 1 A 3 F 5 9 0 B 8 C E 7 E| E B F 5 A 3 4 2 1 7 0 9 6 C 8 D C| C 1 4 3 6 B 9 5 E 2 0 D 8 F A 7 A| A 7 B 8 1 4 6 D 9 2 0 5 C F 3 E 8| 8 D 2 7 9 C 3 6 A F 0 5 B E 1 4 B| B 2 9 A 3 5 D 4 1 8 0 6 F C 7 E 8| 8 E D 3 9 C F B 2 6 5 0 A 4 7 1 9| 9 8 4 E 2 7 3 D F 1 5 0 C 6 A B 6| 6 F D 9 A 1 8 4 E 2 B 0 3 7 5 C 7| 7 2 6 C 3 A D B 8 E 9 0 F 5 1 4 1| 1 C 9 E B 6 4 8 3 F D 0 5 2 7 A F| F 2 E D 4 1 3 8 C 7 5 0 9 A 6 B D| D 8 7 2 C 9 6 3 F A 5 0 E B 4 1 D| D 4 F C 5 3 B 2 7 E 6 0 9 A 1 8 2| 2 4 7 9 3 6 5 1 8 C F A 0 E D B 5| 5 4 8 2 E B F 1 3 D 9 C 0 A 6 7 5| 5 C E A 9 2 B 7 D 1 8 3 0 4 6 F 8| 8 D 9 3 C 5 2 4 7 1 6 F 0 A E B 4| 4 9 C B E 3 1 D 6 A 8 5 0 7 2 F 6| 6 B 7 4 D 8 A 1 5 E C 9 0 3 F 2 3| 3 6 9 C 2 7 8 D 1 4 B E 0 5 A F 4| 4 D 6 5 C A 2 B E 7 F 9 0 3 8 1 C| C A 9 7 D 8 B F 6 2 1 4 E 0 3 5 F| F E 2 8 4 1 5 B 9 7 3 6 A 0 C D 1| 1 8 A E D 6 F 3 9 5 C 7 4 0 2 B 2| 2 7 3 9 6 F 8 E D B C 5 A 0 4 1 3| 3 E B C 9 4 6 A 1 D F 2 7 0 5 8 5| 5 8 4 7 E B 9 2 6 D F A 3 0 C 1 6| 6 3 C 9 7 2 D 8 4 1 E B 5 0 F A 7| 7 E 5 6 F 9 1 8 D 4 C A 3 0 B 2 F| F 9 A 4 E B 8 C 5 1 2 7 D 3 0 6 3| 3 2 E 4 8 D 9 7 5 B F A 6 C 0 1 3| 3 A 8 C F 4 D 1 B 7 E 5 6 2 0 9 6| 6 3 7 D 2 B C A 9 F 8 1 E 4 0 5 6| 6 B E 9 C 1 3 F 4 8 A 7 2 5 0 D 9| 9 4 8 B 2 7 5 E A 1 3 6 F C 0 D 9| 9 C 3 6 8 D 2 7 B E 1 4 A F 0 5 C| C 5 E D 4 2 A 3 6 F 7 1 8 B 0 9 9| 9 F C 2 8 D E A 3 7 4 1 B 5 6 0 2| 2 3 F 5 9 C 8 6 4 A E B 7 D 1 0 A| A 3 1 5 6 D 4 8 2 E 7 C F B 9 0 3| 3 6 2 8 7 E 9 F C A D 4 B 1 5 0 B| B 6 3 4 1 C E 2 9 5 7 A F 8 D 0 4| 4 9 5 6 F A 8 3 7 C E B 2 1 D 0 C| C 9 6 3 D 8 7 2 E B 4 1 F A 5 0 5| 5 C 7 4 D B 3 A F 6 E 8 1 2 9 0（是否..）表（.. $ T $ ..) 代表單個十六進製字元的所有可能的 XOR 組合？
是的。約束 1 說明 $ T $ 是完整的表 $ u\boxplus v $ , 和約束 2 $ \boxplus $ 是異或。
（..）為什麼總共只有 51 個獨特的（..combinations of $ M,K,C $ 和 $ M\oplus K=C $ ，在訂單內）？
因為 $ a_n=(2^n+1)(2^n+2)/6 $ 有價值 $ 51 $ 為了 $ n=4 $ . 該序列是OEIS A007581，說明（沒有證據）：
a(n) is also the number of distinct solutions (avoiding permutations) to the equation: XOR(A,B,C)=0 where A,B,C are n-bit binary numbers. - Ramasamy Chandramouli, Jan 11 2009