二次ふるい法（にじふるいほう、英：Quadratic sieve、略称：QS）とは、素因数分解に関するアルゴリズムで、実用では一般数体篩法に次いで2番目に早い計算方法であるとされている 。
10進数で100桁までなら計算は最速であり、一般数体篩法よりかなり単純である。
基本となるアイデア
与えられた自然数 を因数分解するものとしよう。 は素数テストなどで素数ではないことは分かっており、またエラトステネスの篩のようなシンプルな方法では、実用的な時間内で分解できない程度には大きいものとする。
を2つの平方数の差で表す
もし、 を満たすような2つの自然数 が発見できれば、 であるから、 は因数 を持つことになる。ただし、 の組と因数 の組は1対1対応であるから、 の組を発見するにしろ、因数 の組を発見するにしろ、総当たり法(Brute-force attack)を用いるのであれば、必要な計算量は同じであり、このままではこの方法は利点は無い。
式 の見方をやや変えて、 と定義すれば、 が平方数であるか否かを比較的容易に判定できる方法があれば、 の組を総当たり法によるよりも効率的に求められる可能性が有る。また、 が平方数となる を見つけるのは運によるので、なるべく多数の について、 が平方数かを判定する必要があるだろう。
このためには、まず がなるべく小さい整数となることが好ましい。そこで を次のように組織的に変化させることにする。
まず、 となる整数 を二分法やニュートン法などで求める。 の桁数は(2進法にしろ10進法にしろ) の桁数の約半分になる。
と置いて、 が平方数であるかを判定する。ここで は、適当に決めた試行回数の上限となる非負整数であり、 は の範囲の非負整数とする。 であるから、 の上限値は 程度になる。 が平方数であるかは、その平方根を二分法やニュートン法などで求めれば分かる。 が平方数であれば、その平方根を とすれば、 というように因数が求められる。
残念ながら、この方法でストレートに因数を求めるのであれば、 の値は 程度まで大きくしなければならない。 が10進100桁程度の整数とすれば は10進50桁程度の整数とする必要があり、まだ実用的な方法とは言えない。
平方数の差が となる数の組を組織的に探す
そこで、さらに発想を少し変えて、 と という数の組があって、それぞれ という式を満たしており、 は平方数ではないが、 が平方数 となる場合を考えよう。この場合、 となる。 および と置けば、 であるから となる。
この場合、ユークリッドの互除法で と または の共通因数を計算すれば、運が良ければ の因数が求められるが、運が悪ければ が の因数となって、 と および が互いに素となり、 の因数が求められない場合もあり得る 。
この方法の優れている点は、数の組を2つではなく、もっと多数の組の場合に拡張することが容易なことである。 という 個の数の組があって、それぞれ という式を満たしており、各 は平方数ではないが、 が平方数 となるとしよう。この場合、 となる整数 が存在する。 と置けば、 であるから となる。
この場合も同じく、ユークリッドの互除法で と または の共通因数を計算すれば、運が良ければ の因数が求められるが、運が悪ければ が の因数となって、 と および が互いに素となり、 の因数が求められない場合もあり得る。
さて問題は、 が平方数となる の組をどうやって見つけるかであるが、先に示した
と置く方法で、多数の の組について、 を比較的簡単に素因数分解できれば、どのような を組み合わせて乗ずれば平方数になるかを、かなり効率よく算出できる可能性があるだろう。
そこで、比較的簡単に素因数分解できる のみを選別する、つまり を「ふるい」(sieve) にかけることを考える。このため「比較的簡単に素因数分解できる」ということをさらに厳密に定義するために、B-smooth という概念を導入する。
B-smooth と素因数ベクトル
定義 (B-smooth) を自然数とする。 の素因数が全て 以下の場合、 は B-smooth であるという。
自然数 を適当に決めて固定する。 を 以下の全ての素数の集合とし、 の元の個数を とする。 の元はエラトステネスの篩などの方法であらかじめ算出し、昇順にリスト化しておくものとする。これらの素数には昇順に番号が1から振られており、 番目の元を と表すものとする。つまり、、、、…、、… となっているものとする。
が B-smooth である場合、 は一意的に と表すことができる。ここで、 は の多重度を表す非負整数とする。これを成分とする行ベクトル を考え、 についての の素因数ベクトルと呼ぶことにする。 の場合、 は を含んでいないことを意味する。従って が 1 でなければ、各 が同時に 0 となることはない。
が B-smooth であるか否かの判定は、 の素数リストで昇順に が で何回割れるかを調べて を決定し、 と表すことができるかを実際に調べるしか方法は無い。
と が B-smooth であり、その素因数ベクトルがそれぞれ、 、 である場合、 も B-smooth であり、その素因数ベクトルは、 となる。
以下、
と置く方法で、 が B-smooth である の組のみを順に 個選別し、 の昇順で番号を に付け替えておくものとする。
素因数パリティ(偶奇性)ベクトル
の素因数ベクトルの成分が全て偶数の場合、 は平方数であることになる。素因数ベクトルの成分は非負整数であるが、 が平方数であるか否かを判定するためなら、成分が奇数か遇数かという情報があれば十分である。そこで、素因数ベクトルの各成分を2で除した余り(2を法とした剰余)を成分とするベクトルを考え、素因数パリティ(偶奇性)ベクトルと呼び、 と表すことにする。 であり、これらが取り得る値は 0 または 1 のみである。
と の積 の素因数パリティベクトルは、定義により となるが、これは に等しい。つまり、積 の素因数パリティベクトルの成分は、 と の素因数パリティベクトルの成分の、2を法とした剰余加法になる。
線形代数的に見れば、 についての 素因数パリティベクトルの全体は、有限体 上の 次元の線形空間(ベクトル空間)を成している。 は 2つの元 のみから成る体であり、その加法と乗法は 2を法とした剰余算になる。 を の元とすれば、 と のは、 と定義される。
線型独立、線型従属といった線形代数的な概念は、素因数パリティベクトルが成す線形空間でも成り立ち、 個の の元 ( を 次元ベクトルと見なして「スカラーベクトル」と呼ぶことにする) と 個の素因数パリティベクトル が、
という関係を満たすのは、 が全て 0 である場合に限られるとき、 は線型独立であると呼び、そうでない場合は線型従属であると呼ぶ。
線型従属となる 個の素因数パリティベクトルの組 を見つけることができれば、 が求めていた平方数の 1 つとなる( の内のいずれかは 0 でないから は 1 ではない)。 の値は、各 の素因数ベクトルから の素因数ベクトルを計算して、その各成分(全て偶数)を2で割れば求められる。また、 の値は、 で求められる(以上は簡単なので証明略)。
ただし、この場合も得られる関係式は と、余計な整数 が残った状態となる。ユークリッドの互除法で と または の共通因数を計算すれば、運が良ければ の因数が求められるが、運が悪ければ が の因数となって、 と および が互いに素となり、 の因数が求められない場合もあり得る。
因数が求められるか否かは多分に運によるので、なるべく多数の B-smooth となる の組を求め、さらにそれらを線型従属にするスカラーベクトル をなるべく多数見つける必要があることになる。
次元線形空間においては、一般に より多いベクトルの組は線型従属となる。従って より多い B-smooth となる の組を探せば、1 つ以上の平方数を見つけることが出来ることになる。スカラーベクトル は、具体的にはガウスの消去法(掃き出し法)によって求めることができる。
ガウスの消去法
実際の計算規模
の値は小さい方が素因数ベクトルの算出などに要する計算量が少なくて済むが、各 が B-smooth となる確率はより少なくなり、試行すべき の数が大きくなってしまう。 が10進100桁以上の場合、コンピューターの能力も勘案して、実用的には は 程度とする。 の場合 となり、これが素因数ベクトルおよび素因数パリティベクトルの次数となる。
算法(アルゴリズム) パラメータの選択 篩 有効式の選択 分解
実装 C Quadratic Sieve – C言語で書かれた二次ふるい法のパブリックドメイン実装。2022年に公開され、最大330ビットまでの数のバッチ因数分解をサポートし、JSONまたはCSV形式で出力可能。
脚注
出典