f を p で割れば、別の因子として q ( x ) := x 3 − x + 2 {\textstyle q(x):=x^{3}-x+2} を得るから、因数分解 f = pq を得る。さてさらに再帰的に有理根テストを施して p, q をそれぞれ分解しようと試みれば、これらが ? 上既約であることがわかるから、これで f の既約因子分解 f ( x ) = p ( x ) q ( x ) = ( x 2 + x + 1 ) ( x 3 − x + 2 ) {\displaystyle f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2)} を得た[3]。
現代的手法
有限体上の因数分解詳細は「有限体上の多項式の因数分解（英語版）」、「バーリカンプのアルゴリズム（英語版）」、および「カントール–ツァッセンハウスのアルゴリズム（英語版）」を参照ハンス・ユリウス・ツァッセンハウス
整係数一変数多項式の因数分解

上で見たことを踏まえれば、f(x) が整係数の一変数多項式のときには、一般性を失うことなくそれが原始的かつ無平方と仮定してよい。すると初めに考えるべきは f の任意の因子 g のすべての係数の絶対値を抑える上界 B を計算することである。そうして m を 2B より大きな整数として、g(x) が m を法として求まったならば、その法 m に関して分かっている g の情報から g が復元できる。

その方法を述べるハンス・ユリウス・ツァッセンハウス（ドイツ語版）のアルゴリズムは以下のようなものである:
まず素数 p を f(x) mod p がやはり無平方かつ次数を落とさないように選んで、f(x) mod p を因数分解する。これにより、整係数多項式 f1, …, fr でそれらの積が p を法として f に等しいものが得られる。

次に、ヘンゼル持ち上げを適用して、fi たちがそれらの積がこんどは pa を法として f と一致するようにできる（ただし、a は pa が 2B よりも大きくなるように選ぶものとする）。

この時点で法 pa に関して f(x) は（単数を掛ける違いを除いて）2r 個の因子を持つ— {f1, …, fr} の任意の部分集合の各々に対して、その元の総積が f(x) mod pa の因子を与える—が、法 pa に関する因子が「真の因子」（すなわち、?[x] における f(x) の因子）に対応するとは限らないことに注意する。


法 pa に関する各因子に対してそれが真の因子に対応するものかどうかをテストして、対応するものと分かれば（pa が 2B より大きいという仮定のもと）真の因子を計算することになる。

この方法では、高々 2r 通りをチェックすれば真の既約因子をすべて見つけることができる（各因子の補因子—掛けて f(x) になるもう一方の因子—についてのチェックは飛ばせるから、実際には 2r−1 通りでよい）。f(x) が可約のときは、既に真の因子であるとわかっている fi についてはチェックを飛ばせるので、調べるべき場合の数はさらに減らすことができる。

ツァッセンハウスのアルゴリズムは各場合のチェックについては手早くできるが、その場合の数が最悪の場合では指数函数的に大きくなってしまう。

有理係数多項式の因数分解を多項式時間で計算できる最初のアルゴリズムは Lenstra, Lenstra & Lovasz (1982) が格子基底縮小アルゴリズム（英語版）（"LLLアルゴリズム"）の応用として与えた。簡易版のLLL因数分解アルゴリズムは以下のようなものである: 多項式 f の複素（あるいは p-進）根 α を高精度で計算し、LLL格子基底縮小アルゴリズムを用いて 1, α, α2, … の満たす整係数線型関係式（英語版）（つまり α の満たす整係数多項式関係式）を近似的に求めると、それが（近似でない）真の線型関係式の、したがって f の多項式因子の候補になる。

適切に近似の精度の限界を決めることで、このアルゴリズムが多項式因子か既約性証明の何れかを与えるものであることを保証することができる。この方法は多項式時間であるけれども、格子は高次元のもので、成分数は膨大になり、計算に時間がとられることを考えれば、実用に供されるものではない。

さて、ツァッセンハウスのアルゴリズムの計算量が指数時間となるのは、（f1, …, fr の中から目的に合う部分集合を選び出すという）組合せ問題から来るものであった。ツァッセンハウスと同じやり方ながら組合せ爆発の問題を回避する芸術的因数分解の実装の状態は、組合せ問題をLLLで解決できる格子問題に翻訳する点にある[4]。このやり方の場合、LLL は因数の係数を計算するのではなくて、{0, 1} に r 個の成分をとるベクトル（真の既約因子を与える f1, …, fr の部分集合をエンコードするもの）の計算に用いる。
代数体係数の場合: Trager の方法

体 K が代数体（? の有限次拡大体）であるときの多項式 p(x) ∈ K[x] も因数分解することができる。無平方分解して、多項式は無平方であると仮定してよい。? 上の線型環として L ? K[x]/(p(x)) と陽に書いて、無作為に α ∈ L をとれば、原始元定理により、高確率で α は L を ? 上生成する。生成することが確認できたならば、α の ? 上の最小多項式 q(y) ∈ ?[y] を計算して、それを ?[y] 上で q ( y ) = ∏ i = 1 n q i ( y ) {\displaystyle q(y)=\prod _{i=1}^{n}q_{i}(y)} と因数分解することで、 L = Q [ α ] = Q [ y ] / ( q ( y ) ) = ∏ i = 1 n Q [ y ] / ( q i ( y ) ) {\displaystyle L=\mathbb {Q} [\alpha ]=\mathbb {Q} [y]/(q(y))=\prod _{i=1}^{n}\mathbb {Q} [y]/(q_{i}(y))} と決定できて（p は無平方であるから、L が被約環となることに注意）、α は右辺の元 (y, …, y)（全ての成分が y）に対応する。これが体の直積としての L の唯一の分解であることに注意する。したがってこの分解は ∏ i = 1 m K [ x ] / ( p i ( x ) ) {\displaystyle \prod _{i=1}^{m}K[x]/(p_{i}(x))} と同じものである（ここに p = ∏m