快速減少高飛_(2128)GF(2128)高飛_(2128)GF(2^{128})使用x86 PCLMULQDQ

現代 x86 CPU 支持該PCLMULQDQ指令，該指令執行兩個 64 位數字的 XOR 乘法，而不是加法乘法（即典型的算術乘法）。這使得 XOR 乘法為 $ GF(2^{128}) $ 明顯更快。

然而，它只是乘法的一半 $ GF(2^{128}) $ ：在異或乘法之後，你得到一個 256 位的結果，然後需要通過模數來減少（0x100000000000000000000000000000087對於伽羅瓦/計數器模式）。

當 CPU 的硬體加速僅用於 XOR 乘法時，如何進行 XOR 除法？我曾想過使用CRC32指令來執行 XOR 除法步驟，但遺憾的是，CRC32將模數硬連線為0x11EDC6F41.

基本上，要（天真地）通過 實現模組化約簡M = (1 << 128) + 0x87，您需要：

1. 取高128 位 $ x_H $ 的 256 位（實際上是 255 位，因為永遠無法設置高位）PCLMULQDQ結果 $ x = x_H | x_L $ ,
2. 將它們下移 128 位，
3. 將它們乘以0x87,
4. 將結果與低 128 位進行異或 $ x_L $ 的 256 位結果，和
5. 重複（見下面的註釋）。

步驟 3 可以用 來實現PCLMULQDQ，但由於其中一個被乘數是一個小常數，因此只用離散移位和 XOR 來實現它可能更有效。

請注意，第 3 步（以及第 4 步）的結果可能比 128 位長——在這種情況下最多長 6 位——因此可能需要再次減少。在這第二次縮減中， $ x_H $ 最多有 6 位長（因此第 3 步的結果最多有 13 位長），所以這個 pass 實現起來更簡單，並且保證不會溢出，需要第三遍。

（此外，如果您可以確定原始被乘數之一的長度最多為 122 位，那麼 $ x_H $ 最多 121 位長，因此第 3 步不能溢出 128 位。這可以簡化實現，尤其是不需要第二次歸約。）

在步驟 2-4 中，我們在這裡真正要做的是計算x' = x - M * x_H, wherex_H = x >> 128和乘法和減法都是無進位的。當然，無進位二進制減法與無進位二進制加法相同，即異或。但是，在這裡將其視為減法可以更好地概括，並且也更清楚地解釋了這種方法為何有效：我們實際上只是M從結果中減去倍數，以便清除它的上半部分。

我沒有詳細查看fgrieu 連結的英特爾論文，但我懷疑他們正在做一些比這種天真的減少更聰明、更快的事情。如果他有更多時間，我會讓他總結論文。:)

引用自：https://crypto.stackexchange.com/questions/30029