Binär-XGCD für Polynome

Question

Es existiert ein binary GCD algorithm zum Finden des größten gemeinsamen Teilers einer Zahl. Im Allgemeinen kann die GCD auf XGCD erweitert werden, was dabei helfen kann, eine multiplikative Inverse in einem Feld zu finden.

Ich arbeite mit Binärzahlen, die ein Polynom darstellen. Zum Beispiel repräsentiert die Bitfolge 1101x^3 + x^2 + 1. Ich muss das modulare Inverse eines zufälligen Polynoms modulo x^p - 1 für einige große bekannte prime p berechnen. Jedoch muss ich es in konstanter Zeit machen (was bedeutet, dass die Laufzeit nicht von der Zahl abhängen sollte, die ich invertiere). Ich weiß, wie man die binäre GCD konstante Zeit macht und ich weiß, wie man die XGCD für Polynome implementiert, um multiplikative Inverse zu berechnen. Was ich nicht weiß ist, ob es ein binäres GCD-Äquivalent (mit entsprechendem XGCD) für (binäre) Polynome gibt?

Answer 1

Ja, es gibt. Die "binäre" GCD funktioniert in jedem Ring, in dem die kleinste Primzahl existiert. Für ganze Zahlen ist es 2, daher der Name binär. Für Polynome ist es x. Der Algorithmus folgt der gleichen Idee: Subtrahiere Polynome, um einen freien Term in einem höheren Grad zu eliminieren, falle die höchstmögliche Potenz von x aus und mach weiter, bis das Ergebnis der Subtraktion Null wird.