Unwilling number.

[storflyt32]

A number I came across a little while ago.

125169005719914348816520676003006990595104088750459775327657394996598953675214064913848636757851

This number is not willing to factorize.

Can anyone offer some advice please?

Thanks!

[Mini-Geek]

You can use YAFU to factorize that number (a c96, which means a 96-digit composite) in a fairly short amount of time (seconds, minutes, or hours for a number of this size, depending on what it takes to crack it). It will use ECM, QS, NFS, etc. as needed to find its factors in the best time it can. Use this command:

factor(125169005719914348816520676003006990595104088750459775327657394996598953675214064913848636757851)

(assuming the number isn't of a particularly special form and hasn't been checked for factors to a significant depth, that's a good way to have YAFU do some factorization efforts before going to the long QS/NFS factorization methods)

[Ralf Recker]

Originally Posted by Mini-Geek

(seconds, minutes, or hours for a number of this size, depending on what it takes to crack it)

10 minutes 6 seconds with NFS. Probably faster with ECM depending on your luck:

GMP-ECM 7.0-dev [configured with GMP 5.1.3, --enable-asm-redc, --enable-gpu, --enable-assert, --enable-openmp] [ECM]
Using B1=1000000, B2=1045563762, polynomial Dickson(6), 8 threads
Done 297/2400; avg s/curve: stg1 2.115s, stg2 1.427s; runtime: 137s

Run 297 out of 2400:
Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=1:3545553215
Step 1 took 2116ms
Step 2 took 1436ms
********** Factor found in step 2: 1576422053186621557751857821413401
Found probable prime factor of 34 digits: 1576422053186621557751857821413401
Probable prime cofactor 79400694418664331852968752783562533762348560846718294611714451 has 62 digits

Note to myself: 2400 curves for 3e6...

[bsquared]

3.28 seconds for me.

Guess I got lucky .

[Ralf Recker]

Originally Posted by bsquared

3.28 seconds for me.

Guess I got lucky .

FactorDB?

[bsquared]

Originally Posted by Ralf Recker

FactorDB?

% ./yafu "factor(125169005719914348816520676003006990595104088750459775327657394996598953675214064913848636757851)" -v -threads 16


11/18/13 12:06:23 v1.34.5 @ gree.mayo.edu, System/Build Info:
Using GMP-ECM 6.4.4, Powered by GMP 5.1.1
detected        Intel(R) Xeon(R) CPU E5-4650 0 @ 2.70GHz
detected L1 = 32768 bytes, L2 = 20971520 bytes, CL = 64 bytes
measured cpu frequency ~= 2699.961480
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 125169005719914348816520676003006990595104088750459775327657394996598953675214064913848636757851
fac: using pretesting plan: normal
fac: using tune info for qs/gnfs crossover
div: primes less than 10000
rho: x^2 + 3, starting 1000 iterations on C96
rho: x^2 + 2, starting 1000 iterations on C96
rho: x^2 + 1, starting 1000 iterations on C96
fac: ecm effort reduced from 29.54 to 22.97: input has snfs form
pm1: starting B1 = 150K, B2 = gmp-ecm default on C96
fac: ecm effort reduced from 29.54 to 22.97: input has snfs form
fac: setting target pretesting digits to 22.97
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 t22.97
ecm: 30/30 curves on C96, B1=2K, B2=gmp-ecm default
fac: ecm effort reduced from 29.54 to 22.97: input has snfs form
fac: setting target pretesting digits to 22.97
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 t22.97
ecm: 74/74 curves on C96, B1=11K, B2=gmp-ecm default
fac: ecm effort reduced from 29.54 to 22.97: input has snfs form
fac: setting target pretesting digits to 22.97
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: 117 more curves at B1=50000 needed to get to t22.97
ecm: 16/128 curves on C96, B1=50K, B2=gmp-ecm default, ETA: 2 sec
ecm: found prp34 factor = 1576422053186621557751857821413401

fac: ecm effort reduced from 19.08 to 14.84: input has snfs form
fac: setting target pretesting digits to 14.84
fac: t15: 11.74
fac: t20: 2.56
fac: t25: 0.20
fac: t30: 0.01
fac: sum of completed work is t20.99
pretesting / qs ratio was 86.03
Total factoring time = 3.2817 seconds


***factors found***

P34 = 1576422053186621557751857821413401
P62 = 79400694418664331852968752783562533762348560846718294611714451

ans = 1

But apparently the input has a SNFS form, so even if the ecm factor was missed it would have only taken a few minutes, as you said.

[wombatman]

Lanczos elapsed time = 48.2060 seconds.
Sqrt elapsed time = 0.7590 seconds.
SIQS elapsed time = 1325.4398 seconds.
pretesting / qs ratio was 0.30
Total factoring time = 1727.5118 seconds


***factors found***

P34 = 1576422053186621557751857821413401
P62 = 79400694418664331852968752783562533762348560846718294611714451

Apparently I was very unlucky...

[Mini-Geek]

Originally Posted by bsquared

ecm: 16/128 curves on C96, B1=50K, B2=gmp-ecm default, ETA: 2 sec
ecm: found prp34 factor = 1576422053186621557751857821413401

That's an incredibly lucky find! Do you happen to have the sigma for that?

I found the p34 factor as well, with B1=250000 bounds, sigma 1938467591. That group order factors as [ <2, 3>, <3, 1>, <6151, 1>, <65353, 1>, <91961, 1>, <92593, 1>, <153719, 1>, <124836221, 1> ]

I get Ralf Recker's sigma (assuming it's 3545553215), as [ <2, 3>, <3, 2>, <4909, 1>, <4460124412039738652099414071, 1> ] so either the Dickson polynomial threw in the large factor, or I need to do something to account for the "1:" before it.

[bsquared]

Originally Posted by Mini-Geek

That's an incredibly lucky find! Do you happen to have the sigma for that?

I found the p34 factor as well, with B1=250000 bounds, sigma 1938467591. That group order factors as [ <2, 3>, <3, 1>, <6151, 1>, <65353, 1>, <91961, 1>, <92593, 1>, <153719, 1>, <124836221, 1> ]

I get Ralf Recker's sigma (assuming it's 3545553215), as [ <2, 3>, <3, 2>, <4909, 1>, <4460124412039738652099414071, 1> ] so either the Dickson polynomial threw in the large factor, or I need to do something to account for the "1:" before it.

11/18/13 12:06:27 v1.34.5 @ xxx.yyy.zzz, prp34 = 1576422053186621557751857821413401 (curve 2 stg2 B1=50000 sigma=2945162712 thread=13)

[Mini-Geek]

That group order is indeed very smooth:
[ <2, 4>, <3, 2>, <7, 1>, <47, 1>, <269, 1>, <6899, 1>, <8243, 1>, <15607, 1>, <17497, 1>, <48487, 1>, <164279, 1> ]
GMP-ECM reports that the expected number of curves at those bounds to find a factor of 35 digits is 69076 (34 digits will be close). We collectively have surely run this early ECM way too much, maybe 1000 or 2000 curves? Even so, I estimate a 1-3% chance of finding it at these bounds.
Given the ECM depth that YAFU targets, the most likely course of action for this number should be to QS or GNFS it. Either due to sampling bias (we are more likely to post here if we find it than if we fail, or cancel during QS/NFS) or luck, we seem to be finding this factor far more often than that!

It's worth noting that the number that this thread is all about is a cofactor of 2^725+1, which has already been factored.

[storflyt32]

2^1968721+1 has a factor 3 ...