20121121, 19:35  #23  
"James Heinrich"
May 2004
exNorthern Ontario
3^{2}·19·23 Posts 
Quote:


20121121, 20:17  #24 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
oh I see now I forgot that != was not equals , you are correct. now you can use other knowledge to maybe get it down further.
Last fiddled with by science_man_88 on 20121121 at 20:24 
20121121, 21:18  #25  
"James Heinrich"
May 2004
exNorthern Ontario
111101011101_{2} Posts 
Quote:
Code:
forstep(k=20000,99999,[1,3], Code:
forstep(k=19999,99999,[1,1,2], Code:
if(k%4==2,k++); 

20121121, 21:34  #26  
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Quote:


20121121, 21:58  #27  
"James Heinrich"
May 2004
exNorthern Ontario
3^{2}×19×23 Posts 
Quote:
Code:
// This shows us that if (p mod 4) == 1, then k must equal 0 or 3 (modulo 4). p=4294899893; forstep(k=10000, 19999, [3,1], q=2*k*p+1; if((q%8==1q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;)); // and if (p mod 4) == 3, then k must equal 0 or 1 (modulo 4). p=4294949947; forstep(k=10000, 19999, [1,3], q=2*k*p+1; if((q%8==1q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;)); 

20121121, 22:04  #28  
"Forget I exist"
Jul 2009
Dartmouth NS
20E2_{16} Posts 
Quote:
Last fiddled with by science_man_88 on 20121121 at 22:11 

20121122, 09:52  #29 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10246_{10} Posts 
@James, a side question, as I am sure you are reading this thread: are you still working on those P1 assignments on 2M range which are about 40 days overdue? I can see them in the team assignments and I just want to make sure is not some old forgotten task, you may have deleted the worktodo or whatever. [edit: there are also in 1M range about 20 assignments totally, pretty old, that i7920 should finish everything in onetwo days or so]
Last fiddled with by LaurV on 20121122 at 09:55 
20121122, 12:16  #30  
Einyen
Dec 2003
Denmark
D57_{16} Posts 
Quote:
To speed up you need to trial factor the candidate factors 2kp+1 and only try those that survives. You can make a binary array of kvalues up to some limit say 1e6 or 1e8, and then sieve them up to some limit. For each sieveprime you find the lowest kvalue where 2kp+1 = 0 (mod sieveprime) using Extended Euclidean algorithm. Here the input is your exponent p and your current sieveprime and output is that lowest kvalue where sieveprime is a factor of 2kp+1. Now you can remove all these values from your karray: k, k+2p, k+4p, k+6p ... since they all have the factor: sieveprime. You run this for all sieveprime up to some limit maybe 10^4 or 10^5 and then you can trial factor 2kp+1 in Mp for the remaining kvalues in your array. a, b, x, y, lastx, lasty, tempx, tempy, quot, rem are all temporary variables. Code:
a=p; b=sieveprime; lastx=1; lasty=0; x=0; y=1; if (a%b!=0) { do { quot=a/b; rem=a%b; tempx=lastxquot*x; tempy=lastyquot*y; a=b; b=rem; lastx=x; lasty=y; x=tempx; y=tempy; } while(rem!=1); x=0x; if (x<0) { x=x+sieveprime; } if ((x%2)==1) { x=x+sieveprime; } k=x/2; } 

20121122, 14:32  #31 
Einyen
Dec 2003
Denmark
D57_{16} Posts 

20121122, 15:27  #32  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2806_{16} Posts 
Quote:
Trial factoring, part 1 of 3 (stating the obvious) We take advantage of the fact that (1) p is prime, and (2) q is prime, and (3) q is 1 or 1 mod 8, and (4) q=2kp+1. The rest is filtering. If q is 1 or 7 (mod 8), then 2kp must be 0 or 6 (mod 8), so k*p must be 0 or 3 (mod 4). From the fact that p is prime, we have that p is 1 or 3 (mod 4), as it can't be even number. If p is 1 mod 4, then k can only be 0 or 3 mod 4, and if p is 3 mod 4, then k can only be 0 or 1 mod 4, otherwise the condition (3) fails. Let's put this discussion in a table, with a column for each possible p, and a line for each possible k, where the cells in the table are the modularity of q=2kp to 8. For example, if p=1 and k=2 (mod 4), then q=2*(4x+2)*(4y+1)=32xy+8x+16y+5, so q=5 (mod 8). Let's put his in the table, in excel is very simple. Code:
1 3 0 1 1 1 3 7 2 5 5 3 7 3 Let's put this in a piece of pari code: Code:
/* splitting p in two classes p must be a prime and fromk must be 0 (mod 4), no verification done, for speed reasons*/ tf_2c(p,fromk=0,tok=10000)= { if(p%4==1,v=[3,1], if(p%4==3,v=[1,3], error("p must be odd (prime)"))); forstep(k=fromk, tok, v, q=2*k*p+1; if(Mod(2,q)^p==1, if(q>1,print("M"p" has a factor: "q); break;))); } Last fiddled with by LaurV on 20121122 at 16:03 

20121122, 15:32  #33  
"James Heinrich"
May 2004
exNorthern Ontario
3^{2}·19·23 Posts 
Quote:
I played briefly with mfactor at your suggestion, but (like most TF programs) it's not optimized for such small runs and the overhead of (initializing each run, checking for savefiles, etc) make the runtimeperexponent beyond what I'm willing to invest for this purpose right now. Naturally I'm also running mfaktc, but it's horriblyinefficient on short runtimes (e.g. 5 seconds per candidate), so assuming 10 seconds per 3 candidates, it'll take me (or someone) about 10 years to get through the entire range up to somewhere around 2^66. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Distribution of Mersenne Factors  tapion64  Miscellaneous Math  21  20140418 21:02 
Known Mersenne factors  CRGreathouse  Math  5  20130614 11:44 
A strange new (?) fact about Mersenne factors  ChriS  Math  14  20060412 17:36 
Factors of Mersenne Numbers  asdf  Math  17  20040724 14:00 
Factors of Mersenne numbers ?  Fusion_power  Math  13  20031028 20:52 