bigint.js v0.5 beta 26

このデモでは、p-1法で因数分解する。 現在の記録は、33桁の合成数から、 9桁の素因数 p=265371653 を取り出した。 p-1 は、104149スムースであった。 4万5千桁の LCM[1,2,3,…,10万より少し大きい数] を使って分解した。 コストは30分程度。

beta 25 からの変更点

• toFancyString()メソッドの出力形式を変更。
• [ADD] _getK( n ) は、1,2,3,...,n の最小公倍数を返す。
• 細かい変更多数。

2004-08-19

29分でR39を直接分解。 45240桁のk(104149)を使用。kの構成自体は200秒。繰り返し二乗法で25分。

Success!

R(39): 

111111111111111111111111111111111111111 = 

 3 x 37 x 53 x 79 x 265371653 x 900900900900990990990991

DEBUG: n : 111111111 1111111111 1111111111 1111111111 (39-digit)
DEBUG: divisible by [ 3 ]
DEBUG: *Cost ( erat ): 0 ms
DEBUG: n : 37037037 0370370370 3703703703 7037037037 (38-digit)
DEBUG: divisible by [ 37 ]
DEBUG: *Cost ( erat ): 0 ms
DEBUG: n : 1001001 0010010010 0100100100 1001001001 (37-digit)
DEBUG: divisible by [ 53 ]
DEBUG: *Cost ( erat ): 0 ms
DEBUG: n : 18886 8113396415 2832077360 3792471717 (35-digit)
DEBUG: divisible by [ 79 ]
DEBUG: *Cost ( erat ): 16 ms
DEBUG: n : 239 0735612612 8516861738 7389778123 (33-digit)
DEBUG: *Cost ( sprp? ): 203 ms
DEBUG: 19 : 232792560 (9-digit)
DEBUG: * Cost: 78 ms
DEBUG: 59 : 96907 1216477723 1700912800 (25-digit)
DEBUG: * Cost: 172 ms
DEBUG: 166 : 1 9180528744 5280055985 7620294954 2117157359 0933895120 1900636922 7289584000 (71-digit)
DEBUG: * Cost: 453 ms
DEBUG: 211 : 71 1689472437 4744183892 7276793711 5369682352 1476766817 6422286721 6245363778 1080292930 4135312000 (92-digit)
DEBUG: * Cost: 610 ms
DEBUG: 401 : 239268 4332820374... (176-digit)
DEBUG: * Cost: 1140 ms
DEBUG: 1069 : 2230129244 5892716621... (470-digit)
DEBUG: * Cost: 3188 ms
DEBUG: 2113 : 3192777241 8392712129... (920-digit)
DEBUG: * Cost: 6453 ms
DEBUG: * Cost: 0 ms
DEBUG: *Cost ( getPrimeTable ): 187 ms
DEBUG: *Cost ( bigResult ): 199329 ms
DEBUG: 104149 : 1484675268 8683426881... (45240-digit)
DEBUG: * Cost: 1524266 ms
DEBUG: divisible by [ 265371653 ]
DEBUG: n : 9009 0090090099 0990990991 (24-digit)
DEBUG: STOP [ 900900900900990990990991 ]
DEBUG: *Cost ( sprp? ): 110 ms
DEBUG: ** Total Cost: 1736.205 seconds

2004-08-18

更新: トリックを使わないでいいようにした。 攻撃に使うパラメータを少しチューニングし、一部のケースで高速化した。 R26を失敗させることを代償に、その他の失敗するケースで失敗判定までの待ち時間を半分程度にした。

160秒で、R37を分解。11891桁のK(27407)使用。

R(37): 

1111111111111111111111111111111111111 = 

 247629013 x 2028119 x 2212394296770203368013

