200 桁の自然数の“特殊数体ふるい法”による素因数分解

立教大学 木田祐司

対象となる数=200 桁の合成数

\frac{711^{71} + 1}{711 + 1}

= 42683660622690468069969404132264738688334008350227

15027236476313440948135221266063879588098199043461 97764707626911448677575608502256303703751299411761 17095799782969282125358987110280652986724964712351

この数は“円分数の素因数分解プロジェクト”のリストに載っているもので 2000/4/16 の時点では合成数であることは分かっているもののその約数はひとつも見つかっていないものであった。

これを Special Number Field Sieve Method （特殊数体ふるい法）で分解しようというのが今回の計画である。

1 数体ふるい法の手順

1.1 多項式の選択

n = f(M) となる f(x) をとる。基準はふるいのデータが集まりやすいこと。

1.2 ふるいの実行

a, b で a + bM も a + bθ もあらかじめ決めた素数と素イデアルの集合（factor base）で分解されるものをたくさん見つける。

1.3 平方数になる組み合わせを見つける

得られた a, b の組み合わせで a + bM の積は Q での平方数であり、 a + bθ の積は Q(θ) の平方数であるものを見つける。

1.4 平方根を計算する

a + bM の積の平方根は簡単に見つかるが a + bθ の積の平方根の計算はなかなか難しい。

1.5 約数を計算する

a + bM の積が x^{2} で a + bθ の積が y(θ)^{2} ならば

x^{2} ≡ y(M)^{2} mod n

なので GCD(x − y(M), n) で n の約数が求まる。

2 多項式の選択

n = \frac{711^{71} + 1}{711 + 1}

をある多項式 f(x) とある整数 M （とおまけの小さな整数 k）で

k · n = f(M)

と表したい。

2.1 type 1

2.1.1

\frac{x^{71} + 1}{x + 1} = x^{70} − x^{69} + ⋯ − x + 1 = f(x) とおく

を利用すると

n = f(M), M = 711

2.1.2

η = ζ_{142} + ζ_{142}^{−1} の最小多項式を作ると

g(x) = x^{35} − x^{34} − 34x^{33} + 33x^{32} + 528x^{31} − 496x^{30} − 4960x^{29} + 4495x^{28} + 31465x^{27} − 27405x^{26} − 142506x^{25} + 118755x^{24} + 475020x^{23} − 376740x^{22} − 1184040x^{21} + 888030x^{20} + 2220075x^{19} − 1562275x^{18} − 3124550x^{17} + 2042975x^{16} + 3268760x^{15} − 1961256x^{14} − 2496144x^{13} + 1352078x^{12} + 1352078x^{11} − 646646x^{10} − 497420x^{9} + 203490x^{8} + 116280x^{7} − 38760x^{6} − 15504x^{5} + 3876x^{4} + 969x^{3} − 153x^{2} − 18x + 1

を利用すると

n = g(M/711)711^{35}, M = 711^{2} + 1

2.1.3

次数をもっと下げる。たとえば Gauss 和に関連して

η = ∑_{(a/142)=1} ζ_{142}^{a}

の最小多項式は x^{2} − x + 18 であるが M = ∑_{(a/142)=1} 711^{a} は a が最大 70 になって損である。途中の次数でもこういう問題があって使えない。

2.2 type 2

712 · n = M^{71} + 1, M = 711

2.3 type 3

a^{71} + 1 = a · a^{70} + 1

を利用すると d | 70 に対して

712 · n = 711 · M^{d} + 1, M = 711^{70/d}

for d = 70, 35, 14, 10, 7, 5, 2

2.4 type 4

a(a^{71} + 1) = a^{72} + a

を利用すると d | 72 に対して

712 · 711 · n = M^{d} + 711, M = 711^{72/d}

for d = 72, 36, 24, 18, 12, 9, 8, 6, 4, 3, 2

2.5 type 5

元の形を無視して一般の 200 桁の数と考えると (一般数体ふるい法)

7 次式を用いることにすると

M^{7} < n < M^{8}

となる M を決めて n を M 進数展開する。たとえば

M = 9804184077948685907918848

とすると

f(x) = 4902092038974342824324648x^{7} + 2783835715163198326824466x^{6} − 170356985245574264284556x^{5} − 1197776215499638134929336x^{4} + 3631374707468440052501637x^{3} − 587014204458011428014602x^{2} − 860454197947756556558228x + 448710306279788490342303

によって

n = f(M)

2.6 smoothness を比較する

原則 a + bM と Norm(a + bθ) の大きさが小さいほど良い。

有理側

a + bM おおよそ M = n^{1/d} であるから次数 d が大きいほど M は小さい。

代数側

f(x) = c_{d}x^{d} + c_{d−1}x^{d−1} + ⋯ + c_{1}x + c_{0}

が既約のときこの根を θ とすると

c_{d}Norm(a+bθ) = c_{d}a^{d}+c_{d−1}a^{d−1}(−b)+⋯+c_{1}a(−b)^{d−1}+c_{0}(−b)^{d}

