mersenneforum.org msieve 1.53 refusing to work on factoring a number
 Register FAQ Search Today's Posts Mark Forums Read

 2022-11-20, 00:36 #1 IamMusavaRibica   Nov 2022 2×3 Posts msieve 1.53 refusing to work on factoring a number I'm running msieve 1.53 downloaded from sourceforge on Windows 10 With input number: Code: 592882521637563371255988933569562526270730127954281578371022521620306952310392510665598219753586428161197028620328266639362113343141594645707449734951628116538375683863626055767435783194371195814008292968003192702648520406175128014572590661900720692085587865317 when run using msieve153 -n -v this is the output: Code: Msieve v. 1.53 (SVN 1005) Sun Nov 20 01:28:58 2022 random seeds: 5f88e2c0 38e923d1 factoring 592882521637563371255988933569562526270730127954281578371022521620306952310392510665598219753586428161197028620328266639362113343141594645707449734951628116538375683863626055767435783194371195814008292968003192702648520406175128014572590661900720692085587865317 (261 digits) searching for 15-digit factors commencing number field sieve (261-digit input) commencing number field sieve polynomial selection polynomial degree: 6 max stage 1 norm: 6.21e+033 max stage 2 norm: 9.75e+033 min E-value: 0.00e+000 poly select deadline: 1079999 time limit set to 300.00 CPU-hours expecting poly E from 8.34e-019 to > 9.59e-019 searching leading coefficients from 1 to 164176515 deadline: 3200 CPU-seconds per coefficient randomizing rational coefficient: using piece #41 of 450 coeff 12 specialq 72547801 - 74361496 other 20694795 - 49667508 aprogs: 577224 entries, 2323662 roots 12 68353482965301129500575 19155694413565757733110803778099867582806616 :line minimize failed 12 85124664293115719030869 19155694413565876261099613116039675398342599 :line minimize failed :line minimize failed :line minimize failed 12 83885369207355693831131 19155694413565766216761394420441478348364978 :12 56098656403317214940749 19155694413565774792238272684407892147945377 :line minimize failed :line minimize failed :line minimize failed when terminating with Ctrl+C or running with -nc option, it outputs 'error generating or reading NFS polynomials' and running with no extra arguments (msieve153 -v ) this is the output: Code: searching for 15-digit factors commencing quadratic sieve (261-digit input) using multiplier of 7 using generic 32kb sieve core sieve interval: 400 blocks of size 32768 processing polynomials in batches of 1 using a sieve bound of 42921973 (1299417 primes) using large prime bound of 4294967295 (31 bits) using double large prime bound of 218437776016143360 (51-58 bits) using trial factoring cutoff of 58 bits fatal error: poly selection failed While the elliptic curve method works just fine Does anyone know why is this happening? I cleared the directory of all msieve.fb .dat and relevant files. Last fiddled with by IamMusavaRibica on 2022-11-20 at 00:36
2022-11-20, 01:09   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100111011100012 Posts

Quote:
 Originally Posted by IamMusavaRibica ...commencing quadratic sieve (261-digit input)... Does anyone know why is this happening? I cleared the directory of all msieve.fb .dat and relevant files.
Short answer is you are using the specialized tool as a general tool.
msieve if called in commandline like you did will default to QS (quadratic sieve); this is not going to work with a 261-digit input. msieve is a very good tool when used correctly, but it is not a tool that will do everything for you.

Instead, the shortest recipe is - install another tool - yafu. (It actually uses msieve, as well, internally)

2022-11-20, 03:57   #3
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

2×7×263 Posts

Quote:
 Originally Posted by IamMusavaRibica I'm running msieve 1.53 downloaded from sourceforge on Windows 10 With input number: Code: 592882521637563371255988933569562526270730127954281578371022521620306952310392510665598219753586428161197028620328266639362113343141594645707449734951628116538375683863626055767435783194371195814008292968003192702648520406175128014572590661900720692085587865317
This number has as long as 261 digits (and is a cofactor of 2^1274-958, which may have SNFS polynomial, but I am not sure), if this number can be factored, then 2^1217-1 (with a composite of 248 digits) and 2^1109+1 (with a composite of 225 digits) as well as 10^383-1 (with a composite of 230 digits) can also be factored.

Last fiddled with by sweety439 on 2022-11-20 at 03:57

 2022-11-20, 16:41 #4 chris2be8     Sep 2009 32·271 Posts According to factordb it's (2^1274-958)/548587400055100020569633729957403536012167283572060233678280830124443453419873609038059209411506178791106026467603646596378. But SNFS is probably slower than GNFS for it. So if you have to ask about how to factor it then it's too big a job for you (I could not do it even with help from NFS@Home). It could be simplified to (2^1273-479)/274293700027550010284816864978701768006083641786030116839140415062221726709936804519029604705753089395553013233801823298189 but that doesn't make it significantly easier to factor.
 2022-11-20, 23:51 #5 IamMusavaRibica   Nov 2022 2×3 Posts Thanks everyone The number is aswell equal to (2^1277-7664)/4388699200440800164557069839659228288097338268576481869426246640995547627358988872304473675292049430328848211740829172771024 Yafu was a bit complicated to set up but I'll try again I guess
 2022-11-21, 01:10 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23×439 Posts For your input number, your best hope is ecm.py (or you can run ecm with appropriate B1,B2 in several threads manually).
2022-11-21, 04:58   #7
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

52·229 Posts

Quote:
 Originally Posted by IamMusavaRibica Yafu was a bit complicated to set up but I'll try again I guess
Why? Did you not believe the poster from post #4, who gently explained the job is too big for you?

Rather than explain why and have you ignore me too, I'll just advise you to learn to factor numbers by starting small and working your way up. Try a 100-digit number, then 110, then 120, then 130. Note how the time taken scales up every time you jump 10 digits, and extend that scaling to your 260 digit number. You'll be disappointed in the forecast for a 260 digit factorization.

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH Factoring 39 2022-11-18 14:55 EdH Msieve 8 2022-10-02 21:05 donleon87 Msieve 2 2021-10-06 11:12 EdH Factoring 3 2010-11-12 18:11 aaa120 Msieve 7 2008-11-27 16:50

All times are UTC. The time now is 12:32.

Thu Mar 30 12:32:56 UTC 2023 up 224 days, 10:01, 0 users, load averages: 0.55, 0.67, 0.67