mersenneforum.org Sieving freakishly big MMs (was "World record" phone number?)
 Register FAQ Search Today's Posts Mark Forums Read

2012-09-24, 13:43   #23
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2012-09-24 at 13:44

2012-09-24, 13:55   #24
axn

Jun 2003

153D16 Posts

Quote:
 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 = ?

2012-09-24, 13:56   #25
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2012-09-24 at 13:58

2012-09-25, 04:35   #26
gd_barnes

"Gary"
May 2007
Overland Park, KS

52×11×43 Posts

Quote:
 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.

 2012-09-25, 05:11 #27 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 1006010 Posts Factors of (any) Mp cannot be 3 or 5 (mod 8). The rest follows.
2012-09-25, 06:00   #28
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3×23×149 Posts

Quote:
 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.

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

Last fiddled with by LaurV on 2012-09-25 at 06:42

 2012-09-25, 09:42 #29 gd_barnes     "Gary" May 2007 Overland Park, KS 1182510 Posts 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.
 2012-09-26, 07:28 #30 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 3×23×149 Posts 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). Last fiddled with by LaurV on 2012-09-26 at 08:19
2012-09-26, 07:37   #31
axn

Jun 2003

153D16 Posts

Quote:
 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)

Last fiddled with by axn on 2012-09-26 at 07:38

2012-09-26, 08:16   #32
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

101000001010012 Posts

Quote:
 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"

 2012-09-26, 08:41 #33 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100111010011002 Posts Don't die laughing. Promise? Ok. 15*2^43112611-59 completed P-1, B1=150000, B2=3000000, We4: 5B5B93C9

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55 LaurV Hobbies 74 2018-07-11 19:33 Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19 outlnder Soap Box 20 2005-02-03 09:30 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 10:13.

Sat Feb 4 10:13:46 UTC 2023 up 170 days, 7:42, 1 user, load averages: 1.10, 1.23, 1.21