読者です 読者をやめる 読者になる 読者になる

YAFUを使って大きな数を素因数分解してみる

「Msieveを使って大きな数を素因数分解してみる」では、Msieveを使って大きな数の素因数分解を行った。 素因数分解プログラムには、Msieveの他にYAFU(Yet Another Factorization Utility)がある。 YAFUはECMにGMP-ECM、MPQSにMsieve、GNFSにGGNFSを用い、マルチスレッドで高速に動作する。 ここでは、YAFUを使って大きな数の素因数分解を行い、一般的なPCで解くことができるbit数などを調べてみる。

環境

Windows 8.1 Pro 64 bit版、Intel Core i5-4200U (1.6GHz * 2 * 2)

>systeminfo
OS 名:                  Microsoft Windows 8.1 Pro
OS バージョン:          6.3.9600 N/A ビルド 9600
OS ビルドの種類:        Multiprocessor Free
システムの種類:         x64-based PC
プロセッサ:             1 プロセッサインストール済みです。
                        [01]: Intel64 Family 6 Model 69 Stepping 1 GenuineIntel ~1596 Mhz

YAFU(+GGNFS)のダウンロード

YAFUはWindowsまたはLinux用バイナリあるいはソースコードの形で公開されている。 Linux環境においてYAFUおよびGGNFSをソースコードからコンパイルしての利用を試みたところ、GNFSの計算時にGGNFSがクラッシュしてしまう問題が発生したため、ここではコンパイル済みWindows用バイナリを用いた方法を説明することとする。 なお、MPQSのみを行うのであれば、YAFUのLinux用バイナリも問題なく利用できる。

まず、下のサイトからコンパイル済みのYAFU(yafu-1.34.zip)をダウンロードし、展開する。

次に、下のサイトからコンパイル済みのGGNFS(ggnfs-svn413-win64-core2.zip)をダウンロードし、YAFUのディレクトリ内に展開する。

YAFUは外部プログラムとしてGGNFSを実行することでGNFSを行う。 そこで、yafu.iniでGGNFSの実行ファイルが置かれたディレクトリを次のように指定しておく。

ggnfs_dir=.\ggnfs-svn413-win64-core2\

素因数分解してみる

YAFUでは素因数分解を含むさまざまな処理を関数の形で利用することができる。 中でも、factor関数は複数アルゴリズムを用いて素因数分解を行うものとなっている。

utility                 factoring               arithmetic
------------------------------------------------------------------------------------------
rsa                     factor                  shift
size                    siqs                    nroot
primes                  smallmpqs               modexp
nextprime               nfs                     sqrt
rand                    squfof                  lg2
randb                   pm1                     log
isprime                 pp1                     ln
ispow                   rho                     gcd
issquare                trial                   jacobi
sieverange              ecm                     modinv
testrange               fermat                  fib
bpsw                    snfs                    luc
aprcl                                           llt

次のようなコマンドにて、Msieveで4分程度かかった256 bitの合成数を4スレッド並列で素因数分解したところ、2分程度で計算が完了した。 出力内容から、試し割り、フェルマー法、Pollard-Rhoアルゴリズム、p-1アルゴリズムECMを順に用い、最終的にMPQSで素因数分解を行っていることが確認できる。

>yafu-x64.exe "factor(0x00b84b8a6ba2595165e095dd8226e513f5e42fa956339f0f5b4743b24c223c8603)" -v -threads 4


