Error: tiny factoring failed

[10metreh]

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:

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.

[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:

 
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

[bsquared]

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:

 
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.

[10metreh]

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?

[henryzz]

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

[10metreh]

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.

[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

[bsquared]

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.

[MatWur-S530113]

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

[bsquared]

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.

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.

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.

[jasonp]

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.