Entendendo o algoritmo da Intel para reduzir um módulo polinomial e um polinômio irredutível

Estou lendo este white paper da Intel sobre multiplicação sem transporte . Descreve a multiplicação de polinômios em$\text{GF}(2^n)$. Em um nível alto, isso é realizado em duas etapas: (1) multiplicação de polinômios sobre$\text{GF}(2)$e (2) reduzir o módulo de resultado em um polinômio irredutível. Usamos a representação "padrão" de polinômios de cadeia de bits, ou seja,$x^3+x+1 = [1011]$.

O artigo fornece um algoritmo para o cálculo do polinômio restante na página 16 no algoritmo 3. No entanto, estou tendo problemas para entender o algoritmo de redução nas páginas 16-17 (Algoritmo 4). Essencialmente, acho que precisamos do algoritmo 4 para campos maiores quando nossos resultados parciais ou já não cabem mais em 128 bits. Eles dão um exemplo para a multiplicação de dois polinômios em$\text{GF}(2^{128})$.

De onde vêm as "constantes mágicas" 63, 62 e 57 para os turnos à direita e as "constantes mágicas" 1, 2 e 7 para os turnos à esquerda?

Por exemplo, como generalizar o algoritmo para campos menores, digamos $\text{GF}(2^{32})$? Os valores de deslocamento correspondentes seriam então 15, 14, 9 e 1, 2, 7?

Na etapa final 4, o algoritmo diz para você "XOR $[E_1:E_0]$, $[F_1:F_0]$e $[G_1:G_0]$ um com o outro e $[X_3:D]$"

porque nós fazemos isso? Tanto quanto posso ver, o resultado dessa operação XOR não é armazenado em nenhum lugar nem usado em nenhum lugar. De alguma forma, é usado para computação$[H_1 : H_0]$?

O campo de Galois $GF(2^{128})$tem muitas representações "concretas" diferentes. Uma representação popular está usando polinômios em$GF(2)[x]$ (ou seja, com coeficientes em $GF(2)$) módulo algum polinômio irredutível de grau $128$digamos $x^{128}+x^7+x^2+x^1+x^0$. As constantes mágicas$7,2,1,0$provêm desse polinômio irredutível em particular. Você não vê$0$ já que não há necessidade de mudar $0$. Da mesma forma, as constantes mágicas$57,62,63,64$ são os complementos das constantes acima em relação a $64$. Novamente, você não precisa mudar$64$ já que os registros são $64$bits de largura. Se tivéssemos usado algum outro polinômio irredutível, as constantes teriam sido diferentes.

Em relação à etapa 4, $[H_1:H_0]$ resultados do XORing $[E_1:E_0],[F_1:F_0],[G_1:G_0],[X_3:D]$. Isso implementa a operação de MODing por$x^{128} + x^7 + x^2 + x^1 + x^0$. A ideia é que modulo esse polinômio,$x^{128} = x^7+x^2+x^1+^0$; Além disso, é XOR. Os diferentes summands correspondem a esses diferentes monômios - veja se você consegue encontrar a correspondência.

Para completar, detalharei a resposta de Yuval um pouco mais através de um exemplo de multiplicação de dois polinômios $A$ e $B$ no $\text{GF}(2^{16})$. Deixei

$$A = [0001|1100|1110] = x^8 + x^7 + x^6 + x^3 + x^2 + x,$$ e $$B = [0100|0101|0111] = x^{10} + x^6 + x^4 + x^2 + x + 1.$$ A multiplicação de $A$ e $B$ sobre $\text{GF}(2)$ é então $$C = [0000|0000|0000|0111 | 0101|0010|0000|1010].$$

Em seguida, calculamos para $\text{GF}(2^{16})$ o polinômio

$$q^+ = x^{32}+x^{21}+x^{19}+x^{18}+x^{16}+x^{10}+x^6+x^4+1.$$ Agora queremos multiplicar $q^+$ com os altos bits de $C$e mantenha os 32 bits mais altos desse cálculo para processamento posterior. Para esse fim, usamos o algoritmo 4 (Etapa 1-2). Vamos denotar$C$ de $[X_3:X_2:X_1:X_0]$, onde cada $X_i$tem 8 bits. Em seguida, mudamos para a direita$X_3$ com 28, 26, 22, 16, 14, 13 e, finalmente, com 11. Portanto, temos no total 7 "variáveis ​​temporárias" e as XORamos com $X_2$. Isto resulta em$111_2$, que é o que queríamos.

Na parte inferior do produto da próxima etapa, observe que obtemos os turnos à esquerda de $g^*$, definido na página 16.