QS (Quadratic Sieve, 2次篩法)

ysd@KLab > 因数分解 > QS

前提

因数分解したい数を n と表記します。このとき n が奇数である必要があるので、もし偶数だった場合には必要な回数だけ 2 で割って n が奇数になるようにして下さい。

手順

正直、解説だけでは分かりにくいので、具体例として 1147 を因数分解します。途中使うパラメータとしてはM=6、素数は -1, 2, 3, 11, 13, 17, 19 を使うことにします。5, 7は平方剰余の関係で使っても意味がないので。

篩

xf(x)-12311131719残り
27-418 110 1 0 0 1 1
28-363 101 2 0 0 0 1
29-306 112 0 0 1 0 1
30-247 100 0 1 0 1 1
31-186 111 0 0 0 0 31
32-123 101 0 0 0 0 41
33- 58 110 0 0 0 0 29
34 9 002 0 0 0 0 1
35 78 011 0 1 0 0 1
36 149 000 0 0 0 0149
37 222 011 0 0 0 0 37
38 297 003 1 0 0 0 1
39 374 010 1 0 1 0 1

まずは大量の候補から使えるものを選びやすくするための作業です。√n-M ≤ x ≤ √n+M (Mは適当に設定する)の範囲の整数 x について

f(x)=x2-n   (x2 ≡ f(x) (mod n))

の値を小さな素数（と -1）の範囲だけでいいので素因数分解します。各素因数についての指数を記録しておきましょう。

右の表は具体例における各素数の指数を表わしています。√1147=33.8 なので x は 23～42 を探索します。「残り」の部分は用意していた部分の素数で割り切れない数です。例えば x=31 では

f(31) = -186 = (-1)1・21・31・110・130・170・190・31

ということです。

 

行列解析

篩の手順で作ったリストの中から、掛け合わせることで因数分解した部分の指数が全て偶数になる組み合わせを選び出します。

27 1101001
28 1012000
29 1120010
30 1000101
34 0020000
35 0110100
38 0031000
39 0101010

1101001 10000000
1010000 01000000
1100010 00100000
1000101 00010000
0000000 00001000
0110100 00000100
0011000 00000010
0101010 00000001

1101001 10000000
0111001 11000000
0010101 01010000
0001011 10100000
0000110 01100100
0000000 00001000
0000000 10010110
0000000 11110101

具体例（上記）では一般的なガウス消去法のアルゴリズムで作業してみます。

  1. 「残り」が 1 となる x と、その各素数の指数を取り出します。「残り」を考慮する方法もありますが、説明が面倒なので今回は省略します。
  2. 次に、指数が奇数(1)か偶数(0)かだけを 1/0 で表わし、ついでなので右に単位行列もつけます。
  3. 指数側の行列の下三角（とそれより下）が全て 0 になるようにガウス消去します。（手作業でやってるのでミスがあるかも）

上記の作業の結果残った下3行が以降の計算に使われる組合せを示してます。右の行列でビットが立っている式を掛け合わせましょう。その結果は順に

342 ≡ 32
272・302・352・382 ≡ (-1)2・22・34・112・132・192
272・282・292・302・352・392 ≡ (-1)4・24・34・114・132・172・192

因数分解

行列解析で作った組み合わせに含まれる x を全て掛け合わせたものを A、f(x)を掛け合わせたものの平方根(必ず整数になる)を B と置くと

A2≡B2 (mod n)

となっているので、GCD(A ± B, n) で素因数が出ます。ただし、A≡±B (mod n)だと自明解しか出ません。

具体例を計算してみましょう。

A=34, B=3 ⇒ GCD(34 - 3, 1147)=31 ⇒ 1147 = 31・37
A=27・30・35・38, B=2・32・11・13・19 ⇒ GCD(1070300 - 48906, 1147)=31 ⇒ 1147 = 31・37
A=27・28・29・30・35・39, B=22・32・112・13・17・19 ⇒ GCD(897787800 - 18290844, 1147)=37 ⇒ 1147 = 31・37

今回はたまたま3式とも全部非自明解が出ましたが、自明解が出る確率は50%ちょいだそうで。

ちょっと発展

素数選別

先にどの素数を使って因数分解するかを決めます。仮に f(x) が素数 p で因数分解できるとすると

x2-n≡0 (mod p)

となっています。ここで n を右辺へ移項すると見やすいのですが、n が p について平方剰余（上の式のような n と p の関係。特に x が何かということに関しては言及しない。）になっています。背理法のように考えると、n が p についての平方剰余でなければ p で f(x) は割り切れないので試すだけ無駄、ということが分かるわけです。

そこで、n が平方剰余となる素数を小さい方から順に K 個取ってきます。K は任意に決めて下さい。傾向として n が大きければ K もそこそこ大きいという感じで。その K 個の素数に -1 を付け足した（数として足し算するのではなくリストとして追加する）リストを今後「素数基底」(FB ; Factor Base)と言います。

篩

手順だけを見ると2重ループの構造は 外が x、内が FB の様な感じですが、実際には FB の要素 p で外側のループを回します。中のループは x についてなのですが p とばしの箇所に p についての指数を加えていきます。