例えば、

    2x2 - 5x + 2
 

を因数分解するとき、まず2次と0次の係数が1と2に分解できるから、 って考えますよね。
実は、0次の係数は

  f(0) = g(0)h(0)
 

だから、

  g(0) = (f(0)の約数)
 

の行でこれを使っています。
けれど、最高次（上の例では2次）の係数は使っていません。 これを最後の行に使いましょう。たいていの場合、約数が少なくなります。 それと、後で述べるメリットが出てきます。 因数分解(4)の表記を使って、

    b0 +    (-m)b1 +    (-m)2b2 + ... +    (-m)nbn = c0
    b0 +   (1-m)b1 +   (1-m)2b2 + ... +   (1-m)nbn = c1
                            ...
    b0 + (n-1-m)b1 + (n-1-m)2b2 + ... + (n-1-m)nbn = cn-1
                                                bn = cn
 

要するに f(x_i) のうちの一つを最高次にしてます。 これを強いて言うと、f(∞) に置き換えた感じです。これが次のプログラムです。

    factorize1d.cpp
 

これで、

    1 + 3x + x12
 

を因数分解したところ、0.97秒と5倍速くなりました。

    1 + 3x + x14
 

では、4.8秒かかりました。

最後の因数分解は4.8秒かかっていますが、 これにかかってる時間の大半は連立方程式の解が整数かどうかのチェックです。 最後の7次で因数分解しようとするところは、 32768通りの連立方程式に対し整数かどうかチェックしています。 今まではこの場合の数を減らしてきたのですが、 これからはこのうちの1回1回の時間を減らしていきます。 それにしてもどうしてこんなに時間がかかるのかという感じですが。

さて、最後の行は、

    bn = cn
 

だから、b_n が整数なら c_n も整数になり、 チェックが省けます。
そして最初の行もチェックが省けます。

    b0 = cm
 

f(0) に対応する部分が b₀ を求める最初の行になります。

    factorize1e.cpp
 

このプログラムで、

    1 + 3x + x14
 

を因数分解したところ、1.46秒と3.3倍速くなりました。

    1 + 3x + x15
 

では、203秒もかかりました。厳しいですね。

こんなに時間がかかるのは小数計算のせいでしょうか。
n-1個の整数チェックの計算のうち最初の一つだけ整数計算に置き換えてみましょう。 最後から2番目の行は次のようになります。

    bn-1 = ((-1)n-1c0 + (-1)n-2n-1C1c1 + (-1)n-3n-1C2c2 + ... + cn-1)/(n-1)! + d
 

d はある整数です。これが整数かどうかを判定するには、

    (-1)n-1c0 + (-1)n-2n-1C1c1 + (-1)n-3n-1C2c2 + ... + cn-1
 

が (n-1)! で割り切れるかみればよいです。
単純に考えると、このチェックをクリアする確率は 1/(n-1)! なので、 上の2つの例の n=7 なら非常に小さいですし、この行が最も小さくなります。 だから、この行を最初にチェックするようにしましょう （実は前のプログラムからそうしています）。

    factorize1f.cpp
 

こうすると、

    1 + 3x + x15
 

の因数分解が1.87秒！
100倍速い。こんなに違うとは、ショック。