mersenneforum.org MMM127
 Register FAQ Search Today's Posts Mark Forums Read

 2013-08-28, 07:29 #1 aketilander     "Åke Tilander" Apr 2011 Sandviken, Sweden 2·283 Posts MMM127 This thread is intended for any discussion of any aspect of MMM127 The TF for MM127 is now at k=70*10^15. The probability of finding a factor is decreasing rapidly as the k:s grow bigger. The TF-work is enormous now just for the probability of 1% of finding a factor. Another way of proving that the Catalan-Mersenne-series does not generate an infinite number of primes would be to TF MMM127 = MM170141183460469231731687303715884105727. Well, if it is difficult to TF any of the double mersennes that presently, at this moment, are included in the project it would be so much more difficult with MMM127 of course. My question is though at which k for MM127 would it be equally probable of finding a factor of MMM127 for the smallest reasonable k to TF if the same amount of work is done? That is if we want to prove that the Catalan-Mersenne-series does not generate infinitely many primes at which point (k) would it be easier doing so by starting TF MMM127 instead of continuing TF MM127? Is it possible to estimate this? Another question: If both MM127 and MMM127 are composite is there any relation between the k:s of the smallest factor, that is must the k for the smallest factor of MM127 be smaller then the k for the smallest factor of MMM127? Last fiddled with by aketilander on 2013-08-28 at 07:32
2013-08-28, 10:46   #2
LaurV
Romulan Interpreter

Jun 2011
Thailand

22×7×11×29 Posts

Quote:
 Originally Posted by aketilander Another question: If both MM127 and MMM127 are composite is there any relation between the k:s of the smallest factor, that is must the k for the smallest factor of MM127 be smaller then the k for the smallest factor of MMM127?
Well, this is easy, if MM127=a*b, then 2^(a*b)-1 will be divisible by 2^a-1, 2^b-1, and if for example b is a factor of eulerphi(a) or viceversa, or if order(a)|(b-1) or viceversa, then it (MMM127) would be divisible by a^k or b^k, with k>=2. Also, regardless of this, all remaining factors of it will have the form 2*a*b*k+1, where each a and b are of the form 2*M127*k+1 (different k's, of course)

But these numbers are so big that are intangible...

For a good comparison look to, for example, M1081, and find the k of all known factors (yes, I mean 1081=23*47). For the C251 remaining factor of it, all factors must be 2*23*47*k+1. (Remember my request to Oliver to allow non-prime exponents in mfaktc, just to ask for confirmation, and not to exit with error, this will allow a guy who knows what is doing, to try to TF cases like this).

Last fiddled with by LaurV on 2013-08-28 at 10:55 Reason: links

 2013-08-28, 20:16 #3 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 2×19×61 Posts I may be wrong, but I believe a single trial division of MMM127 would require roughly the same computational complexity as an LL test of MM127. Last fiddled with by ixfd64 on 2013-08-28 at 20:25
2013-08-31, 17:20   #4
aketilander

"Åke Tilander"
Apr 2011
Sandviken, Sweden

56610 Posts

Quote:
 Originally Posted by aketilander My question is though at which k for MM127 would it be equally probable of finding a factor of MMM127 for the smallest reasonable k to TF if the same amount of work is done? That is if we want to prove that the Catalan-Mersenne-series does not generate infinitely many primes at which point (k) would it be easier doing so by starting TF MMM127 instead of continuing TF MM127? Is it possible to estimate this?
Quote:
 Originally Posted by ixfd64 I may be wrong, but I believe a single trial division of MMM127 would require roughly the same computational complexity as an LL test of MM127.
And then I found the excellent answer by LaurV:

Quote:
 Originally Posted by LaurV Doing a TF for a double mersenne, you have to compute $2^{2^p-1}-1$ mod $q=2*k*(2^p-1)+1$, which is equivalent to raise 2^(2^p) and check if this is 2 (mod q). This means you have to, in fact, take x=2, and square it p times, mod q. Many programs can do that, including P95, but the time involved would be the same amount of time as LL-ing Mp (is exactly the same type and amount of computation like a LL test, the modulus q has just few bits more then Mp, when we do mod Mp on a "clasic" LL test). i.e. to LL any Mp (the job we normally do for GIMPS), you start with s0=4 and do sn+1=sn2-2 (mod Mp), p-2 times otoh, to test if 2*k*Mp+1 divides MMp, you start with s0=2 and do sn+1=sn2 (mod 2*k*Mp+1), exactly p times (so there are two more iterations), and the mod is just few bits (for a small k) bigger then Mp (taking about the same time, in fact). The time will be the same like doing LL test for exponent p (about)
And the same could be applied to the "triple" MMM127 of course.

So the couclusion is that it will not be any reason doing one single TF of MMM127 until we have LLed MM127. And the breakevenpoint for that is around:

Quote:
 Originally Posted by aketilander If you ask the question: For how long would it be rational to continue TF instead of doing a LL when the double mersennes are concerned? The simple answer is "for ever", but if we insist and want to have an estimate of how long this "for ever" is we could extrapolate the breakeven points used by prime95. There would be so many IFs included in doing something like that so I simply omit all of them. When I do a simple extrapolation then I get the following breakeven points: MM61 173 bits (k = 2^111 = 2.6 E33) MM89 254 bits (k = 2^164 = 2.3 E49) MM107 307 bits (k = 2^199 = 8.0 E59) MM127 365 bits (k = 2^237 = 2.2 E71) i.e for MM127 it would be better to continue trial factoring until factors of the size 365 bits which equals a k-value of 2.2*10^71. For a Billion digit Mersenne the breakeven point would be 86 bits and for a 10Billion it would be 96 bits using the same way of extrapolating.

Last fiddled with by aketilander on 2013-08-31 at 17:20