である。次数 d が大きいほどノルムは大きい。

ベストがどこにあるかは a, b の大きさに関係する。 a, b の大きさは n で決まる。

n = 10^{200} くらいでは a, b は ±10^{6} ∼ 10^{7} である。

このとき log(a + bM), log Norm(a + bθ) およびその和を表にする。

\begin{matrix}型 & 次数 & 有理側 & 代数側 & 合計 \\ 1 & 70 & 21.5 & 1047.7 & 1069.2 \\ 1 & 35 & 28.1 & 538.8 & 566.9 \\ 3 & 70 & 21.5 & 1054.2 & 1075.8 \\ 3 & 35 & 28.1 & 530.4 & 558.5 \\ 3 & 14 & 47.8 & 216.1 & 263.9 \\ 3 & 10 & 60.9 & 156.2 & 217.2 \\ 3 & 7 & 80.6 & 111.3 & 192.0 \\ 3 & 5 & 106.9 & 81.4 & 188.3 \\ 3 & 2 & 244.8 & 36.5 & 281.3 \\ 4 & 72 & 21.5 & 1084.2 & 1105.7 \\ 4 & 36 & 28.1 & 545.4 & 573.5 \\ 4 & 24 & 34.7 & 365.8 & 400.4 \\ 4 & 18 & 41.2 & 276.0 & 317.2 \\ 4 & 12 & 54.4 & 186.2 & 240.5 \\ 4 & 9 & 67.5 & 141.3 & 208.8 \\ 4 & 8 & 74.1 & 126.3 & 200.4 \\ 4 & 6 & 93.8 & 96.4 & 190.1 \\ 4 & 4 & 133.2 & 66.4 & 199.6 \\ 4 & 3 & 172.6 & 51.5 & 224.0 \\ 4 & 2 & 251.4 & 36.5 & 287.9 \\ 5 & 7 & 74.7 & 177.7 & 252.4 \end{matrix} ただし、 5 の 7 では a, b の範囲は 10^{7.5} それ以外は 10^{6.5}

8

3 パラメータ

• f(x) = 711x^{5} + 1

• M = 711^{14} = 8436735042656804975557684769311505497041 • 有理素数 = 1, 270, 607 個（2 · 10^{7} 以下の素数）

• 有理素数の Large Primes < 10^{9}

• 素イデアル = 1, 270, 760 個（2 · 10^{7} 以下の素数上にある一次の素イデアル）

• 素イデアルの Large Primes < 10^{9}

• 二次指標 = 16 個

• ふるいの範囲 −12 · 2^{20} < a < 12 · 2^{20}, 1 ≤ b < 20 · 2^{20}

4 factor base

4.1 有理素数

1, 270, 607 個

2, 3, 5, 7, 11, 13, 17,

⋯

19999909, 19999927, 19999963, 19999981, 19999999

4.2 一次の素イデアル

1, 270, 760 個

711θ^{5} + 1 = 0

となる θ によって

(2, θ − 1), (5, θ − 4), (7, θ − 3), (13, θ − 4), (17, θ − 10), ⋯ (19999981, θ − 5846257), (19999981, θ − 7167641), (19999981, θ − 9848594), (19999981, θ − 17477842), (19999981, θ − 19659609), (19999999, θ − 8374175)

5 分解の例

a = 2826561, b = 5000036 のとき

5.1 有理素数への分解

a + bM = 42183978935745560522767543923209222699405720037 = 3 ∗ 9661 ∗ 11831 ∗ 36653 ∗ 39581 ∗ 62047 ∗ 72383 ∗ 409529

∗ 1498411 ∗ 30769007

最後の素数は factor base からは外れている（Large Prime）。

5.2 素イデアルへの分解

\begin{matrix}Norm(a + bθ)c_{d} = 125155614566294603198234274225011335 \\ = 5 ∗ 7 ∗ 461 ∗ 24781 ∗ 65963 ∗ 14506229 ∗ 15148657 ∗ 21594019 \end{matrix}

より

(a + bθ) = (5, θ − 4) ∗ (7, θ − 3) ∗ (461, θ − 148) ∗ (24781, θ − 14295)

∗ (65963, θ − 36311) ∗ (14506229, θ − 902086)

∗ (15148657, θ − 10406352) ∗ (21594019, θ − 824397)

最後の素イデアルは factor base からは外れている（Large Prime ）。

b を固定して a を −12 · 2^{20} から 12 · 2^{20} まで動かす。たとえば次のような有効なデータが得られる。

  a        b  有理 LP1,2  代数 LP1,2
-9605966 5000031 179568947 537355927         1  36927481
 671009 5000031  30188911  47420081         1         1
4116367 5000031         1 549595127  20412481 110098277
-11230839 5000032 102484367 568527233         1 104528821
-8464945 5000032 129518309 941059061         1  51214231
-10811253 5000033         1 103844821         1  89577821
1478951 5000033         1         1  24883757 285872449
1806958 5000033  53346317  76818011         1 353498623
1603993 5000034  23446363 380368507         1 182247187
1838081 5000034         1         1         1  50642377
-4154813 5000035  91762421  97563083         1         1
-432827 5000035         1 155327609         1  73342163
 990897 5000035 358755563 537369683         1  38834291
