Error: tiny factoring failed

[MatWur-S530113]

Hello,

first @ Ben: I think I understand now. The 28 digit threshold size is already working for P-1 and ECM, because normally the QS factors such small numbers in ms.

@Jason&Ben: from the sight of a user a built-in function is a function, which only needs the program.exe to run, thus I'm satisfied with my version of msieve and I don't need (and want) to compile msieve for myself. And, as I use the Alpertron for numbers up to 60 digit, I never got this fault by myself (with exception of this test). But thanks for the information, it's always very interesting to read about such internals.

@10metreh: as Jason finally said, the fault is known and in the QS-library. I don't understand enough from programming with C++ or the QS to look at it, but I want to give you some morality support: Yes, we need a proggy to fully factor a number (hm... up to 70, maybe 80 digit or so). maybe we can instigate/inspire/animate someone, who knows enough about it, to have a look at it and maybe correct this fault in the QS

best regards,

Matthias

[bsquared]

Originally Posted by MatWur-S530113

Yes, we need a proggy to fully factor a number (hm... up to 70, maybe 80 digit or so). maybe we can instigate/inspire/animate someone, who knows enough about it, to have a look at it and maybe correct this fault in the QS

best regards,

Matthias

Msieve is such a program. Except, as we have seen, in the very rare instance where it fails for a number of inconsequential size, it can factor any number to 80 digits and well beyond.

I've looked at the code and haven't been able to find the problem, although I suspect its in the linear algebra (block gaussian) because I've had similar problem with my own code.

You could also check out Yafu (shameless plug ). There's a thread about it in the factoring forum. It implements P-1, P+1, and ECM natively as well as SIQS and worked fine for the C26 in this thread.

- ben.

[MatWur-S530113]

Originally Posted by bsquared

Msieve is such a program. Except, as we have seen, in the very rare instance where it fails for a number of inconsequential size, it can factor any number to 80 digits and well beyond.

I know. I already factored a 118 digit number with msieve's MPQS and atm I try to factor a number (only 104 digits) using the nfs in msieve for the first time. As I'm said, I'm very satisfied with my version
The 80 digit I use here is only because I run GMP-ECM on numbers 80+digit before sieving them out.

Originally Posted by bsquared

I've looked at the code and haven't been able to find the problem, although I suspect its in the linear algebra (block gaussian) because I've had similar problem with my own code.

That's nice (...that you have looked at the code, not that you have found nothing). One more reason for anotherone with enough knowledge to have a look at it.

Originally Posted by bsquared

You could also check out Yafu (shameless plug ). There's a thread about it in the factoring forum. It implements P-1, P+1, and ECM natively as well as SIQS and worked fine for the C26 in this thread.

- ben.

As I said, I use the Alpertron for small numbers. And 10metreh's problem is, that he wants *one* proggy for *all* numbers (that's why I haven't suggestet him to use the Alpertron for small numbers like I do). I don't know if Yafu is as good as msieve for numbers with 80-120 digits. If not he still have to use more than 1 proggy to factor all numbers (up to this limit of digits). As he said, this (little) error prevents msieve atm to be *the* factoring proggy to fully factor numbers up to 120 digit. And we are simply sad about this.
But I by myself will give Yafu a try. Just for fun and testing.

best regards,

Matthias

[Random Poster]

Originally Posted by 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.

I don't think this is such a big problem. If ECM finds a composite factor m (whether it's the entire number to be factored or not), then there's an elliptic curve E, a point P on E, and an integer k such that kP is the identity of E modulo every prime factor of m. With these known, there's a simple algorithm to factor m:

1. If k is prime, then P has the exact same order modulo every prime factor of m (which is unlikely). In that case, choose a different point and start over.
2. Since now k is composite, find a prime factor q of k (easy, since k is chosen to be smooth) and let r=k/q.
3. If rP is the identity of E modulo every prime factor of m, replace k with r and go back to step 1.
4. If rP is not the identity of E modulo any prime factor of m, replace k with r and P with qP, and go back to step 1.
5. Now rP must be the identity of E modulo some but not all prime factors of m, which means that m is split into two proper factors. If one of these is still composite, replace m by this factor and go back to step 3. (If the other factor is also composite, store the variables while working on the first one.)

I have no idea if this is actually worth implementing, though.

[10metreh]

Originally Posted by MatWur-S530113

I know. I already factored a 118 digit number with msieve's MPQS and atm I try to factor a number (only 104 digits) using the nfs in msieve for the first time. As I'm said, I'm very satisfied with my version
The 80 digit I use here is only because I run GMP-ECM on numbers 80+digit before sieving them out.



That's nice (...that you have looked at the code, not that you have found nothing). One more reason for anotherone with enough knowledge to have a look at it.



As I said, I use the Alpertron for small numbers. And 10metreh's problem is, that he wants *one* proggy for *all* numbers (that's why I haven't suggestet him to use the Alpertron for small numbers like I do). I don't know if Yafu is as good as msieve for numbers with 80-120 digits. If not he still have to use more than 1 proggy to factor all numbers (up to this limit of digits). As he said, this (little) error prevents msieve atm to be *the* factoring proggy to fully factor numbers up to 120 digit. And we are simply sad about this.
But I by myself will give Yafu a try. Just for fun and testing.

best regards,

Matthias

I just happened to be off the internet at that point in time - otherwise I would have used the Alpertron anyway. I think it's an excellent applet. The only problem is that its QS is so slow - 7 mins for a C61.

Exactly how rare is this error? What percentage of C26s with no small factors will fail?

[jasonp]

Originally Posted by 10metreh

Exactly how rare is this error? What percentage of C26s with no small factors will fail?

About 1 in 1000, if experience is any guide. The tiny QS code also only finds 16 dependencies, so even without the bug you would very occaisionally get a failure to work.

Guys, it isn't like msieve is protecting your bank balance or anything.

[schickel]

Originally Posted by jasonp

About 1 in 1000, if experience is any guide. The tiny QS code also only finds 16 dependencies, so even without the bug you would very occaisionally get a failure to work.

Guys, it isn't like msieve is protecting your bank balance or anything.

Like I said, it keeps life interesting.

You've sure come a long way with msieve from the start, Jason.

Keep up the great work!

[10metreh]

Originally Posted by schickel

Like I said, it keeps life interesting.

You've sure come a long way with msieve from the start, Jason.

Keep up the great work!

What I find amazing about msieve is that there are so many error messages somewhere in the code. Someone could search the code for previously unseen messages.

[jasonp]

Originally Posted by 10metreh

Someone could search the code for previously unseen messages.

You can also find the input that will start the hidden flight simulator :)

[Jeff Gilchrist]

Originally Posted by jasonp

You can also find the input that will start the hidden flight simulator :)

Which is very useful now that Microsoft has dumped the company that produces MS FlightSim.

[10metreh]

Originally Posted by jasonp

You can also find the input that will start the hidden flight simulator :)

Is there really a hidden flight simulator? Does the input look random?