Wie könnte man die Multiplikation in endlichen Körpern implementieren?

Question

Wenn F: = GF (p ^ n) das endliche Feld mit p ^ n Elementen, wobei p eine Primzahl ist und natürliche Zahl na, gibt es einen effizienten Algorithmus zur Arbeit aus dem Produkt von zwei Elementen in F?

Hier sind meine Gedanken so weit:

Ich weiß, dass die Standard-Konstruktion von F ist ein irreduzibles Polynom f vom Grad n in GF (p) zu nehmen und dann Ansichtselemente von F als Polynome in dem Quotienten GF (p) [X] / (f) und ich habe das Gefühl, dass dies wahrscheinlich schon der richtige Ansatz, da Polynom Multiplikation und Addition sollte einfach zu implementieren sein, aber ich kann nicht irgendwie zu sehen, wie dies tatsächlich geschehen. Zum Beispiel: Wie würde man eine geeignete f wählen, und wie kann ich die Äquivalenzklasse eines beliebigen Polynom bekommen?

Answer 1

Zuerst ein irreduzibles Polynom vom Grad n über GF [p] wählen. Nur zufällig diejenigen erzeugen, eine zufällige Polynom irreduziblen mit einer Wahrscheinlichkeit von ~ 1 / n .

Ihre zufällige Polynome Um zu testen, werden Sie einige Code-Faktor Polynome über GF müssen [p] finden Sie unter wikipedia für einige Algorithmen.

Dann Ihre Elemente in GF [p ^ n] sind nur n-Grad Polynome über GF [p]. Genau das tun, normale Polynomarithmetik und stellen Sie sicher, dass der Rest Modulo Ihr irreduzibles Polynom zu berechnen.

Es ist ziemlich einfach, um Code auf einfache Versionen dieser Regelung. Sie können in beliebig kompliziert werden, wie Sie implementieren, sagen, die Modulo-Operation. Siehe modulare Potenzierung , Montgomery Multiplikation und FFT-Multiplikation verwendet wird.

Answer 2

Ob es ein effizienter Algorithmus zu multiplizieren Elementen in GF (p ^ n) hängt davon ab, wie Sie die Elemente von GF vertreten (p ^ n).

Wie Sie sagen, ist eine Möglichkeit, in der Tat zur Arbeit in GF (p) (X) / (f). Addition und Multiplikation ist relativ einfach hier. Jedoch ist eine geeignete irreduzibles Polynom f Bestimmung nicht einfach - soweit ich weiß, dass es für die Berechnung eines geeigneten f kein effizienter Algorithmus ist.

Eine andere Möglichkeit ist zu verwenden, was genannt werden Zech Logarithmen . Magma Anwendungen vorausberechnet Tabellen von ihnen für mit kleinen endlichen Körpern zu arbeiten. Es ist möglich, dass GAP tut Auch obwohl seine Dokumentation ist weniger klar.

mit mathematischen Strukturen Computing ist oft sehr schwierig. Sie sind sicherlich nicht alles klar, hier fehlt.

Answer 3

Es hängt von Ihren Bedürfnissen und auf dem Feld.

Wenn Sie multiplizieren Sie einen Generator von F wählen müssen ^x . Wenn Sie hinzufügen, müssen Sie die Tatsache nutzen, dass F ein Vektorraum über einige kleinere F _{p ^m} . In der Praxis, was Sie viel Zeit tun, ist etwas gemischten Ansatz. Z.B. wenn Sie über F arbeiten ₂₅₆ , nehmen Sie einen Generator X von F ₂₅₆ ^x , und G sein, es ist Minimalpolynoms über F ₁₆ . Sie haben jetzt

(sum _{i kleiner als 16} a _i X ⁱ ) (sum _{j kleiner als 16} b < sub> j X ^j ) = sum_k sum _{i + j = k} a _i b _j X ^{i + j}

Alles, was Sie tun müssen, um die Multiplikation effizienter zu machen, speichern Sie ist eine multipication Tabelle von F ₁₆ und (unter Verwendung von G) Konstrukt X ^ m in Form von niedrigeren Potenzen von X und Elementen in F < sub> 16

Finanly, in dem seltenen Fall, dass p ⁿ = 2 ^{2 n} , erhalten Sie Conways Bereich nimbers (Blick in Conways „zu gewinnen Wege“oder 4A Abschnitt 7.1.3) Volumen, in Knuth, für die es sehr effiziente Algorithmen.

Answer 4

Galois-Feld-Arithmetik-Bibliothek (C ++, mod 2, nicht schauen, wie es unterstützt andere Primelemente)

Linbox (C ++)

MPFQ (C ++)

Ich habe keine persönliche Erfahrung w / diese aber (habe meine eigenen primitiven C ++ Klassen für Galois Felder Grad 31 oder weniger, nichts zu exotisch oder wert Kopieren gemacht). Wie einer der Kommentatoren erwähnt, können Sie überprüfen mathoverflow.net - fragen Sie einfach gut und stellen Sie sicher, Sie haben Ihre Hausaufgaben gemacht zuerst. Jemand dort sollte wissen, welche Arten von mathematischer Software zur Manipulation von endlichen Körpern geeignet sind, und es ist nahe genug, um mathoverflow der Bereich von Interesse, dass eine gut angegeben Frage soll nicht geschlossen erhalten.