1053896 5000035 125185631 248886481         1  46439317
1708817 5000035  26749949  32448629         1 703787297
-10681755 5000036         1         1 101591561 402056819
-952613 5000036         1 767225939  21447929 153358831
2826561 5000036         1  30769007         1  21594019
10845275 5000036         1 542097503  27615641 846407651
-2718110 5000037 182786663 454826689         1 231272039
-589520 5000037         1 832500587         1 306731189
4685823 5000038 112926217 749860493         1 791625521
7445871 5000038  81150781 191083003         1 539984603

6 実行の経過と実行時間

6.1 ふるい

• CPU: PentiumII,III 450-933MHz 他

• RAM: 128MB 程度のパソコン約 20 台による分散処理を行った。すべてが連続運転をしたわけではない。

2000/4/12 開始、 2000/12/3 終了。

1 台 (Pentium3-133*6=800MHz) ならば

60,000 時間=2,500 日かかったと推定される。

この処理はメモリアクセスが頻繁に起こるのでベースクロックが重要である。同じ 800MHz でも 100*8 ではかなり遅くなる。一方 133*6 と 133*7 はほとんど変わらない。

(worse) Athlon → Pentium3 → Pentium4 (better) プログラム

• 木田版 SNFS on Windows

• 苫米地版 SNFS on Linux and Windows

• 鳥居版 SNFS on Windows and Linux 集まったデータ

FreeRelations =  63, 548
FF = 511, 250
P − F  = 2, 981, 537
F − P  = 1, 882, 722
P − P  = 10, 295, 584
PP − F  = 5, 945, 698
F − PP  = 2, 093, 455
PP − P  = 16, 554, 039
P − PP  = 10, 057, 344
P − F 以下合計 = 49, 810, 379

P − F, F − P, P − P, PP − F, F − PP, PP − P, P − PP は組み合わせて Large Primes 部分を消さねばならない。これらを結合して新しい FF 型データを作り、次を得た。

\begin{matrix}2 個の組み合せ & 268, 536 \\ 3 個の組み合せ & 217, 765 \\ 4 個の組み合せ & 189, 579 \\ 5 個の組み合せ & 174, 729 \\ 6 個の組み合せ & 163, 484 \\ 7 個の組み合せ & 156, 086 \\ 8 個の組み合せ & 147, 793 \\ 9 個の組み合せ & 139, 840 \\ 10 個の組み合せ & 132, 612 \\ 11 個の組み合せ & 124, 690 \\ 12 個の組み合せ & 116, 999 \\ 13 個の組み合せ & 110, 084 \\ 14 個の組み合せ & 102, 249 \\ 合計 & 2, 044, 446 \end{matrix}

以上から FF 型データが 63, 548 + 511, 250 + 2, 044, 446 = 2, 619, 244 個見つかった。これは必要な個数である 2, 541, 367 を超えているのでデータの収集は完了した。

6.2 連立方程式を解く

2, 541, 367 変数の F_{2} 上の連立方程式を解く。行列のデータ

• 行数=列数= 2, 541, 367

• 全非ゼロ要素数 = 202, 483, 912

• 1 行の平均非ゼロ要素数 = 79.68 が Block Lanczos 法により処理され非自明な線形関係が 25 個得られた。 Lanczos 法は大規模疎行列の解法で使われる反復法の一種。消去法より適している。

• CPU: PenitiumIII-933MHz

• RAM: 768MB(650MB 必須)

• HDD: 20GB が 1 台で 430 時間かかった。

2001/2/4 開始、 2001/2/22 終了。プログラムは C+inlineAssembler で書かれ Visual C 6.0 で

コンパイルされ Windows2000 上で実行された。 (worse) Athlon → Pentium3 → Pentium4 (better)

6.3 平方根を求める

得られた関係式が生成する平方数の平方根を求める。

∏_{i}(a_{i} + b_{i}θ) = y(θ)^{2}

となる y(θ) を求める。

ここで積の個数は 1, 264, 448 であった（これは解によって異なる）。

実際にはこの巨大な数を計算する必要はなく

y(M) mod n

を計算すれば十分である。このとき 32bit の素数を 24, 552 個使った中国の剰余定理を用いる。

１個の平方根の計算にはおよそ 120 時間かかる。これはかなり遅い。改良の余地が十分ある。

2001/3/5 開始、 2001/3/16 終了

7 結論

C200 = P81 ∗ P119 P81 = 98455676967830187583329074548959275081922866376894 1335929333073587404947243303679 であった。

8 実行者

ふるいの部分は複数の人員で範囲を分担して行った。 team-mp2000

• 木田祐司

• 伊豆哲也

• 鵜飼昌樹

• 苫米地聰

• 鳥居泰伸