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