01/14/16 02:11:16 v1.34.5 @ LETSNOTE-SX3, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.1.1
detected Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
detected L1 = 32768 bytes, L2 = 3145728 bytes, CL = 64 bytes
measured cpu frequency ~= 2298.506410
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> fac: factoring 83359033011986879296513856404319061797526856544841606538718515
630707528467971
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C77
rho: x^2 + 2, starting 1000 iterations on C77
rho: x^2 + 1, starting 1000 iterations on C77
pm1: starting B1 = 150K, B2 = gmp-ecm default on C77
fac: setting target pretesting digits to 23.69
fac: sum of completed work is t0.00
fac: work done at B1=2000: 0 curves, max work = 30 curves
fac: 30 more curves at B1=2000 needed to get to t23.69
ecm: 30/30 curves on C77, B1=2K, B2=gmp-ecm default
fac: setting target pretesting digits to 23.69
fac: t15: 1.00
fac: t20: 0.04
fac: sum of completed work is t15.18
fac: work done at B1=11000: 0 curves, max work = 74 curves
fac: 74 more curves at B1=11000 needed to get to t23.69
ecm: 74/74 curves on C77, B1=11K, B2=gmp-ecm default
fac: setting target pretesting digits to 23.69
fac: t15: 7.17
fac: t20: 1.04
fac: t25: 0.05
fac: sum of completed work is t20.24
fac: work done at B1=50000: 0 curves, max work = 214 curves
fac: 149 more curves at B1=50000 needed to get to t23.69
ecm: 149/149 curves on C77, B1=50K, B2=gmp-ecm default, ETA: 0 sec
fac: setting target pretesting digits to 23.69
fac: t15: 28.45
fac: t20: 8.13
fac: t25: 0.74
fac: t30: 0.05
fac: sum of completed work is t20.24
fac: work done at B1=50000: 0 curves, max work = 214 curves
fac: 149 more curves at B1=50000 needed to get to t23.69
ecm: 149/149 curves on C77, B1=50K, B2=gmp-ecm default, ETA: 0 sec
fac: setting target pretesting digits to 23.69
fac: t15: 28.45
fac: t20: 8.13
fac: t25: 0.74
fac: t30: 0.05
fac: sum of completed work is t23.72

starting SIQS on c77: 8335903301198687929651385640431906179752685654484160653871
8515630707528467971

==== sieve params ====
n = 79 digits, 260 bits
factor base: 36160 primes (max prime = 915029)
single large prime cutoff: 77777465 (85 * pmax)
allocating 7 large prime slices of factor base
buckets hold 2048 elements
using SSE4.1 enabled 32k sieve core
sieve interval: 10 blocks of size 32768
polynomial A has ~ 10 factors
using multiplier of 19
using SPV correction of 20 bits, starting at offset 30
using SSE2 for x64 sieve scanning
using SSE2 for resieving 13-16 bit primes
using SSE2 for 8x trial divison to 13 bits
using SSE4.1 and inline ASM for small prime sieving
using SSE2 for poly updating up to 15 bits
using SSE4.1 for medium prime poly updating
using SSE4.1 and inline ASM for large prime poly updating
trial factoring cutoff at 90 bits

==== sieving in progress ( 4 threads):   36224 relations needed ====
====            Press ctrl-c to abort and save state            ====
36023 rels found: 18330 full + 17693 from 189619 partial, (1972.34 rels/sec)

sieving required 85170 total polynomials
trial division touched 3599367 sieve locations out of 55817011200
QS elapsed time = 106.0464 seconds.

==== post processing stage (msieve-1.38) ====
begin with 211149 relations
reduce to 52735 relations in 2 passes
attempting to read 52735 relations
recovered 52735 relations
recovered 39124 polynomials
freed 9 duplicate relations
attempting to build 36802 cycles
found 36802 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 18589
   length 2 : 18213
largest cycle: 2 relations
matrix is 36160 x 36802 (5.2 MB) with weight 1078755 (29.31/col)
sparse part has weight 1078755 (29.31/col)
filtering completed in 3 passes
matrix is 26299 x 26363 (4.1 MB) with weight 866014 (32.85/col)
sparse part has weight 866014 (32.85/col)
saving the first 48 matrix rows for later
matrix is 26251 x 26363 (3.4 MB) with weight 708442 (26.87/col)
sparse part has weight 634443 (24.07/col)
matrix includes 64 packed rows
using block size 10545 for processor cache size 3072 kB
commencing Lanczos iteration
memory use: 3.1 MB
lanczos halted after 416 iterations (dim = 26249)
recovered 17 nontrivial dependencies
Lanczos elapsed time = 2.1070 seconds.
Sqrt elapsed time = 0.0700 seconds.
SIQS elapsed time = 108.2240 seconds.
pretesting / qs ratio was 0.22
Total factoring time = 131.9222 seconds


