mersenneforum.org Error: tiny factoring failed
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2009-01-22, 18:42 #1 10metreh     Nov 2008 1001000100102 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 This does not look enlightening, but what was printed to the DOS window looks like a bug in msieve: 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 What on earth made this happen? GMP-ECM factors this fine: it is 153108022657 * 79810635304691.
 2009-01-22, 19:30 #2 MatWur-S530113     Apr 2007 Spessart/Germany 2×34 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 15-digit factors Thu Jan 22 20:25:50 2009 P-1 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 best regards, Matthias Last fiddled with by MatWur-S530113 on 2009-01-22 at 19:31 Reason: 1 s missed, p30 correctet to p28
2009-01-22, 19:45   #3
bsquared

"Ben"
Feb 2007

1101011011012 Posts

Quote:
 Originally Posted by MatWur-S530113 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 15-digit factors Thu Jan 22 20:25:50 2009 P-1 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 best regards, Matthias
This worked because it made the number big enough to be factored using SIQS. For really small inputs like the C26, siqs is too cumbersome to use (for a variety of reasons), and msieve resorts to its "tinyqs" routine. The bug is apparently in there. Tinyqs uses ordinary mpqs, and according to the comments in the source, "The practical upper limit on the input size is 85 bits, about 25-26 digits". All that said, I don't know where the code is failing.

- ben.

2009-01-22, 20:07   #4
10metreh

Nov 2008

2×33×43 Posts

Quote:
 Originally Posted by bsquared This worked because it made the number big enough to be factored using SIQS. For really small inputs like the C26, siqs is too cumbersome to use (for a variety of reasons), and msieve resorts to its "tinyqs" routine. The bug is apparently in there. Tinyqs uses ordinary mpqs, and according to the comments in the source, "The practical upper limit on the input size is 85 bits, about 25-26 digits". All that said, I don't know where the code is failing. - ben.
This seems to be the only thing ATM that prevents msieve from being a general-purpose factoring program. Why doesn't it use P-1 etc?

2009-01-22, 20:36   #5
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2×5×587 Posts

Quote:
 Originally Posted by 10metreh This seems to be the only thing ATM that prevents msieve from being a general-purpose factoring program. Why doesn't it use P-1 etc?
it does in fact that factorization Matthias succeeded in earlier didnt get past P-1 and ECM
Thu Jan 22 20:25:50 2009 P-1 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

2009-01-22, 20:38   #6
10metreh

Nov 2008

2×33×43 Posts

Quote:
 Originally Posted by henryzz it does in fact that factorization Matthias succeeded in earlier didnt get past P-1 and ECM Thu Jan 22 20:25:50 2009 P-1 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
I meant for the "tiny" numbers.

 2009-01-22, 20:46 #7 MatWur-S530113     Apr 2007 Spessart/Germany 2·34 Posts Hello, I would say the SIQS first performs a P-1 (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 P-1 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
2009-01-22, 21:03   #8
bsquared

"Ben"
Feb 2007

7×491 Posts

Quote:
 Originally Posted by MatWur-S530113 Hello, I would say the SIQS first performs a P-1 (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 P-1 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
From what I can tell in the code, the order of operations is:

1.) trial divide
2.) pollard Rho
3.) P-1, ECM
4.) SIQS

Caveats:
3.) only gets used if the user has GMP-ECM 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 P-1. This is because for numbers 26 digits in size, it doesn't make a lot of sense to use P-1 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 P-1 or ECM reduces an input to below the threshold, tinyqs will still be used instead of the full SIQS.

2009-01-22, 22:44   #9
MatWur-S530113

Apr 2007
Spessart/Germany

2·34 Posts

Quote:
 Originally Posted by bsquared From what I can tell in the code, the order of operations is: 1.) trial divide 2.) pollard Rho 3.) P-1, ECM 4.) SIQS Caveats: 3.) only gets used if the user has GMP-ECM 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 P-1. This is because for numbers 26 digits in size, it doesn't make a lot of sense to use P-1 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 P-1 or ECM reduces an input to below the threshold, tinyqs will still be used instead of the full SIQS.
Some problems with this.
I have GMP-ECM, but I never configured msieve to use it. Thus there must be a built-in function for P-1 and ECM.
But in the first tests (with the original C26) P-1 and/or ECM wasn't called.
Thus the QS was called *before* calling the P-1 and/or ECM built-in function.

But how do I configure msieve to use GMP-ECM. Is it possible with the windows binary or have I to compile such a msieve.exe for myself?

best regards,

Matthias

2009-01-22, 23:10   #10
bsquared

"Ben"
Feb 2007

1101011011012 Posts

Quote:
 Originally Posted by MatWur-S530113 Some problems with this. I have GMP-ECM, but I never configured msieve to use it. Thus there must be a built-in function for P-1 and ECM.
The windows binary from the website appears to have the GMP-ECM code included, so I'm wrong about you needing to configure it. Configuration is needed if you are going to build the source from scratch. The msieve library doesn't include any P-1 or ECM code.

Quote:
 Originally Posted by MatWur-S530113 But in the first tests (with the original C26) P-1 and/or ECM wasn't called. Thus the QS was called *before* calling the P-1 and/or ECM built-in function.
Yes, because it's too small. I thought I mentioned that fact under caveats to 3.) Rereading it, maybe I wasn't clear.

Quote:
 Originally Posted by MatWur-S530113 But how do I configure msieve to use GMP-ECM. Is it possible with the windows binary or have I to compile such a msieve.exe for myself? best regards, Matthias
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.

 2009-01-22, 23:24 #11 jasonp Tribal Bullet     Oct 2004 33·131 Posts Ben is right, you do not need ecm.exe because the GMP-ECM 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/P-1/ECM work, with progressively increasing B1 and B2, depending on the size of the input. I wrote that code to avoid everyone having to hand-roll 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 GMP-ECM to be built already; if you're building the source from the included makefile, you have to invoke make with 'ECM=1' to get GMP-ECM linked in. Last fiddled with by jasonp on 2009-01-22 at 23:31

 Similar Threads Thread Thread Starter Forum Replies Last Post 3.14159 Miscellaneous Math 947 2021-02-13 08:40 Rodrigo Software 19 2011-02-15 04:32 petrw1 LMH > 100M 1 2010-07-13 15:35 jasong Factoring 2 2006-02-26 22:18 antiroach NFSNET Discussion 1 2003-07-08 00:27

All times are UTC. The time now is 03:38.

Tue May 11 03:38:17 UTC 2021 up 32 days, 22:19, 1 user, load averages: 2.14, 1.99, 1.95