MMM127

[aketilander]

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?

[LaurV]

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

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

[aketilander]

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?

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:

Originally Posted by LaurV

Doing a TF for a double mersenne, you have to compute mod , 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 M_p (the job we normally do for GIMPS), you start with s₀=4 and do s_n+1=s_n²-2 (mod M_p), p-2 times

otoh, to test if 2*k*M_p+1 divides MM_p, you start with s₀=2 and do s_n+1=s_n² (mod 2*k*M_p+1), exactly p times (so there are two more iterations), and the mod is just few bits (for a small k) bigger then M_p (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:

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.