***factors found***

P39 = 289260226283275563579648656678444936057
P39 = 288180072604771133716023733756993741403

ans = 1

factor関数は与える数の大きさが約320 bitを越えると、MPQSの代わりにGNFSを用いるようになる。 下の実行結果の通り、今回の環境では4スレッド並列で320 bitを2時間程度、384 bitを14時間程度にて素因数分解することができた。

>yafu-x64.exe "factor(0x00df34b665506dc5f87d35fca1fe966b11b27681942e69b712753602cb5c9bee39d37bb48471b7af9d)" -v -threads 4


01/14/16 04:41:01 v1.34.5 @ LETSNOTE-SX3, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.1.1
detected Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
detected L1 = 32768 bytes, L2 = 3145728 bytes, CL = 64 bytes
measured cpu frequency ~= 2289.501050
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> fac: factoring 18623629926741647734447892990738046138362290381569878848732125
84141889794599301578079441570475933
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C97
rho: x^2 + 2, starting 1000 iterations on C97
rho: x^2 + 1, starting 1000 iterations on C97
pm1: starting B1 = 150K, B2 = gmp-ecm default on C97
fac: setting target pretesting digits to 29.85
fac: sum of completed work is t0.00
fac: work done at B1=2000: 0 curves, max work = 30 curves
fac: 30 more curves at B1=2000 needed to get to t29.85
ecm: 30/30 curves on C97, B1=2K, B2=gmp-ecm default
fac: setting target pretesting digits to 29.85
fac: t15: 1.00
fac: t20: 0.04
fac: sum of completed work is t15.18
fac: work done at B1=11000: 0 curves, max work = 74 curves
fac: 74 more curves at B1=11000 needed to get to t29.85
ecm: 74/74 curves on C97, B1=11K, B2=gmp-ecm default
fac: setting target pretesting digits to 29.85
fac: t15: 7.17
fac: t20: 1.04
fac: t25: 0.05
fac: sum of completed work is t20.24
fac: work done at B1=50000: 0 curves, max work = 214 curves
fac: 214 more curves at B1=50000 needed to get to t29.85
ecm: 214/214 curves on C97, B1=50K, B2=gmp-ecm default, ETA: 0 sec
pm1: starting B1 = 3750K, B2 = gmp-ecm default on C97
fac: setting target pretesting digits to 29.85
fac: t15: 37.74
fac: t20: 11.23
fac: t25: 1.05
fac: t30: 0.07
fac: sum of completed work is t25.33
fac: work done at B1=250000: 0 curves, max work = 430 curves
fac: 390 more curves at B1=250000 needed to get to t29.85
ecm: 390/390 curves on C97, B1=250K, B2=gmp-ecm default, ETA: 1 sec
fac: setting target pretesting digits to 29.85
fac: t15: 115.74
fac: t20: 59.98
fac: t25: 8.85
fac: t30: 0.97
fac: t35: 0.08
fac: sum of completed work is t29.87
nfs: checking for job file - no job file found
nfs: checking for poly file - no poly file found
nfs: commencing nfs on c97: 1862362992674164773444789299073804613836229038156987
884873212584141889794599301578079441570475933
nfs: searching for brent special forms...
nfs: searching for homogeneous cunningham special forms...
nfs: searching for XYYXF special forms...
nfs: couldn't find special form
nfs: setting deadline of 225 seconds
nfs: commencing polynomial search over range: 1 - 251
commencing number field sieve (97-digit input)
nfs: commencing polynomial search over range: 251 - 501
commencing number field sieve (97-digit input)
nfs: commencing polynomial search over range: 501 - 751
commencing number field sieve (97-digit input)
nfs: commencing polynomial search over range: 751 - 1001
commencing number field sieve (97-digit input)
commencing number field sieve polynomial selection
commencing number field sieve polynomial selection
commencing number field sieve polynomial selection
commencing number field sieve polynomial selection
polynomial degree: 4
max stage 1 norm: 2.93e+016
max stage 2 norm: 1.42e+015
min E-value: 1.29e-008
poly select deadline: 1003
polynomial degree: 4
max stage 1 norm: 2.93e+016
max stage 2 norm: 1.42e+015
min E-value: 1.29e-008
poly select deadline: 1003
polynomial degree: 4
max stage 1 norm: 2.93e+016
max stage 2 norm: 1.42e+015
min E-value: 1.29e-008
poly select deadline: 1003
polynomial degree: 4
max stage 1 norm: 2.93e+016
max stage 2 norm: 1.42e+015
min E-value: 1.29e-008
poly select deadline: 1003
time limit set to 0.28 CPU-hours
expecting poly E from 1.96e-008 to > 2.26e-008
searching leading coefficients from 1 to 251
time limit set to 0.28 CPU-hours
expecting poly E from 1.96e-008 to > 2.26e-008
searching leading coefficients from 751 to 1001
time limit set to 0.28 CPU-hours
expecting poly E from 1.96e-008 to > 2.26e-008
searching leading coefficients from 251 to 501
time limit set to 0.28 CPU-hours
expecting poly E from 1.96e-008 to > 2.26e-008
searching leading coefficients from 501 to 751
searching leading coefficients from 501 to 751
deadline: 5 CPU-seconds per coefficient
deadline: 5 CPU-seconds per coefficient
deadline: 5 CPU-seconds per coefficient
deadline: 5 CPU-seconds per coefficient
coeff 12 specialq 1 - 20564 other 7315 - 17556
coeff 252 specialq 1 - 64432 other 4999 - 11997
aprogs: 304 entries, 922 roots
aprogs: 480 entries, 1474 roots
12 973884742889 627654680537405076769065
coeff 504 specialq 1 - 83563 other 4584 - 11001
coeff 756 specialq 1 - 97254 other 4358 - 10459
aprogs: 302 entries, 944 roots
aprogs: 295 entries, 864 roots
252 654986656399 293201338159686620882504
756 676465259 222784839818098969098945
(snip)

