Eine Polynomrestfolge entsteht durch wiederholte Division mit Rest zweier Polynome. Falls es sich um Polynome mit Koeffizienten aus einem Körper handelt, liefert zum Beispiel der euklidische Algorithmus eine solche Folge. Im allgemeineren Fall von Polynomen mit Koeffizienten aus einem faktoriellen Ring muss jedoch der Dividend mit einer geeigneten Konstante multipliziert werden, um die Division mit Rest durchführen zu können (Pseudodivision).

Polynomrestfolgen werden in der Computeralgebra zur Berechnung eines größten gemeinsamen Teilers zweier Polynome eingesetzt. Das dort auftretende Problem, dass die Koeffizienten der Polynome exponentiell anwachsen, wird durch das Subresultantenverfahren gelöst.

Für zwei Polynome ${\displaystyle f,g\in R[x]}$, ${\displaystyle g\not =0}$, mit Koeffizienten aus einem faktoriellen Ring ${\displaystyle R}$ ist gibt es stets Polynome ${\displaystyle q,r\in R[x]}$, so dass

${\displaystyle \mathrm {lc} (g)^{\mathrm {deg} (f)-\mathrm {deg} (g)+1}f\,=\,qg+br}$ und ${\displaystyle \mathrm {deg} (r)\,<\,\mathrm {deg} (g)}$

gilt; dabei bezeichnet ${\displaystyle \mathrm {lc} (g)}$ den Leitkoeffizienten von ${\displaystyle g}$. Dabei wird ${\displaystyle r}$ als Pseudorest und ${\displaystyle q}$ als Pseudoquotient bezeichnet (Pseudodivision, s. Donald Knuth, Abschnitt 4.6.1), und wir schreiben

${\displaystyle r=\mathrm {prem} (f,g)}$.

Polynome ${\displaystyle f}$ und ${\displaystyle g}$ heißen ähnlich, in Zeichen ${\displaystyle f\sim g}$, falls es ${\displaystyle a,b\in R}$ gibt mit

${\displaystyle af=bg.}$

Eine Folge ${\displaystyle p_{0},p_{1},\ldots ,p_{n}}$ von Polynomen heißt Polynomrestfolge, falls

${\displaystyle p_{i+2}\ \sim \ \mathrm {prem} (p_{i},p_{i+1})}$

für ${\displaystyle k=0,\ldots ,n-2}$ sowie

${\displaystyle \mathrm {prem} (p_{n-1},p_{n})=0}$

gelten.

Zu Polynomen ${\displaystyle p_{0},p_{1}}$ liefert

${\displaystyle p_{k+2}:=\mathrm {prem} (p_{k},p_{k+1})}$

eine Polynomrestfolge, die Pseudo-Polynomrestfolge genannt wird. In der Praxis hat sie den Nachteil, dass die Koeffizienten der Polynome ${\displaystyle p_{k}}$ exponentiell anwachsen.

Dividiert man ein Polynom durch seinen Inhalt, so erhält man ein Polynom, dessen Koeffizienten teilerfremd sind (primitiver Anteil des Polynoms, ppart). Dies führt zur Folge

${\displaystyle p_{k+2}:=\mathrm {ppart} (\mathrm {prem} (p_{k},p_{k+1})),}$

die primitive Polynomrestfolge genannt wird. Um diese Folge zu berechnen, sind allerdings ggT-Berechnungen im Koeffizientenring ${\displaystyle R}$ erforderlich, die in der Praxis viel Rechenzeit in Anspruch nehmen.

In der Praxis wird üblicherweise die durch

${\displaystyle p_{k+2}:={\frac {\mathrm {prem} (p_{k},p_{k+1})}{g_{k}\cdot h_{k}^{\delta _{k}}}}}$

definierte Folge eingesetzt. Dabei ist

${\displaystyle \delta _{k}:=\mathrm {deg} (p_{k})-\mathrm {deg} (p_{k+1})}$

und ${\displaystyle g_{k}}$ und ${\displaystyle h_{k}}$ sind durch

${\displaystyle h_{0},g_{0}:=1}$

${\displaystyle g_{k+1}:=\mathrm {lc} (p_{k+1})}$

${\displaystyle h_{k+1}:=h_{k}^{1-\delta _{k}}g_{k+1}^{\delta _{k}}}$

definiert. Alle dabei vorkommenden Divisionen gehen auf, und die Koeffizienten der so definierten Polynome wachsen wesentlich langsamer als bei der Pseudo-Polynomrestfolge.

Das letzte Glied ${\displaystyle p_{n}}$ einer Polynomrestfolge ist ähnlich zum größten gemeinsamen Teiler der Polynome ${\displaystyle p_{0}}$ und ${\displaystyle p_{1}}$:

${\displaystyle p_{n}\ \sim \ \mathrm {ggT} (p_{0},p_{1}).}$

Polynomrestfolgen können daher zur ggT-Berechnung in Polynomringen eingesetzt werden.

• W. S. Brown, Joseph F. Traub: On Euclid’s Algorithm and the Theory of Subresultants. In: Journal of the ACM. Band 18-4, Oktober 1971, S. 505–514. 
• Donald E. Knuth: The Art of Computer Programming. 3. Auflage. Vol. II: Seminumerical Algorithms. Addison-Wesley, 1998. 
• Rüdiger Loos: Generalized Polynomial Remainder Sequences. In: Bruno Buchberger, G. E. Collins, Rüdiger Loos (Hrsg.): Computer Algebra. Springer, 1982. 
• Attila Pethő: Algebraische Algorithmen. Hrsg.: Michael Pohst. Vieweg, 1999, ISBN 978-3-528-06598-0. 
• Michael Kaplan: Computeralgebra. Springer, 2005, ISBN 3-540-21379-1.