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

7

Ich lese dieses Intel-Whitepaper zur Multiplikation ohne Übertrag . Es beschreibt die Multiplikation von Polynomen inGF(2n). Auf hoher Ebene wird dies in zwei Schritten durchgeführt: (1) Multiplikation von Polynomen überGF(2)und (2) Reduzieren des Ergebnismoduls zu einem irreduziblen Polynom. Wir verwenden die "Standard" -Bitstring-Darstellung von Polynomen, d. H.x3+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 inGF(2128).

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? GF(232)? Würden die entsprechenden Verschiebungswerte dann 15, 14, 9 und 1, 2, 7 sein?

Im letzten Schritt 4 fordert der Algorithmus Sie auf, "XOR" [E1:E0], [F1:F0], und [G1:G0] miteinander und [X3: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?[H1:H0]?

Gideon
quelle

Antworten:

6

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

In Bezug auf Schritt 4, [H1:H0] Ergebnisse von XORing [E1:E0],[F1:F0],[G1:G0],[X3:D]. Dies implementiert den Betrieb von MODing byx128+x7+x2+x1+x0. Die Idee ist, dass Modulo dieses Polynom,x128=x7+x2+x1+0;; Außerdem ist hier XOR. Die verschiedenen Summanden entsprechen diesen verschiedenen Monomen - sehen Sie, ob Sie die Entsprechung finden können.

Yuval Filmus
quelle
4

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 GF(216). Lassen

A=[0001|1100|1110]=x8+x7+x6+x3+x2+x,
und
B=[0100|0101|0111]=x10+x6+x4+x2+x+1.
Die Multiplikation von A und B Über GF(2) ist dann
C=[0000|0000|0000|0111|0101|0010|0000|1010].

Wir berechnen dann für GF(216) das Polynom

q+=x32+x21+x19+x18+x16+x10+x6+x4+1.
Wir wollen uns jetzt vermehren q+ mit den hohen Bits von Cund 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 wirC durch [X3:X2:X1:X0], wo jeder Xiist 8 Bit lang. Wir verschieben uns dann nach rechtsX3 mit 28, 26, 22, 16, 14, 13 und schließlich mit 11. Wir haben also insgesamt 7 "temporäre Variablen" und XOR sie mit X2. Das führt zu1112, 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.

Gideon
quelle