polynomial selection complete
R0: -401034424431043462338261
R1: 652775191453
A0: 13666786107026231161977467200
A1: -16093301653574737957248
A2: -1353086361656893
A3: 531875298
A4: 72
skew 5671101.83, size 2.601e-013, alpha -5.071, combined = 1.866e-008 rroots = 2

elapsed time of 652.9056 seconds exceeds 225 second deadline; poly select done
searching for best poly...
new best score = 1.321000e-008, new best line = 1
new best score = 1.349000e-008, new best line = 6
new best score = 1.355000e-008, new best line = 11
new best score = 1.456000e-008, new best line = 16
new best score = 1.459000e-008, new best line = 19
new best score = 1.469000e-008, new best line = 40
new best score = 1.478000e-008, new best line = 61
new best score = 1.494000e-008, new best line = 144
new best score = 1.518000e-008, new best line = 158
new best score = 1.555000e-008, new best line = 160
new best score = 1.677000e-008, new best line = 218
new best score = 1.838000e-008, new best line = 1336
new best score = 1.956000e-008, new best line = 4005
best poly:
# norm 3.659080e-013 alpha -4.543241 e 1.956e-008 rroots 4
n: 18623629926741647734447892990738046138362290381569878848732125841418897945993
01578079441570475933
skew: 1409169.75
c0: 325770881979370151487896520
c1: 1240463780963613095758
c2: -1451477525232085
c3: -1640771960
c4: 336
Y0: -272856818438382720008659
Y1: 1825347411121
nfs: commencing algebraic side lattice sieving over range: 825000 - 830000
nfs: commencing algebraic side lattice sieving over range: 820000 - 825000
nfs: commencing algebraic side lattice sieving over range: 810000 - 815000
nfs: commencing algebraic side lattice sieving over range: 815000 - 820000
gnfs-lasieve4I12e: L1_BITS=15, SVN $Revision: 406 $
gnfs-lasieve4I12e: L1_BITS=15, SVN $Revision: 406 $
gnfs-lasieve4I12e: L1_BITS=15, SVN $Revision: 406 $
 Warning:  lowering FB_bound to 824999.
 Warning:  lowering FB_bound to 814999.
 Warning:  lowering FB_bound to 809999.
