６．複数多項式二次ふるい法
（MPQS : Multiple Polynomial Quadratic Sieve Method）

このアルゴリズムも x² - ｙ²≡0 (mod n) を利用する。
まず、Fermat の方法 x² - ｙ² = (x+y)(x-y) のときに使った、

x = int(sqrt(n)) + 1

から始める。

x²≡ｒ(mod n)

において、r が２乗数であれば話は終わりだが、なかなかそうはなってくれないので、
いろんな x について r を求めて、r の積が２乗数になるようにする。

12345679 を例にとって考えてみよう。x = isqrt(12345679) + 1 = 3514 から始める。

3514² - 12345679 = 2517 = 3×839
3515² - 12345679 = 9546 = 2×3×37×43
3516² - 12345679 = 16577 = 11×11×137
3517² - 12345679 = 23610 = 2×3×5×787
3518² - 12345679 = 30645 = 3×3×3×5×227
　……

３番目、５番目等は、なかなかいい線に行っている。
このようなのを、もっと多数求める。

……などとやっていたら、求めるものがいつ得られるのかわからない。
そこで方針を変える。

いろいろ計算して、使えそうなものを組み合わせる

のではなく、

最初から右辺の素数を固定しておき、
素因数分解結果がそれ以下の素数から構成されるもののみを集める

とする。この素因数分解はいちいち完全にやる必要はなく、必要としている素数の組、

p₁, p₂, …… , p_k

で順に割っていき、割り切れなかったものを除去していけばよい。
このようにして得られた x と r の組から、２乗になるものを構成するには、

各素数のべき数の和が偶数となるような一次結合

を求めればよい。これは、上記 k 個の変数からなる連立方程式を解く問題に帰着される。
この方法を、複数多項式二次ふるい法（MPQS : Multiple Polynomial Quadratic Sieve Method） と呼ぶ。

このアルゴリズムは、

• x, r を求める部分は、お互いに何の関連もないので、複数の計算機で同時に実行が可能。
  最後の連立方程式を解く部分のみ、１台の計算機上で行えばよい
• 時間さえかければ、必ず素因数が得られる

というメリットがある。
実際に、Silverman は、24台の Sun3 を結合して、90桁前後の合成数を数多く素因数分解している。

ここでは、コーディング例は示さない。
詳細は、

木田祐司、牧野潔夫「UBASICによるコンピュータ整数論」(株)日本評論社（1994）

参照のこと。