mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-09-24, 13:43   #23
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by retina View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-09-24, 13:55   #24
axn
 
axn's Avatar
 
Jun 2003

19·271 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
so if my calcuations are correctly done
It isn't. You could've done a simple verification -- (2*185*7+1)%8 = ?
axn is offline   Reply With Quote
Old 2012-09-24, 13:56   #25
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by axn View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-09-25, 04:35   #26
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

2·5,261 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
gd_barnes is offline   Reply With Quote
Old 2012-09-25, 05:11   #27
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·3·797 Posts
Default

Factors of (any) Mp cannot be 3 or 5 (mod 8). The rest follows.
Batalov is offline   Reply With Quote
Old 2012-09-25, 06:00   #28
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24·13·47 Posts
Post

Quote:
Originally Posted by gd_barnes View Post
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
LaurV is offline   Reply With Quote
Old 2012-09-25, 09:42   #29
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

1052210 Posts
Default

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.
gd_barnes is offline   Reply With Quote
Old 2012-09-26, 07:28   #30
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24·13·47 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2012-09-26, 07:37   #31
axn
 
axn's Avatar
 
Jun 2003

120358 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
axn is offline   Reply With Quote
Old 2012-09-26, 08:16   #32
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

977610 Posts
Default

Quote:
Originally Posted by axn View Post
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"
LaurV is offline   Reply With Quote
Old 2012-09-26, 08:41   #33
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×797 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really. CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55
Official "World cup 2014/2018" teat LaurV Hobbies 74 2018-07-11 19:33
Problem E7 of Richard Guy's "Unsolved problems in number theory" Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19
Is the USA the "new" peacekeeper of the world?? outlnder Soap Box 20 2005-02-03 09:30
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 05:08.


Wed Oct 20 05:08:03 UTC 2021 up 88 days, 23:37, 0 users, load averages: 1.41, 1.29, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.