Verständnis des Intel-Algorithmus zum Reduzieren eines Polynommoduls zu einem irreduziblen Polynom

Ich lese dieses Intel-Whitepaper zur Multiplikation ohne Übertrag . Es beschreibt die Multiplikation von Polynomen in$\text{GF}(2^n)$. Auf hoher Ebene wird dies in zwei Schritten durchgeführt: (1) Multiplikation von Polynomen über$\text{GF}(2)$und (2) Reduzieren des Ergebnismoduls zu einem irreduziblen Polynom. Wir verwenden die "Standard" -Bitstring-Darstellung von Polynomen, d. H.$x^3+x+1 = [1011]$.

Das Papier enthält einen Algorithmus zur Berechnung des Restpolynoms auf Seite 16 in Algorithmus 3. Ich habe jedoch Probleme, den Reduktionsalgorithmus auf den Seiten 16-17 (Algorithmus 4) zu verstehen. Im Wesentlichen denke ich, dass wir Algorithmus 4 für größere Felder benötigen, wenn unsere oder Teilergebnisse nicht mehr auf 128 Bit passen. Sie geben ein Beispiel für die Multiplikation zweier Polynome in$\text{GF}(2^{128})$.

Woher kommen die "magischen Konstanten" 63, 62 und 57 für Rechtsverschiebungen und die "magischen Konstanten" 1, 2 und 7 für Linksverschiebungen?

Wie verallgemeinert man beispielsweise den Algorithmus für kleinere Felder? $\text{GF}(2^{32})$? Würden die entsprechenden Verschiebungswerte dann 15, 14, 9 und 1, 2, 7 sein?

Im letzten Schritt 4 fordert der Algorithmus Sie auf, "XOR" $[E_1:E_0]$, $[F_1:F_0]$, und $[G_1:G_0]$ miteinander und $[X_3:D]$".

Warum machen wir das? Soweit ich sehen kann, wird das Ergebnis dieser XOR-Operation weder irgendwo gespeichert noch irgendwo verwendet. Wird es irgendwie zum Rechnen verwendet?$[H_1 : H_0]$?

Das Galois-Feld $GF(2^{128})$hat viele verschiedene "konkrete" Darstellungen. Eine beliebte Darstellung ist die Verwendung von Polynomen in$GF(2)[x]$ (dh mit Koeffizienten in $GF(2)$) modulo ein irreduzibles Polynom vom Grad $128$, sagen $x^{128}+x^7+x^2+x^1+x^0$. Die magischen Konstanten$7,2,1,0$kommen von diesem bestimmten irreduziblen Polynom. Du siehst nicht$0$ da besteht keine Notwendigkeit, um zu verschieben $0$. Ebenso die magischen Konstanten$57,62,63,64$ sind die Ergänzungen der obigen Konstanten in Bezug auf $64$. Auch hier müssen Sie nicht vorbeischalten$64$ da sind die Register $64$Bits breit. Wenn wir ein anderes irreduzibles Polynom verwendet hätten, wären die Konstanten anders gewesen.

In Bezug auf Schritt 4, $[H_1:H_0]$ Ergebnisse von XORing $[E_1:E_0],[F_1:F_0],[G_1:G_0],[X_3:D]$. Dies implementiert den Betrieb von MODing by$x^{128} + x^7 + x^2 + x^1 + x^0$. Die Idee ist, dass Modulo dieses Polynom,$x^{128} = x^7+x^2+x^1+^0$;; Außerdem ist hier XOR. Die verschiedenen Summanden entsprechen diesen verschiedenen Monomen - sehen Sie, ob Sie die Entsprechung finden können.

Der Vollständigkeit halber werde ich Yuvals Antwort anhand eines Beispiels für die Multiplikation zweier Polynome etwas genauer erläutern $A$ und $B$ im $\text{GF}(2^{16})$. Lassen

$$A = [0001|1100|1110] = x^8 + x^7 + x^6 + x^3 + x^2 + x,$$ und $$B = [0100|0101|0111] = x^{10} + x^6 + x^4 + x^2 + x + 1.$$ Die Multiplikation von $A$ und $B$ Über $\text{GF}(2)$ ist dann $$C = [0000|0000|0000|0111 | 0101|0010|0000|1010].$$

Wir berechnen dann für $\text{GF}(2^{16})$ das Polynom

$$q^+ = x^{32}+x^{21}+x^{19}+x^{18}+x^{16}+x^{10}+x^6+x^4+1.$$ Wir wollen uns jetzt vermehren $q^+$ mit den hohen Bits von $C$und behalten Sie die 32 höchsten Bits dieser Berechnung für die spätere Verarbeitung. Zu diesem Zweck verwenden wir Algorithmus 4 (Schritt 1-2). Bezeichnen wir$C$ durch $[X_3:X_2:X_1:X_0]$, wo jeder $X_i$ist 8 Bit lang. Wir verschieben uns dann nach rechts$X_3$ mit 28, 26, 22, 16, 14, 13 und schließlich mit 11. Wir haben also insgesamt 7 "temporäre Variablen" und XOR sie mit $X_2$. Das führt zu$111_2$, was wir wollten.

Beachten Sie für den unteren Teil des Produkts des nächsten Schritts, dass wir die Linksverschiebungen von erhalten $g^*$, definiert auf Seite 16.