mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-01-22, 18:42   #1
10metreh
 
10metreh's Avatar
 
Nov 2008

1001000100102 Posts
Default 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.
10metreh is offline   Reply With Quote
Old 2009-01-22, 19:30   #2
MatWur-S530113
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

2×34 Posts
Default

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
MatWur-S530113 is offline   Reply With Quote
Old 2009-01-22, 19:45   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101011011012 Posts
Default

Quote:
Originally Posted by MatWur-S530113 View Post
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.
bsquared is offline   Reply With Quote
Old 2009-01-22, 20:07   #4
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by bsquared View Post
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?
10metreh is offline   Reply With Quote
Old 2009-01-22, 20:36   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×5×587 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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
henryzz is offline   Reply With Quote
Old 2009-01-22, 20:38   #6
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
10metreh is offline   Reply With Quote
Old 2009-01-22, 20:46   #7
MatWur-S530113
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

2·34 Posts
Default

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
MatWur-S530113 is offline   Reply With Quote
Old 2009-01-22, 21:03   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

7×491 Posts
Default

Quote:
Originally Posted by MatWur-S530113 View Post
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.
bsquared is offline   Reply With Quote
Old 2009-01-22, 22:44   #9
MatWur-S530113
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

2·34 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
MatWur-S530113 is offline   Reply With Quote
Old 2009-01-22, 23:10   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101011011012 Posts
Default

Quote:
Originally Posted by MatWur-S530113 View Post
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 View Post
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 View Post
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.
bsquared is offline   Reply With Quote
Old 2009-01-22, 23:24   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33·131 Posts
Default

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
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Thread for posting tiny primes 3.14159 Miscellaneous Math 947 2021-02-13 08:40
Factoring software for tiny Linux versions Rodrigo Software 19 2011-02-15 04:32
Tiny range request .... 555.1M petrw1 LMH > 100M 1 2010-07-13 15:35
"Connection to socket failed" error for about 24 hours jasong Factoring 2 2006-02-26 22:18
Tiny error on nfsnet pages. 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.