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

[UberNumberGeek]

Originally Posted by 10metreh

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).

I got the following results from checking the status of my Prime95 after adding the curves to my worktodo.ini:

3 curves of 1061 @ 260M in 137 min
3 curves of 1657 @ 110M in 77 min
3 curves of 2671 @ 44M in 44 min
3 curves of 10061 @ 11M in 49 min
3 curves of 14489 @ 3M in 25 min
3 curves of 47507 @ 250K in 9 min
3 curves of 120293@ 50K in 4 min

Thus, I could finish the remaining 126 curves of 50K for M(120293) in under 3 hours with my Intel Core2 6600 @ 2.40GHz and 2 GB RAM. If that is a "waste" of processing power, I rationalize it by the fact that finding a prime takes more than 20 days and has odds of more than 1:200K against, whereas running a curve takes mere minutes and has a much better chance of success. I also believe the "goal" of GIMPS has gone from finding the next prime to knowing as much about all Mersennes since Aug 2008. I am now way off topic.

[10metreh]

Originally Posted by UberNumberGeek

I got the following results from checking the status of my Prime95 after adding the curves to my worktodo.ini:

3 curves of 1061 @ 260M in 137 min
3 curves of 1657 @ 110M in 77 min
3 curves of 2671 @ 44M in 44 min
3 curves of 10061 @ 11M in 49 min
3 curves of 14489 @ 3M in 25 min
3 curves of 47507 @ 250K in 9 min
3 curves of 120293@ 50K in 4 min

Thus, I could finish the remaining 126 curves of 50K for M(120293) in under 3 hours with my Intel Core2 6600 @ 2.40GHz and 2 GB RAM. If that is a "waste" of processing power, I rationalize it by the fact that finding a prime takes more than 20 days and has odds of more than 1:200K against, whereas running a curve takes mere minutes and has a much better chance of success. I also believe the "goal" of GIMPS has gone from finding the next prime to knowing as much about all Mersennes since Aug 2008. I am now way off topic.

There are loads of Mersennes like M120293 that are in the same range and have not had t25, so if you do a lot of them, you should find quite a few factors. And that would put you one level above me, in a way - you would have found a new factor of a Mersenne number!

[R.D. Silverman]

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? (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.

Get hold of my joint paper with Sam Wagstaff
"A Practical Analysis of the Elliptic Curve Factoring Algorithm"

read it. It will answer your questions.

[UberNumberGeek]

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.

Originally Posted by Andi47

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)

I just went with what was available on M(1061)'s status page. The B2 should have been 6e12 if B1=6e10, correct?

If Andi47 and Alex ran the P-1 tests stated, it seems highly unlikely a factor for M(1061) will be found with, the comparably "tiny", ECM curves of 260M.

[10metreh]

Originally Posted by UberNumberGeek

I just went with what was available on M(1061)'s status page. The B2 should have been 6e12 if B1=6e10, correct?

If Andi47 and Alex ran the P-1 tests stated, it seems highly unlikely a factor for M(1061) will be found with, the comparably "tiny", ECM curves of 260M.

Remember I said that most 60-digit possible factors just couldn't be found with P-1 with current hardware. I also said that B1s in ECM and P-1 were not comparable. t60 is more likely to find a factor than the P-1 that has been done.

And with P-1, the optimal B2 is quite a way above what you would expect. With a B1 of 6e10, I would guess a B2 of ~1e16 would be optimal.

[UberNumberGeek]

Originally Posted by R.D. Silverman

Get hold of my joint paper with Sam Wagstaff
"A Practical Analysis of the Elliptic Curve Factoring Algorithm"

read it. It will answer your questions.

Sir, I will, and I am honored by your offering. Thank you for making my forthcoming education easily obtainable. Thank you also for not slaughtering me and my ignorant questions.

[UberNumberGeek]

Originally Posted by 10metreh

Remember I said that most 60-digit possible factors just couldn't be found with P-1 with current hardware. I also said that B1s in ECM and P-1 were not comparable. t60 is more likely to find a factor than the P-1 that has been done.

And with P-1, the optimal B2 is quite a way above what you would expect. With a B1 of 6e10, I would guess a B2 of ~1e16 would be optimal.

Again I show how little I know and that I have not paid appropriate attention to the teaching you gave me earlier as well as to that which I have learned from other posts. I do apologize.

I also went with the assumption that B2 = B1 times 100, which I have seen in many posts and in the Wiki.

Thank you for your patience and multiple explanations.

[R.D. Silverman]

Originally Posted by UberNumberGeek

Again I show how little I know and that I have not paid appropriate attention to the teaching you gave me earlier as well as to that which I have learned from other posts. I do apologize.

I also went with the assumption that B2 = B1 times 100, which I have seen in many posts and in the Wiki.

Thank you for your patience and multiple explanations.

B2 = B1 * 100 is a legacy assertion. It was once true based upon the
fastest ECM implementation at the time (back in the 1980's and early
90's; due to P. Montgomery).

Now, if one wants to OPTIMIZE the parameters using a convolution/FFT
based step 2, then B2 = B1^2 will maximize the per unit time probability
of success. Once, again, you need to read my paper to see the
analysis of why this is true.

[R.D. Silverman]

Originally Posted by UberNumberGeek

I just went with what was available on M(1061)'s status page. The B2 should have been 6e12 if B1=6e10, correct?

If Andi47 and Alex ran the P-1 tests stated, it seems highly unlikely a factor for M(1061) will be found with, the comparably "tiny", ECM curves of 260M.

(1) It is P-1 test (singular).
(2) Your second assertion is grossly false. Especially if you are reaching
your 'conclusion' by comparing the B1,B2 limits between P-1 and ECM.
ECM uses *multiple* curves.

Once more: READ MY PAPER

[akruppa]

Originally Posted by R.D. Silverman

Get hold of my joint paper with Sam Wagstaff
"A Practical Analysis of the Elliptic Curve Factoring Algorithm"

read it. It will answer your questions.

It won't do him a blind bit of good, not without learning some basics first. The standard recommendation "Crandall & Pomerance, Prime numbers" is the best I can think of to get a first idea of how P-1 and ECM work. They go into rather more detail on elliptic curve arithmetic than one really needs to understand how to use ECM, though.

What's a good text for elementary facts on smoothness probabilities, explaining stuff like Dickman's ρ(α) function, and that for a given p, B/ρ(log(p)/log(B)) has a minimum for some positive B?

Alex

[FactorEyes]

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.

In the spirit of this thread, I would like to add that I am working on a new implementation of Pollard rho which should be able to crack 2^1061-1 on a cluster which I am building in my garage. Using 65,536 CPUs, as well as careful ASM subroutines to take advantage of branch prediction at the hardware level, both P-1 and ECM will be rendered obsolete.