20090122, 18:42  #1 
Nov 2008
100100010010_{2} Posts 
Error: tiny factoring failed
Code:
Thu Jan 22 18:37:38 2009 Thu Jan 22 18:37:38 2009 Thu Jan 22 18:37:38 2009 Msieve v. 1.39 Thu Jan 22 18:37:38 2009 random seeds: 3ef511e8 668c8c88 Thu Jan 22 18:37:38 2009 factoring 12219648558500193726383987 (26 digits) Thu Jan 22 18:37:39 2009 elapsed time 00:00:01 Code:
Msieve v. 1.39 Thu Jan 22 18:37:38 2009 random seeds: 3ef511e8 668c8c88 factoring 12219648558500193726383987 (26 digits) error: tiny factoring failed elapsed time 00:00:01 GMPECM factors this fine: it is 153108022657 * 79810635304691. 
20090122, 19:30  #2 
Apr 2007
Spessart/Germany
2×3^{4} Posts 
Hello,
I tried msieve v1.31  v1.38, all failed to factor this number. But I got the factors by multiplying the number with a (random choosen) p28: Code:
Thu Jan 22 20:25:50 2009 Thu Jan 22 20:25:50 2009 Msieve v. 1.38 Thu Jan 22 20:25:50 2009 random seeds: 38f70120 8cfa2f29 Thu Jan 22 20:25:50 2009 factoring 14931981089325586245890766903754586738781611574879977 (53 digits) Thu Jan 22 20:25:50 2009 searching for 15digit factors Thu Jan 22 20:25:50 2009 P1 stage 1 factor found Thu Jan 22 20:25:50 2009 ECM stage 2 factor found Thu Jan 22 20:25:50 2009 prp12 factor: 153108022657 Thu Jan 22 20:25:50 2009 prp14 factor: 79810635304691 Thu Jan 22 20:25:50 2009 prp28 factor: 1221964855850019372638398771 Thu Jan 22 20:25:50 2009 elapsed time 00:00:00 Matthias Last fiddled with by MatWurS530113 on 20090122 at 19:31 Reason: 1 s missed, p30 correctet to p28 
20090122, 19:45  #3  
"Ben"
Feb 2007
110101101101_{2} Posts 
Quote:
 ben. 

20090122, 20:07  #4  
Nov 2008
2×3^{3}×43 Posts 
Quote:


20090122, 20:36  #5  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×5×587 Posts 
Quote:
Thu Jan 22 20:25:50 2009 P1 stage 1 factor found Thu Jan 22 20:25:50 2009 ECM stage 2 factor found Thu Jan 22 20:25:50 2009 prp12 factor: 153108022657 Thu Jan 22 20:25:50 2009 prp14 factor: 79810635304691 Thu Jan 22 20:25:50 2009 prp28 factor: 1221964855850019372638398771 

20090122, 20:38  #6  
Nov 2008
2×3^{3}×43 Posts 
Quote:


20090122, 20:46  #7 
Apr 2007
Spessart/Germany
2·3^{4} Posts 
Hello,
I would say the SIQS first performs a P1 (factor 1 was found, very smooth...), then some curves ECM (factor 2...) and if the remaining cofactor is still composite then it performs MPQS. Tinyqs seems to perform a 'normal' QS (without 'multi polynominal', the upper limit of MPQS is ~120digit ~400bit). It is simply a part of the 'Self Initializing' algorithm. Obviously it is performed, because the first TF failed, then SI is called. But the input is too small > tinyqs. Maybe it is better to perform first the P1 in SI, then perform the ECM in SI and then (if the input is too low for MPQS) switch to tinyqs and perform the QS. I don't know the code because I'm not a C++programmer. But I think only some changes in order to call these functions could solve many of those 'tiny'problems. best regards, Matthias 
20090122, 21:03  #8  
"Ben"
Feb 2007
7×491 Posts 
Quote:
1.) trial divide 2.) pollard Rho 3.) P1, ECM 4.) SIQS Caveats: 3.) only gets used if the user has GMPECM available and msieve is configured to know about it. Msieve doesn't contain a native implementation of those algorithms. 3.) also only gets called if the number is above a certain threshold size, which the C26 is not. That's why 10metreh's number didn't get P1. This is because for numbers 26 digits in size, it doesn't make a lot of sense to use P1 and ECM if you have a QS routine sitting around which you *know* will find the factors in milliseconds (ignoring the bug, of course). 4.) may instead use tinyqs if the number is below the threshold size. So if P1 or ECM reduces an input to below the threshold, tinyqs will still be used instead of the full SIQS. 

20090122, 22:44  #9  
Apr 2007
Spessart/Germany
2·3^{4} Posts 
Quote:
I have GMPECM, but I never configured msieve to use it. Thus there must be a builtin function for P1 and ECM. But in the first tests (with the original C26) P1 and/or ECM wasn't called. Thus the QS was called *before* calling the P1 and/or ECM builtin function. But how do I configure msieve to use GMPECM. Is it possible with the windows binary or have I to compile such a msieve.exe for myself? best regards, Matthias 

20090122, 23:10  #10  
"Ben"
Feb 2007
110101101101_{2} Posts 
Quote:
Quote:
As I just discovered, the windows binary from the website doesn't seem to need any configuration. If you are trying to build it yourself that's different, and I'm probably not qualified to answer that. 

20090122, 23:24  #11 
Tribal Bullet
Oct 2004
3^{3}·131 Posts 
Ben is right, you do not need ecm.exe because the GMPECM library is compiled directly into the msieve official binary. Someone was working on a patch to switch to ECM if the tiny MPQS code fails, but it's tricky to do this because the B1 and B2 bounds must be extremely small or else ECM will never split N, it will just keep finding a factor of N.
Msieve runs P+1 and a few ECM curves on any input number that is not small enough that the tiny factoring code is required. You can run with 'e' as well and it will do progressively more P+1/P1/ECM work, with progressively increasing B1 and B2, depending on the size of the input. I wrote that code to avoid everyone having to handroll scripts / batch files / UBASIC programs that run ecm.exe and then msieve.exe with manually determined ranges of work bounds. The tiny factoring problem has been known for a long time, and only happens very rarely. I haven't had the time to track it down. PS: If compiling the library yourself, Brian Gladman's MSVC project expects GMPECM to be built already; if you're building the source from the included makefile, you have to invoke make with 'ECM=1' to get GMPECM linked in. Last fiddled with by jasonp on 20090122 at 23:31 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Thread for posting tiny primes  3.14159  Miscellaneous Math  947  20210213 08:40 
Factoring software for tiny Linux versions  Rodrigo  Software  19  20110215 04:32 
Tiny range request .... 555.1M  petrw1  LMH > 100M  1  20100713 15:35 
"Connection to socket failed" error for about 24 hours  jasong  Factoring  2  20060226 22:18 
Tiny error on nfsnet pages.  antiroach  NFSNET Discussion  1  20030708 00:27 