您如何得出在伽羅瓦域中除以 3 的算法？
維基百科的這個函式計算 AES 中使用的 sbox：
#include <stdint.h> #define ROTL8(x,shift) ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift)))) void initialize_aes_sbox(uint8_t sbox[256]) { uint8_t p = 1, q = 1; /* loop invariant: p * q == 1 in the Galois field */ do { /* multiply p by 3 */ p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0); /* divide q by 3 (equals multiplication by 0xf6) */ q ^= q << 1; q ^= q << 2; q ^= q << 4; q ^= q & 0x80 ? 0x09 : 0; /* compute the affine transformation */ uint8_t xformed = q ^ ROTL8(q, 1) ^ ROTL8(q, 2) ^ ROTL8(q, 3) ^ ROTL8(q, 4); sbox[p] = xformed ^ 0x63; } while (p != 1); /* 0 is a special case since it has no inverse */ sbox[0] = 0x63; }它包含了我花了一段時間才理解的微妙細節。最讓我困惑的是除以 3。在伽羅華域中 246 乘以 3 是 1，所以 246 是 3 的倒數，乘以 246 等於除以 3。這一點我很清楚，但是我無法從這個事實到這些行做出合乎邏輯的飛躍：
q ^= q << 1; q ^= q << 2; q ^= q << 4; q ^= q & 0x80 ? 0x09 : 0;我按照 FIPS.197 文件中描述的方式執行了乘法運算（將原始值乘以 2 的指數相加）。它很冗長，所以我想出了一個系統。我將被乘數的位命名為 a、b、c、d、e、f、g 和 h。你大概能看出我在做什麼。我已經像你應該的那樣減少了多項式。為了得到 246，我們需要加上指數 128、64、32、16、4 和 2：
2 .b...... ..c..... ...d.... a...e... a....f.. ......g. a......h a....... 4 ..c..... ...d.... a...e... ab...f.. .b....g. a......h ab...... .b...... 16 a...e... ab...f.. .bc...g. a.cd...h ab.d.... .bc..... ..cd.... ...d.... 32 ab...f.. .bc...g. a.cd...h .b.de... abc.e... ..cd.... a..de... a...e... 64 .bc...g. a.cd...h .b.de... ..c.ef.. abcd.f.. a..de... .b..ef.. ab...f.. 128 a.cd...h .b.de... ..c.ef.. a..d.fg. abcde.g. .b..ef.. a.c..fg. .bc...g.對每一列中的所有字母進行異或運算會產生一個結果位。結果如下：
a^b^c^d^e^f^g^h, b^c^d^e^f^g^h, c^d^e^f^g^h, d^e^f^g^h, a^b^c^d, f^g^h, g^h, a^b^c^d^e^f^g.回到維基百科算法；它看起來像是乘以 255 - 除了不是用每一步的多項式減少它後面跟著一個與 9 的條件異或。
前三行的計算結果為：
a^b^c^d^e^f^g^h, b^c^d^e^f^g^h, c^d^e^f^g^h, d^e^f^g^h, e^f^g^h, f^g^h, g^h, h最後一行有效地將位 7 (a^b^c^d^e^f^g^h) 異或到位 3 (e^f^g^h) 和 0 (a)。在位 3 中，e、f、g 和 h 相互抵消。在位 0 h 中抵消。這是最終結果：
a^b^c^d^e^f^g^h, b^c^d^e^f^g^h, c^d^e^f^g^h, d^e^f^g^h, a^b^c^d, f^g^h, g^h, a^b^c^d^e^f^g.幸運的是它產生了相同的結果，但是你是如何得出這個算法的呢？
我是該程式碼的原作者，我對它的那部分並不感到非常自豪，但這裡有一種方法可以了解它為什麼有效。
乘以“3”（我原來的評論說 $ x+1 $ ), 稍微重寫, 是
p ^= p << 1; p ^= original_p & 0x80 ? 0x1B : 0;如何反轉它並不明顯，因為在反轉時你無法訪問
original_p.但是可以顛倒操作順序：
p ^= p & 0x80 ? some_constant : 0; p ^= p << 1;0x1B = 00011011 二進制。00001001 變成 00011011 之後
p ^= (p << 1)。因此，some_constant應該是0x09。這更容易反轉。第一行是它自己的逆，而 的逆
p ^= p << 1是p ^= p << 1; p ^= p << 2; p ^= p << 4。可能有一些方法可以將其理解為“0xf6”的優化乘法，但如果有的話，我沒有看到它。
如果我們將乘法反轉，程式碼會更好 $ x $ （“2”），因為在這種情況下，輸入的高位最終成為輸出的低位，在反轉時很容易測試。很遺憾， $ x $ 在此欄位表示中沒有完整的順序。