gnfs-lasieve4I12e: L1_BITS=15, SVN $Revision: 406 $
 Warning:  lowering FB_bound to 819999.
FBsize 64380+0 (deg 4), 122539+0 (deg 1)
FBsize 64766+0 (deg 4), 122539+0 (deg 1)
FBsize 65540+0 (deg 4), 122539+0 (deg 1)
FBsize 65133+0 (deg 4), 122539+0 (deg 1)
total yield: 67753, q=820037 (0.00696 sec/rel)
367 Special q, 562 reduction iterations
reports: 192873602->25223739->23263435->5346992->5346254->4682300
Number of relations with k rational and l algebraic primes for (k,l)=:

Total yield: 67753
1403/922 mpqs failures, 37059/30861 vain mpqs
milliseconds total: Sieve 51115 Sched 0 medsched 21899
TD 348033 (Init 4638, MPQS 290056) Sieve-Change 40147
TD side 0: init/small/medium/large/search: 842 4910 1085 991 17498
sieve: init/small/medium/large/search: 1586 11321 1250 4631 7601
TD side 1: init/small/medium/large/search: 312 5068 1034 1079 310574
sieve: init/small/medium/large/search: 851 7503 1249 6292 8831
total yield: 71261, q=815029 (0.00690 sec/rel)
386 Special q, 568 reduction iterations
reports: 206147649->26949034->24850150->5598877->5598232->4903505
Number of relations with k rational and l algebraic primes for (k,l)=:
(snip)
Total yield: 72921
1598/1140 mpqs failures, 49531/36843 vain mpqs
milliseconds total: Sieve 53074 Sched 0 medsched 21947
TD 377429 (Init 5215, MPQS 313240) Sieve-Change 43252
TD side 0: init/small/medium/large/search: 862 5215 1110 1046 19661
sieve: init/small/medium/large/search: 1641 10790 1279 5268 8265
TD side 1: init/small/medium/large/search: 326 5329 1039 1078 336543
sieve: init/small/medium/large/search: 891 7367 1264 6328 9981
nfs: found 2983516 relations, need at least 2852068, proceeding with filtering .
..
nfs: commencing msieve filtering
18623629926741647734447892990738046138362290381569878848732125841418897945993015
78079441570475933
commencing relation filtering
estimated available RAM is 8098.3 MB
commencing duplicate removal, pass 1
found 224859 hash collisions in 3067360 relations
added 488 free relations
commencing duplicate removal, pass 2
found 112899 duplicates and 2954949 unique relations
memory use: 12.3 MB
reading ideals above 100000
commencing singleton removal, initial pass
memory use: 86.1 MB
reading all ideals from disk
memory use: 89.8 MB
keeping 3133635 ideals with weight <= 200, target excess is 24197
commencing in-memory singleton removal
begin with 2954949 relations and 3133635 unique ideals
reduce to 1283930 relations and 1168188 ideals in 21 passes
max relations containing the same ideal: 110
removing 274054 relations and 230217 ideals in 43837 cliques
commencing in-memory singleton removal
begin with 1009876 relations and 1168188 unique ideals
reduce to 959816 relations and 885563 ideals in 9 passes
max relations containing the same ideal: 90
removing 208239 relations and 164402 ideals in 43837 cliques
commencing in-memory singleton removal
begin with 751577 relations and 885563 unique ideals
reduce to 711901 relations and 679522 ideals in 10 passes
max relations containing the same ideal: 72
relations with 0 large ideals: 463
relations with 1 large ideals: 1278
relations with 2 large ideals: 10594
relations with 3 large ideals: 48262
relations with 4 large ideals: 124603
relations with 5 large ideals: 202861
relations with 6 large ideals: 185798
relations with 7+ large ideals: 138042
commencing 2-way merge
reduce to 412969 relation sets and 380590 unique ideals
commencing full merge
memory use: 40.5 MB
found 191499 cycles, need 184790
weight of 184790 cycles is about 13135883 (71.09/cycle)
distribution of cycle lengths:
1 relations: 17275
2 relations: 17556
3 relations: 17832
4 relations: 16609
5 relations: 15885
6 relations: 14849
7 relations: 13210
8 relations: 11877
9 relations: 10575
10+ relations: 49122
heaviest cycle: 22 relations
commencing cycle optimization
start with 1267678 relations
pruned 34157 relations
memory use: 40.3 MB
distribution of cycle lengths:
1 relations: 17275
2 relations: 17960
3 relations: 18478
4 relations: 17101
5 relations: 16315
6 relations: 15212
7 relations: 13518
8 relations: 12011
9 relations: 10773
10+ relations: 46147
heaviest cycle: 22 relations
RelProcTime: 48
nfs: commencing msieve linear algebra

