Does a large P-1 test eliminate need for ECM tests

[UberNumberGeek]

1061 is the lowest remaining exponent with no known factors. As of 2009-04-01 15:56:55 utc it has had 41,089 out of 112,000 ECM curves with B1=260,000,000 tested. However, the exponent status page for 1061 (http://v5www.mersenne.org/report_exp...&B1=Get+status ) shows a P-1 test with B1=60000000000, B2=120000000000. This same page also shows 11 P-1 tests with B1=4.5e+010, B2=4.5e+012.

Do these P-1 tests negate the need to finish the remaining 71,000 B1=260,000,000 curves? Would "pitching in" to help complete those remaining curves be a "waste of time", or does, as R. D. Silverman posted on http://mersenneforum.org/showthread.php?t=5752 at 18 Apr 06, 05:13 PM, "Running P-1 is equivalent to running ECM with just a SINGLE curve. P-1 runs a lot faster than ECM, which is why it is worthwhile" mean the remaining ECM curves still have a chance of finding the factor?

I have read over a dozen posts attempting to answer this on my own, and I believe Dr. Silverman's statement is confirmed, but I would like to be certain that I am not wasting cycles attempting to find a factor for 1061 using ECM if those P-1 tests mentioned above have already surpassed what the ECM B1=260,000,000 range can find.

I thank all of you impressive geniuses and fellow math fanatics in advance, and I am grateful to you for the opportunity to be a part of this phenominal effort and to learn from you all.

[10metreh]

Originally Posted by UberNumberGeek

1061 is the lowest remaining exponent with no known factors. As of 2009-04-01 15:56:55 utc it has had 41,089 out of 112,000 ECM curves with B1=260,000,000 tested. However, the exponent status page for 1061 (http://v5www.mersenne.org/report_exp...&B1=Get+status ) shows a P-1 test with B1=60000000000, B2=120000000000. This same page also shows 11 P-1 tests with B1=4.5e+010, B2=4.5e+012.

Do these P-1 tests negate the need to finish the remaining 71,000 B1=260,000,000 curves? Would "pitching in" to help complete those remaining curves be a "waste of time", or does, as R. D. Silverman posted on http://mersenneforum.org/showthread.php?t=5752 at 18 Apr 06, 05:13 PM, "Running P-1 is equivalent to running ECM with just a SINGLE curve. P-1 runs a lot faster than ECM, which is why it is worthwhile" mean the remaining ECM curves still have a chance of finding the factor?

I have read over a dozen posts attempting to answer this on my own, and I believe Dr. Silverman's statement is confirmed, but I would like to be certain that I am not wasting cycles attempting to find a factor for 1061 using ECM if those P-1 tests mentioned above have already surpassed what the ECM B1=260,000,000 range can find.

I thank all of you impressive geniuses and fellow math fanatics in advance, and I am grateful to you for the opportunity to be a part of this phenominal effort and to learn from you all.

P-1 finds a factor P when P-1's second highest prime factor is below B1 and its highest prime factor is below B2. However, ECM can find other factors as well. The P-1 does not negate the need for the remaining 71000 curves because, at the 60 digit level, most possible factors just couldn't be found with the P-1 that has been done so far, neither could they be found with additional P-1 given the hardware ATM. However, P-1 has the potential to find much larger factors than ECM, and it can be worthwhile.

Oh, one last thing - with P-1, different B1s don't correspond with different factor sizes, like ECM.

Oh, seems that wasn't the last thing - with P-1 you don't have to run many times, like ECM. One run should suffice if the factor fits to the bounds.

BTW I'd be surprised if the P-1 that has been run on M1061 is only B1=6e10, B2=12e10. Firstly, that B2 is way too small for that B1, and secondly, I would have expected someone like Alex Kruppa to have run much more than that.

[fivemack]

The P-1 test works if the particular prime factor that the number has is such that p-1 has all but one of its factors less than 60000000000 and the other one less than 120000000000.

The ECM test works if *some number* has all but one of its factors less than 260000000 and the other one less than 3178559884516; but each trial picks a *different* 'some number', and you get the factorisation if any of them happen to have this property.

So they are testing different things; if the p-1 had found a factor there'd be no point in running ECM, but since it didn't then you can run ECM if you want.

It is very likely that 2^1061-1 has no factors accessible to ECM, and should be done by SNFS; however, doing it by SNFS would require a fair amount of software development that hasn't been done yet, about a thousand years of sieving on machines with 4GB memory per CPU and an uninterrupted month on a $100,000 computer cluster to finish the job.

[10metreh]

Originally Posted by fivemack

It is very likely that 2^1061-1 has no factors accessible to ECM, and should be done by SNFS; however, doing it by SNFS would require a fair amount of software development that hasn't been done yet, about a thousand years of sieving on machines with 4GB memory per CPU and an uninterrupted month on a $100,000 computer cluster to finish the job.

And there's the problem that it might need t70 run on it first. (And we're only a third of the way through t60. Come on guys, speed up! What would you think if ages are spent doing SNFS on it and a P60 pops up?)

[UberNumberGeek]

10metreh, I thank you for your immediate reply and for doing so in a manner which I could FINALLY understand completely! I am in your debt.

I have attempted to understand P-1 and ECM via the Wiki and many Forum posts, but sadly it is way above my head. I understand they are similar yet different forms for finding factors (quadruple-"f" alliteration score), hopefully my confusion is understandable to geniuses such as yourself.

If I might trouble you with a related follow-up: does running more than 3 ECM curves increase the chance of finding a factor, or does setting my worktodo.ini to run, say, 59 curves, only get us all 59 curves closer to the 112,000 curve finish in one lump?

[10metreh]

Originally Posted by UberNumberGeek

10metreh, I thank you for your immediate reply and for doing so in a manner which I could FINALLY understand completely! I am in your debt.

I have attempted to understand P-1 and ECM via the Wiki and many Forum posts, but sadly it is way above my head. I understand they are similar yet different forms for finding factors (quadruple-"f" alliteration score), hopefully my confusion is understandable to geniuses such as yourself.

If I might trouble you with a related follow-up: does running more than 3 ECM curves increase the chance of finding a factor, or does setting my worktodo.ini to run, say, 59 curves, only get us all 59 curves closer to the 112,000 curve finish in one lump?

The more curves you run, the higher chance there is of a factor being found , but curves take so long at 260M that it is hard to do many. However, every little helps so have a go! And yes, 59 curves = 59 curves. Duplicated sigmas are rare, so the chances are each one fo the 59 will be different.

[UberNumberGeek]

I may need to lie down after receiving these posts which have removed so much confusion. Thank you both 10metreh and fivemack!

I by no means am trying to test your patience, but you both have used terms in your gracious replies to me that I have seen in other posts but not understood.

If I may:

For what does "SNFS" stand? Is that a similar undertaking to GIMPS or software comparable to Prime95?

Do you believe that the lowest factor for 1061 (and please, should I be using M(1061)?) lies above the t60 (t60 meaning 60-digit?) range? If so, is this beyond what Prime95's ECM can attempt? (Ah, I see that fivemack answered this, but I misread his post as "unlikely" rather than the actually posted "likely")

I did not state my 3 vs 59 curve question clearly enough, for which I do apologize. I suppose I was asking if running 59 curves had any sort of cummulative effect in that it may help Prime95 pick a better *some number* based upon the GCD and/or results of previous curves, perhaps "narrowing the scope" of the search. Would running more curves per line in the worktodo.ini possible lead to better results, or, because each curve is randomly-chosen, any given curve is just as likely as the next?

Finally, if all curves' sigmas are chosen randomly, how are they chosen, and why only 112,000 260M curves?

Again, sincere thanks to you both for the education.

[10metreh]

Originally Posted by UberNumberGeek

I may need to lie down after receiving these posts which have removed so much confusion. Thank you both 10metreh and fivemack!

I by no means am trying to test your patience, but you both have used terms in your gracious replies to me that I have seen in other posts but not understood.

If I may:

For what does "SNFS" stand? Is that a similar undertaking to GIMPS or software comparable to Prime95?

Do you believe that the lowest factor for 1061 (and please, should I be using M(1061)?) lies above the t60 (t60 meaning 60-digit?) range? If so, is this beyond what Prime95's ECM can attempt?

I did not state my 3 vs 59 curve question clearly enough, for which I do apologize. I suppose I was asking if running 59 curves had any sort of cummulative effect in that it may help Prime95 pick a better *some number* based upon the GCD and/or results of previous curves, perhaps "narrowing the scope" of the search. Would running more curves per line in the worktodo.ini possible lead to better results, or, because each curve is randomly-chosen, any given curve is just as likely as the next?

Finally, if all curves' sigmas are chosen randomly, how are they chosen, and why only 112,000 260M curves?

Again, sincere thanks to you both for the education.

SNFS stands for "special number field sieve". It is completely different to ECM and P-1 in that it always completes the factorization of the number, but it needs a certain amount of work to be able to do this. SNFS is best for numbers of a special form, so M1061 (and the smaller M877) are candidates. The program most commonly used to do SNFS is called GGNFS.

Every curve is just as likely as the every other curve to find a factor.

It's only a certain number of curves at 260M because once you have run enough curves, you've probably eliminated all 60-digit factors. After that, you go on to 850M for 65-digit factors. Different B1s are optimal for different factor sizes with ECM. A single curve at 260M would probably remove all 20-digit factors, but 74 curves at 11K is so much faster!

About random sigmas: there are several random (or rather pseudo-random) number generation algorithms around, one of which is used in Prime95. I don't know exactly how it works.

And a tip: GMP-ECM is faster in stage 2 than Prime95, I think there are a few programs around that automate this. I'm not sure where they are though. You can get GMP-ECM binaries from places like gilchrist.ca/jeff/factoring/.

t60 means that there is a 1-1/e chance that there are no undiscovered factors <= 60 digits.

[UberNumberGeek]

Originally Posted by 10metreh

It's only a certain number of curves at 260M because once you have run enough curves, you've probably eliminated all 60-digit factors. After that, you go on to 850M for 65-digit factors. Different B1s are optimal for different factor sizes with ECM. A single curve at 260M would probably remove all 20-digit factors, but 74 curves at 11K is so much faster!

Hence the "man and wife under the umbrella" example given in the Wiki, brilliant!

Slight change in topic: is there a way to compare which would finish faster, a larger exponent with a small ECM curve vs a smaller exponent with a large ECM curve? (other than putting 120293 at 3 50K curves and 1061 at 3 260M curves into my worktodo.ini) I was wondering if there was a performance correlation akin to the time larger FFT sizes cause larger exponents to take when LL-testing them.

[Andi47]

Originally Posted by 10metreh

BTW I'd be surprised if the P-1 that has been run on M1061 is only B1=6e10, B2=12e10. Firstly, that B2 is way too small for that B1, and secondly, I would have expected someone like Alex Kruppa to have run much more than that.

We did in spring 2008 (I did the B1, Alex did the B2): B1 = 103e10, B2 = 1e18 (I am not sure if he eventually extended that to B2=2e18)

[10metreh]

Originally Posted by UberNumberGeek

Hence the "man and wife under the umbrella" example given in the Wiki, brilliant!

Slight change in topic: is there a way to compare which would finish faster, a larger exponent with a small ECM curve vs a smaller exponent with a large ECM curve? (other than putting 120293 at 3 50K curves and 1061 at 3 260M curves into my worktodo.ini) I was wondering if there was a performance correlation akin to the time larger FFT sizes cause larger exponents to take when LL-testing them.

I don't know of any way of comparing which is faster without just running a curve of each. I think it depends on your processor too, if they are close. I would have thought that 3 50K curves on 120293 would be faster. (and you only need 214 of them to complete t25).

You'll have realised by now that larger numbers take longer to run curves on, like LL testing. One curve at 11e3 on (10^71-1)/9 took 0.28 seconds, but a curve with the same bounds on M1061 took 1.36 seconds. (And BTW, 10^71-1 has been factored, but the factors are too large to be found quickly with B1=11e3.)