mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2013-04-12, 23:06   #1
Aramis Wyler
 
Aramis Wyler's Avatar
 
"Bill Staffen"
Jan 2013
Pittsburgh, PA, USA

23·3·17 Posts
Default I am so sorry for being bad at math.

But I really did search the forums before asking, and read up on the relevant topics on the mersenne wiki and wikipedia.

I am trying to figure out why p-1 factorization is used over ECM for mersenne primes. Seems like ECM used to be a thing, and now it's not, and I don't know why.
Aramis Wyler is offline   Reply With Quote
Old 2013-04-12, 23:18   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts
Default

All the factors of 2^p-1 are of the form 2*k*p+1. This means in the p-1 method we get the factor p for free. This makes it much easier to find factors using p-1 than ecm for this form of number. I imagine one day when the exponents get large enough some ecm will be done in addition to p-1. We have probably got a long way to go before that happens though.
henryzz is offline   Reply With Quote
Old 2013-04-12, 23:28   #3
Aramis Wyler
 
Aramis Wyler's Avatar
 
"Bill Staffen"
Jan 2013
Pittsburgh, PA, USA

23·3·17 Posts
Default

Wow, that's crazy. I will work on that for a while, thanks much.
Aramis Wyler is offline   Reply With Quote
Old 2013-04-13, 03:34   #4
axn
 
axn's Avatar
 
Jun 2003

470910 Posts
Default

Quote:
Originally Posted by henryzz View Post
I imagine one day when the exponents get large enough some ecm will be done in addition to p-1.
Never gonna happen. As exponent grows larger, the TF level also goes higher. Thus useful ECM level also goes higher. It'll never breakeven. The handicap (not being able to leverage the p in 2kp+1) is too large (and getting larger).
axn is offline   Reply With Quote
Old 2013-04-13, 15:33   #5
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by Aramis Wyler View Post
But I really did search the forums before asking, and read up on the relevant topics on the mersenne wiki and wikipedia.

I am trying to figure out why p-1 factorization is used over ECM for mersenne primes. Seems like ECM used to be a thing, and now it's not, and I don't know why.
ECM is still most definitely a thing.

ECM is used on Mersenne numbers, but usually only on small exponents below about 10,000,000. See this page. These are already known to be composite, and in some cases a factor is known. Finding (additional) factors, not primality testing is the goal here.

For larger exponents, finding factors is nice, but the main goal is finding primes. We search for factors in the hope that a small investment of computer time will save us from having to conduct two expensive LL tests. The law of diminishing returns applies to factor-finding - the deeper we search, the fewer factors each extra GHz-day is likely to find. Eventually we reach the break-even point at which the expected cost of finding a factor is equal to the cost of doing the LLs. At this point, we stop.

That break-even point, for ECM is none at all. Why? And why not for P-1? First P-1 is oveall a faster and less memory-hungry algorithm. Since P-1 will happily eat up all the memory I can throw at it - and I have 16GB - you can imagine how voracious ECM is. Second, as henryzz remarks above, P-1 can make use of the 2kp+1 form of Mersenne factors which means it will find factors about log2(p) bits larger than ECM would run to the same bounds. Finally, after we've already done TF and P-1, there just aren't enough small factors left to find.

If P-1 is so much better than ECM, you may be wondering why use ECM at all? The answer is that ECM can be run again and again with the same bounds on the same number, and still have a chance of finding a new factor, while P-1 can be run only once.
Mr. P-1 is offline   Reply With Quote
Old 2013-04-13, 18:01   #6
Aramis Wyler
 
Aramis Wyler's Avatar
 
"Bill Staffen"
Jan 2013
Pittsburgh, PA, USA

1100110002 Posts
Default

Thank you, that's very helpful. I would not have guessed that p-1 might be the 'less memory hungry' version of anything. :)

Last fiddled with by Aramis Wyler on 2013-04-13 at 18:01
Aramis Wyler is offline   Reply With Quote
Old 2013-04-13, 18:22   #7
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22×32×31 Posts
Default

At one level, P-1 and ECM are very similar: Both methods exploit group operations hoping to find a factor if the group order is smooth. Given a prime factor F, the group order in P-1 is fixed at F-1, and the group operation is multiplication mod F. In ECM, there are many group orders possible depending upon what curve is chosen, but the group orders are all in the range from F+1-2*sqrt(F) to F+1+2*sqrt(F), roughly the same size as F-1, so we would expect an a priori probability of any of these group orders to be smooth to be about the same. However, there are two considerations that make P-1 the more efficient method for eliminating LL candidates:

1) We know that the P-1 group order is divisible by 2p, where p is the Mersenne number exponent in question. ECM curves can be chosen so that the group order is divisible by either 12 or 16. Suppose trial factoring has already been done to 73 or so bits on a Mersenne number with a 26-bit exponent. Suppose that this number has a factor which is a little bit larger, say 80 bits. The group orders then are also 80 bit numbers, but since the P-1 group order is divisible by 2p, we find the factor when the cofactor of 80 - 27 = 53 bits is smooth to the factoring bounds. ECM only finds the factor when the cofactor of 80 - 4 = 76 bits is smooth, and the probability that a 76-bit factor is smooth is considerably less than for a 53-bit factor. Of course, if we really want to find that particular factor, and P-1 does not find it, we can run a number of ECM curves on the number, but in the context of GIMPS, it would be more efficient to move on and run P-1 on other numbers, eliminating more LL candidates in the long run.

2) The other advantage of P-1 is that the group operation, multiplication mod F, is straightforward and easy to implement. (Of course, we don't know F, so we do the multiplications mod 2p-1, but this also applies to ECM.) The group operation in ECM is more complicated, and requires about 6 times the amount of computations to perform one step than a step in P-1 takes. So one ECM curve to given factoring bounds should take about 6 times as long as a P-1 run to the same bounds.

I have oversimplified some details, but I hope this is sufficient to get across the general reason why ECM on LL candidates just is not as efficient as doing P-1, and doing P-1 to higher bounds will find more candidates in the long run than ECM.

Last fiddled with by philmoore on 2013-04-13 at 18:24
philmoore is offline   Reply With Quote
Old 2013-04-13, 18:49   #8
Aramis Wyler
 
Aramis Wyler's Avatar
 
"Bill Staffen"
Jan 2013
Pittsburgh, PA, USA

23·3·17 Posts
Default

This may not make sence, but knowing what numbers are going to be hit by p-1 stage 1, would it be a significant gain to sieve those numbers out of the TF test?
Aramis Wyler is offline   Reply With Quote
Old 2013-04-13, 21:01   #9
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22·32·31 Posts
Default

Ideally, all numbers should be hit by the P-1 test before LL testing. But it makes sense to TF them to a certain level before doing P-1. TF finds some factors that P-1 will miss, and conversely, P-1 will find some factors that TF will miss.
philmoore is offline   Reply With Quote
Old 2013-04-14, 15:45   #10
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

Quote:
Originally Posted by Aramis Wyler View Post
This may not make sence, but knowing what numbers are going to be hit by p-1 stage 1, would it be a significant gain to sieve those numbers out of the TF test?
To do that would effectively require the trial factorisation of q-1 for every candidate factor q of Mp. While this can indeed be done quickly using a sieve (it's how the quadratic sieve factoring algorithm works) it would still take far more time, and eliminate so few candidates, that the cost would exceed the benefit.
Mr. P-1 is offline   Reply With Quote
Old 2013-04-14, 16:06   #11
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

Quote:
Originally Posted by Aramis Wyler View Post
Thank you, that's very helpful. I would not have guessed that p-1 might be the 'less memory hungry' version of anything. :)
The implementation of P-1 in Prime95 is the less memory-hungry version of P-1. I once crashed my computer running gmp-ecm's version of P-1 without the -maxmem switch on a 250 digit number. I watched it gobble up memory until it blasted past 14GB, at which point I tried to kill it. Unfortunately I was too late. The system became unresponsive and I had to press the reset button.

Prime95, by contrast will comfortably run P-1 on 20-million-digit numbers using that much memory, and if pressed, could make do with just a few hundred Meg. The downside is that with Prime95, stage 2 typically takes longer than stage 1, while B2 is typically about 50 times B1. With gmp-ecm stage 2 is much faster than stage 1 despite B2 being tens of thousands times larger than B1.
Mr. P-1 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
need some math help. swl551 Math 2 2014-02-20 16:33
Math ET_ Operazione Doppi Mersennes 4 2012-09-20 19:33
Math JohnFullspeed Forum Feedback 1 2011-07-11 16:42
math help pls! DSC Miscellaneous Math 2 2005-09-11 04:53
help with math DSC Homework Help 13 2005-08-31 07:16

All times are UTC. The time now is 18:14.

Thu Oct 22 18:14:58 UTC 2020 up 42 days, 15:25, 2 users, load averages: 1.93, 2.29, 2.53

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.