commencing linear algebra
read 184790 cycles
cycles contain 658609 unique relations
read 658609 relations
using 20 quadratic characters above 33553520
building initial matrix
memory use: 80.2 MB
read 184790 cycles
matrix is 184607 x 184790 (55.5 MB) with weight 17533863 (94.89/col)
sparse part has weight 12514965 (67.73/col)
filtering completed in 2 passes
matrix is 183988 x 184170 (55.4 MB) with weight 17502133 (95.03/col)
sparse part has weight 12501110 (67.88/col)
matrix starts at (0, 0)
matrix is 183988 x 184170 (55.4 MB) with weight 17502133 (95.03/col)
sparse part has weight 12501110 (67.88/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 183940 x 184170 (52.9 MB) with weight 13774342 (74.79/col)
sparse part has weight 12022779 (65.28/col)
using block size 65536 for processor cache size 3072 kB
commencing Lanczos iteration
memory use: 39.7 MB
linear algebra at 6.6%, ETA 0h 3m 184170 dimensions (6.6%, ETA 0h 3m)
linear algebra completed 182137 of 184170 dimensions (98.9%, ETA 0h 0m)
lanczos halted after 2910 iterations (dim = 183940)
recovered 33 nontrivial dependencies
BLanczosTime: 266
nfs: commencing msieve sqrt
commencing square root phase
reading relations for dependency 1
read 92350 cycles
cycles contain 330090 unique relations
read 330090 relations
multiplying 330090 relations
multiply complete, coefficients have about 13.03 million bits
initial square root is modulo 30742633
GCD is 1, no factor found
reading relations for dependency 2
read 91669 cycles
cycles contain 328470 unique relations
read 328470 relations
multiplying 328470 relations
multiply complete, coefficients have about 12.97 million bits
initial square root is modulo 28276979
GCD is N, no factor found
reading relations for dependency 3
read 91921 cycles
cycles contain 328398 unique relations
read 328398 relations
multiplying 328398 relations
multiply complete, coefficients have about 12.96 million bits
initial square root is modulo 28137013
sqrtTime: 66
NFS elapsed time = 6782.2092 seconds.
pretesting / nfs ratio was 0.05
Total factoring time = 7127.1257 seconds


***factors found***

P49 = 1451135465007329936687682012556458198263354033267
P49 = 1283383279909541494981671251013593566543423047599

ans = 1
>yafu-x64.exe "factor(0x00baefb8b7a7840aa2cb78d9d1f22a367be1214e9552ccee4c0d78a5ec99c3ba0bfa23d857b0b6ed2773e50c76fbb179a9)" -v -threads 4
(snip)
commencing square root phase
reading relations for dependency 1
read 269122 cycles
cycles contain 934630 unique relations
read 934630 relations
multiplying 934630 relations
multiply complete, coefficients have about 37.80 million bits
initial square root is modulo 267517
sqrtTime: 157
NFS elapsed time = 45999.5370 seconds.
pretesting / nfs ratio was 0.09
Total factoring time = 50087.5248 seconds


***factors found***

P58 = 4911154640312831735300579932662636306005188439240020352879
P58 = 5858530077012370931106950309549472688326371985155604622439

ans = 1

なお、RSA鍵のように小さな数を因数に持たないことがわかっている場合には、factor関数の代わりにsiqsあるいはnfs関数を用いることで、ECMまでのステップを飛ばして計算することも可能である。

フェルマー法による素因数分解

上で触れたように、factor関数はフェルマー法による素因数分解も試みる。 そのため、下の実行結果の通り、「単純な素因数分解アルゴリズムを実装してみる」で例に用いた4096 bitの合同数も素因数分解できる。 ただし、今回の環境では結果を出力した後にプログラムはクラッシュした。

>yafu-x64.exe "factor(1034186074668005446865661651578208369514158803552244005581133348807218259696136975186768057532805396894757503164834709575083359161158060701923008831149233177215596305395749862300700772298386522636562203611668211601359078939366452933448401372783149865070405032946502692195960337152490393257718681775969357953766124434670452760182942622011519373645653657784274264774773270847089540432369489508909290697992927057404389218509541644042197448296417276686963995927414541514778710278820030649227976349765070908207584414253880096569270321293357683127769728901749940165024782079154839570419235490028108256539125090626571373643257455521820767805808214404175900736109428513289545954241551995058498737472560704736894014465695117165251699935296644992760434412206519036326801985540077086806228464411438175416317958133959586691011057808141234300883692932436022122663781160823472736298914304029803683697389880156222528045623045436226522780569221934366978973936408257173404970887883159180079205465195884955186605310665826226975454171035075016280417683011623124380312403051425940705920625660567584606796218038626946234225864706878239646554381165540673005572649955471689205027195933802181344480474070023069194083134722979170599617466579222550596280381011)" -v -threads 4


01/15/16 01:30:43 v1.34.5 @ LETSNOTE-SX3, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.1.1
detected Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
detected L1 = 32768 bytes, L2 = 3145728 bytes, CL = 64 bytes
measured cpu frequency ~= 2308.637110
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> fac: factoring 10341860746680054468656616515782083695141588035522440055811333
48807218259696136975186768057532805396894757503164834709575083359161158060701923
00883114923317721559630539574986230070077229838652263656220361166821160135907893
93664529334484013727831498650704050329465026921959603371524903932577186817759693
57953766124434670452760182942622011519373645653657784274264774773270847089540432
36948950890929069799292705740438921850954164404219744829641727668696399592741454
15147787102788200306492279763497650709082075844142538800965692703212933576831277
69728901749940165024782079154839570419235490028108256539125090626571373643257455
52182076780580821440417590073610942851328954595424155199505849873747256070473689
40144656951171652516999352966449927604344122065190363268019855400770868062284644
11438175416317958133959586691011057808141234300883692932436022122663781160823472
73629891430402980368369738988015622252804562304543622652278056922193436697897393
64082571734049708878831591800792054651958849551866053106658262269754541710350750
16280417683011623124380312403051425940705920625660567584606796218038626946234225
86470687823964655438116554067300557264995547168920502719593380218134448047407002
3069194083134722979170599617466579222550596280381011
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 0.7157 seconds


***factors found***

PRP617 = 32158763574926282399690427421751598974822750157866002942864427634852437
38054001758645149385466172990938051873364918662438520673733632481310950023760330
40260091126965655108468499879374236192629733939691750567598216521388697832153781
69757835283584660846583208812725733839059137580944002686113912792569631796916069
73243177559932045834693785958981549752582862262265216570927115224646472848992767
06966010162485595159519321546866335991009453149218342273243819587511846849798242
41375253606863601895383658582486045363570755445629865194046700806542078378801136
397577730247660070033517187439537339428288763342861366560261446073
PRP617 = 32158763574926282399690427421751598974822750157866002942864427634852437
38054001758645149385466172990938051873364918662438520673733632481310950023760330
40260091126965655108468499879374236192629733939691750567598216521388697832153781
69757835283584660846583208812725733839059137580944002686113912792569631796916069
73243177559932045834693785958981549752582862262265216570927115224646472848992767
06966010162485595159519321546866335991009453149218342273243819587511846849798242
41375253606863601895383658582486045363570755445629865194046700806542078378801136
397577730247660070033517187439537339428288763342861366560261414507

ans = 1

関連リンク