Algorithmus zur Faktorisierung von Polynomen mit ganzzahligen Koeffizienten. Der Algorithmus enthält folgende Schritte:

1. Wir wählen eine Primzahl p, die nicht die Diskriminante des Polynoms f teilt.
2. Wir faktorisieren das Polynom f über dem Primkörper 𝔽_p der Chrakteristik p. Sei k die Zahl der Faktoren.
3. Wenn k = 1 ist, ist das Polynom auch über ℤ irreduzibel und wir sind fertig.
4. Wenn k > 1 ist, werden die Faktoren auf alle möglichen Weisen in zwei nicht-leere Teilmengen aufgeteilt. Wir wählen eine Partition und multiplizieren die Faktoren so, daß f modulo p zwei nichttriviale Faktoren g₀ und h₀ mit nicht verschwindender Resultante hat: \begin{eqnarray}f\equiv {g}_{o}{h}_{0}\,\mathrm{mod}\,p\end{eqnarray} und \begin{eqnarray}{\rm{Res}}({g}_{0},{h}_{0})\rlap{/}{\equiv }0\,\mathrm{mod}\,p.\end{eqnarray}
5. Wir wenden das Henselsche Lemma an, um eine Zerlegung f ≡ gh mod pⁿ zu erhalten, pⁿ > B, die Koeffizienten von g und h werden zwischen −p^n/2 und p^n/2 gewählt. Wenn g das Polynom f über ℤ teilt, haben wir zwei nichttriviale Faktoren gefunden, auf die wir die Prozedur wieder anwenden können,
6. Wenn g das Polynom f über ℤ nicht teilt und bereits alle anderen Partitionen getestet sind, ist f irreduzibel und wir sind fertig.