Sieving freakishly big MMs (was "World record" phone number?)

[science_man_88]

Originally Posted by retina

1. That you have a program that can calculate residues.

2. That Mp is not division by any number <=1000.

3. That your unformatted code forces me to scroll sideways (yuck!).

I reformatted it a bit just not perfectly

I used pari from the residues mod 8 that can be prime I get (7-1)/2 = 3; (5-1)/2 = 2;(3-1)/2 = 1 and (1-1)/2 = 4 mod 8

1,2,3,4 mod 8 = kp; p=7 mod 8, so k = 4,5,6,7 mod 8 185 = 1 mod 8 so if my calcuations are correctly done k=185 is ruled out.

[axn]

Originally Posted by science_man_88

so if my calcuations are correctly done

It isn't. You could've done a simple verification -- (2*185*7+1)%8 = ?

[science_man_88]

Originally Posted by axn

It isn't. You could've done a simple verification -- (2*185*7+1)%8 = ?

okay I see know it's 7 mod 8 just realized why doh.okay maybe not, I'm missing something clearly.

[gd_barnes]

Originally Posted by LaurV

In fact, as Mp is 3 mod 4, when looking for factors of MMp of the form q=2*k*Mp+1, we are interested only in k=0,1 (mod 4). So, k can only be 1,4,5,8,9,12,13,16,17, etc.

Can you explain why factors of MMp of the form q=2k*Mp+1 must be k=0,1 (mod 4) where Mp=M43112609 ?

I personally did some trial factoring on all k<=50 and could find no factor < 10M for k=30. k=6 also has a smallest factor of 198623. Those are just two examples where k=2,3 (mod 4) but the smallest factor is not trivial.

[Batalov]

Factors of (any) Mp cannot be 3 or 5 (mod 8). The rest follows.

[LaurV]

Originally Posted by gd_barnes

Can you explain why factors of MMp of the form q=2k*Mp+1 must be k=0,1 (mod 4) where Mp=M43112609 ?

You have (a) q=2kp+1 and either (b) q=8x+1 or (c) q=8x-1. Combining (a) and (b) gives q=2*(4z)*p+1 (i.e. k=0 mod 4) in all cases, regardless of p. Combining (a) and (c) can't be solved in general case, you have to split the two cases where p=1 (mod 4) or p=3 (mod 4). First gives k=3 (mod 4) and second gives k=1 (mod 4).

Therefore, factors of M(4z+3) are either 8kp+1 or 8kp+2p+1 (that is 2*(4x)*(4z+3)+1 or 2*(4x+1)*(4z+3)+1 with natural x).
Ex: M11 has factors 23 and 89, with k=1=4*0+1, and k=4=4*1 (renaming the right k). M43 has factors 431, 9719 and 2099863, with correspondent k: 5=4*1+1, 113=4*28+1, 24417=4*6104+1. The k's for such numbers can only be 1,4,5,8,9,12,13, etc.

Same, factors of M(4z+1) are either 8kp+1, or 8kp+6p+1 (that is 2*(4x)*(4z+1)+1 or 2*(4x+3)*(4z+1)+1 with natural x. Ex: M29 has factors 233, 1103 and 2089, with correspondent k's 4=4*1, 19=4*4+3, 36=4*9. M37 has factor 223 with k=3=4*0+3.

Other combinations give composite numbers or primes which are 3 or 5 mod 8, as Batalov said. Those can't be "prime factors" of Mp with prime p.

As Mp is always 3 mod 4, it follows that if Mp is prime, MMp may have only factors with k=1 or k=0 mod 4.

Remark also that the "plus" factors (the one of the form 1 mod 8) can be in any number, including zero, but the "minus" factors (the one being "-1" mod 8) must be in odd number, because Mp is 3 mod 4, and product of two numbers which are 3 (mod 4) is 1 (mod 4). So it can't be an "even" number of "minus" factors. This implies that if Mp is composite, then it has al least one proper factor of the "minus" type (whose k is either 1 or 3 mod 4, depending on p).

To filter (I can't say sieve, but very elementary) possible factors for MMp you can try this small pari function to get a better insight.

mmp47(k,startq,stopq)=
{
    p=43112609;
    until(q>stopq,
        if(k%4,k+=3,k++);
        cnt=0;
        q=startq-1;
        while(q<=stopq && 2*k*(Mod(2,q=nextprime(q++))^p-1)+1,
            if(q>cnt,printf("... %d ...%c",q,13);
            cnt=cnt+10^6)
        );
        print(k" : "q"                 ");
    );
    return(q<=stopq);
}

call it with "mmp47(0,0,10^10)" and wait... you can stop it with ctrl+c when it reaches 185, and restart it again with "mmp47(185,0,10^10)" to skip to the next value after 185 (which would be 188). Next "hump" is 201.

@sm88: I got your PM, I hope the explanations above satisfy you too. Also, 1G4=1.4*10^9 (from electronics, resistors with 1.27 kilo-ohms are marked 1k27, to save space on small PCBs, components, etc, generally the notation is used in physics, 3M5 means 3.5 mega, or 3500000, etc, like rounding where the "small amounts" are not interesting). The k=185 is tested to much higher values, you can use the code above but is slow, some guys tested it to 1T or so (I won't bet my life on it, take it like rumors only).

[gd_barnes]

Ah, I get it now. k==(0 or 1 mod 4) is a necessary requirement for a factor of MM43112609. It is not a necessary requirement for the form 2*k*M43112609+1 to be prime.

Based on this, can anyone find a factor of 2*30*M43112609+1 ? I trial factored it to f=~10M. This was the only k<50 that I could not find a factor for of this form. There's no particular reason that it is needed...I'm just curious.

[LaurV]

The k=30 has no factors to 20G8 (that is 2.08*10^10) (I let my little script running overnight in half a core).

If we consider all k's, then "humps" we get at k=54, 83, and another few, below 185. All tested and having no factors below about 3G (a bit more). Did not test them higher then k=185. Proving their primality would be impossible anyhow.

For k being 0 or 1 (mod 4) type (the "can be a factor of MMp" type), we have k=185, 201 (both tested to 10G) and 233 (2G55), 273 (2G),384 (2G55), and 513, 521, 560, 593, 656 (all tested to 1G) and few more which I don't remember right now. All k under 1000, for this k type, were tested to 1G.

From the "hard" category, there is only one harder then k=5, and that is k=216 who dies at 747M (2*216*Mp+1 is divisible by 747303643).

[axn]

Originally Posted by LaurV

Proving their primality would be impossible anyhow

On the contrary. It is pretty straightforward to apply a "N-1" test to these candidates. (Doing a PRP test is easier still - P95 can do it)

[LaurV]

Originally Posted by axn

On the contrary. It is pretty straightforward to apply a "N-1" test to these candidates. (Doing a PRP test is easier still - P95 can do it)

Sure, what I wanted to say was "testing them higher by this method of trial factoring will not prove their primality". After I read your post I see that it could be interpreted as "it is impossible to prove them prime by any method". Sorry for this, it was not intended. I always say that "nothing is impossible"

[Batalov]

Don't die laughing. Promise? Ok.
15*2^43112611-59 completed P-1, B1=150000, B2=3000000, We4: 5B5B93C9