DEBUG: n : 1111111 1111111111 1111111111 1111111111 (37-digit)
DEBUG: 19 : 232792560 (9-digit)
DEBUG: * Cost: 328 ms
DEBUG: 59 : 96907 1216477723 1700912800 (25-digit)
DEBUG: * Cost: 188 ms
DEBUG: 166 : 1 9180528744 5280055985 7620294954 2117157359 0933895120 1900636922 7289584000 (71-digit)
DEBUG: * Cost: 500 ms
DEBUG: 211 : 71 1689472437 4744183892 7276793711 5369682352 1476766817 6422286721 6245363778 1080292930 4135312000 (92-digit)
DEBUG: * Cost: 656 ms
DEBUG: 401 : 239268 4332820374 6728570999 1240271234 5831859265 9360638729 7182671388 8236341840 7134284845 3841244185 6513751474 6150867189 7423029055 7754962684 2547975763 5631050978 8597851479 3615648000 (176-digit)
DEBUG: * Cost: 1266 ms
DEBUG: divisible by [ 247629013 ]
DEBUG: n : 44869989 0877128808 4531157547 (28-digit)
DEBUG: 19 : 232792560 (9-digit)
DEBUG: * Cost: 187 ms
DEBUG: 59 : 96907 1216477723 1700912800 (25-digit)
DEBUG: * Cost: 125 ms
DEBUG: 166 : 1 9180528744 5280055985 7620294954 2117157359 0933895120 1900636922 7289584000 (71-digit)
DEBUG: * Cost: 313 ms
DEBUG: 211 : 71 1689472437 4744183892 7276793711 5369682352 1476766817 6422286721 6245363778 1080292930 4135312000 (92-digit)
DEBUG: * Cost: 437 ms
DEBUG: 401 : 239268 4332820374 6728570999 1240271234 5831859265 9360638729 7182671388 8236341840 7134284845 3841244185 6513751474 6150867189 7423029055 7754962684 2547975763 5631050978 8597851479 3615648000 (176-digit)
DEBUG: * Cost: 828 ms
DEBUG: 1069 : 2230129244 5892716621... (470-digit)
DEBUG: * Cost: 2282 ms
DEBUG: 2113 : 3192777241 8392712129... (920-digit)
DEBUG: * Cost: 4718 ms
DEBUG: * Cost: 0 ms
DEBUG: *Cost ( getPrimeTable ): 47 ms
DEBUG: *Cost ( bigResult ): 15703 ms
DEBUG: 27407 : 4 5411258138... (11891-digit)
DEBUG: * Cost: 132063 ms
DEBUG: divisible by [ 2028119 ]
DEBUG: n : 22 1239429677 0203368013 (22-digit)
DEBUG: SPRP(2) [ 2212394296770203368013 ]
DEBUG: ** Total Cost: 159.735 seconds

R34の因数 117957818840753430733 = 5363222357 * 21993833369 前者のp-1は202753スムース。 後者ははるかにでかい。

2004-08-17

Pollard の方法による因数分解（p-1 Factorization Method）のデモ。 手元では、1を31個並べた数を18秒で分解できた。

R(31): 1111111111111111111111111111111 = 2791 x 6943319 x 57336415063790604359

18秒は決して速くはないが、 100% JavaScript で動いているところがおもしろい。

例として、Repunit を分解する。レプユニットとは1を並べた数。例えば、

R(3): 111 = 3 x 37

R(4): 1111 = 11 x 101

R(5): 11111 = 41 x 271

概要としては、bigNumber を分解したいとして、
big1 = Bigint.powmod( 2, k, bigNumber );
を求める。ここで k は、小さい数をたくさんかけた形をしている。 具体的には、2,3,4,...,X の最小公倍数が k で、Xの初期値は 101 それでうまく行かないなら X= 211, 401, 1009, 2003, 4001 を順に試す。

big1 - 1 と bigNumber の最大公約数 D で判断する。 D = 1 なら失敗で、そうでなければ、ほとんどの場合、 D は bigNumber の約数である。

所要時間の例。R16までとR18～R25は一瞬～1秒未満。 R17は6秒だった。R26は15秒だった。環境によって変化する。

R(17): 11111111111111111 = 2071723 x 5363222357

余因数がSPRP(2)になると分解に成功と報告する。 実際にはSPRP(2)は素数とは限らないが、この範囲では擬素数は紛れ込まない。 ただし、Pollard の方法で見つかった因数それ自体が素数でないときは、本当は分解が完成していないが、 そのままとする。要するに、これは Pollard 法の骨組みのテストであり、 結果を厳密に吟味する部分は省略している。

例えばR36の分解で出る 17543877193 は素数ではない。 17543877193 の約数 52579 はR18を参照すればすぐ分かるが、ここでは分解の完成には興味ないので、行っていない。

R(36): 111111111111111111111111111111111111 = 3 x 3 x 7 x 11 x 13 x 19 x 37 x 101 x 9901 x 17543877193 x 999999000001

R41までの範囲で、 R18とR32は、このアルゴリズムでは本来うまくいかないのだが、個別に対応してある。 R34等は、このアルゴリズムでは失敗する。 レプユニットの分解という目的だけなら、R34はR17の因数を参照すれば容易に分解できるが、 ここではR34の直接分解自体を行って失敗する。 R37は本質的に失敗する。37は素数なので前の結果を参照できない。

R(37): 1111111111111111111111111111111111111 = 247629013 x 4486998908771288084531157547

4486998908771288084531157547 = 2028119 x 2212394296770203368013 は、ここで使っている範囲では分解できない。

[index]