mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operazione Doppi Mersennes

Reply
 
Thread Tools
Old 2013-08-28, 07:29   #1
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2·283 Posts
Default 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
aketilander is offline   Reply With Quote
Old 2013-08-28, 10:46   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

Quote:
Originally Posted by aketilander View Post
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
LaurV is offline   Reply With Quote
Old 2013-08-28, 20:16   #3
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

2×19×61 Posts
Default

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
ixfd64 is offline   Reply With Quote
Old 2013-08-31, 17:20   #4
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

56610 Posts
Default

Quote:
Originally Posted by aketilander View Post
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 View Post
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 View Post
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 View Post
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
aketilander is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
search for MMM127 small factors? Orgasmic Troll Miscellaneous Math 7 2006-06-11 15:38

All times are UTC. The time now is 12:23.

Thu Nov 26 12:23:39 UTC 2020 up 77 days, 9:34, 4 users, load averages: 0.92, 1.34, 1.47

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.