20121122, 15:40  #34 
"James Heinrich"
May 2004
exNorthern Ontario
3,929 Posts 
Between rcv's post #7 and science_man_88's post #20, I actually (mostly) understand this part. And it's incorporated in my current PARI code quite nicely  the p%4 decision of [1,3] vs [3,1] is made in the PHP code that pulls the candidates out of the database and generates the PARI code.

20121122, 15:51  #35 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3·5·683 Posts 
Trial factoring, part 2 of 3
Let's introduce 3 into equation. Mod 12 (=4*3), a prime (our p) can only be 1, 5, 7, or 11. Otherwise is not prime. So, let's put this in the table, with all possible 12 classes of k (mod 12). Of course, the cells on the table will contain the modularity of q to 24. Code:
k\p 1 5 7 11 0 1 1 1 1 1 3 11 15 23 2 5 21 5 21 3 7 7 19 19 4 9 17 9 17 5 11 3 23 15 6 13 13 13 13 7 15 23 3 11 8 17 9 17 9 9 19 19 7 7 10 21 5 21 5 11 23 15 11 3 Let's put this in a piece of pari code: Code:
/* splitting p in 12 classes p must be a prime and fromk must be 0 (mod 12), no verification done, for speed reasons*/ tf_12c(p,fromk=0,tok=10000)= { if(p%12== 1,v=[3,5,3,1], if(p%12== 5,v=[3,1,3,5], if(p%12== 7,v=[5,3,1,3], if(p%12==11,v=[1,3,5,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;))); } Code:
(22:15:54) gp > \r tf (22:44:22) gp > tf_2c(11) M11 has a factor: 23 (22:44:34) gp > # timer = 1 (on) (22:44:36) gp > tf_2c(67) time = 3 ms. (22:44:42) gp > tf_2c(67,,10^10) M67 has a factor: 193707721 time = 604 ms. (22:44:53) gp > tf_2c(67,,10^10) M67 has a factor: 193707721 time = 599 ms. (22:44:56) gp > tf_12c(67,,10^10) M67 has a factor: 193707721 time = 412 ms. (22:45:02) gp > tf_12c(67,,10^10) M67 has a factor: 193707721 time = 396 ms. Next step is to put 5 into equation (60 classes), then 7 (420 classes), then 11 (4620 classes) and you have mfaktc. Excepting millions of optimization things I come later with part 3, 60 classes, let me have some sleep (here 23:00) and need few minutes to make the table in excel tomorrow. Last fiddled with by LaurV on 20121122 at 16:22 Reason: alignment of the table, still did not get it right, I hate when the forum changes my spacing 
20121122, 17:03  #36 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3×5×683 Posts 
Trial factoring, part 3 of 3
Let's introduce 5 into equation, as I said, mod 60 (=4*3*5), a prime (our p) can be 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59. Otherwise is not prime. Caution for 49, it is not prime, but its gcd with 60 is 1, so a prime CAN be 49 mod 60. Ex: 109, 229, 349, 409, etc. There are no other possibilities of reminders modulo 60 for a prime, all the other are divisible by either 2, 3, or 5, for p>5. The table is attached in excel form: 60classes.zip You have to look for "conditional formatting" formula to see how I grayed the cells (I did not do it by hand, I am nerd, but not SO NERD!). Remind that the cells are (mod 120) (as the q is k*p multiplied by 2), and that is where we get the modularity to 8 being 1 or 7. All numbers 3 or 5 (mod 8) were grayed, and all for which the gcd with 120 is bigger then 1. Caution, this lets into the table values like 49 or 119, even if they are not prime, but a prime can be 49 or 119 mod 120, because their gcd is 1. (same observation for 77, 91, but they are grayed because are 3,5 mod 8). Let's put this in a piece of pari code: Code:
/* splitting k in 60 classes p must be a prime>5 and fromk must be 0 (mod 60), no verification done, for speed reasons*/ tf_60c(p,fromk=0,tok=10000)= { if(p%60== 1, v=[3,5,3,4,5,3,1,11,1,3,5,4,3,5,3,1], if(p%60== 7, v=[5,3,1,3,5,3,4,5,3,1,11,1,3,5,4,3], if(p%60==11, v=[1], if(p%60==13, v=[1], if(p%60==17, v=[1], if(p%60==19, v=[1], if(p%60==23, v=[1], if(p%60==29, v=[1], if(p%60==31, v=[1], if(p%60==37, v=[1], if(p%60==41, v=[1], if(p%60==43, v=[1], if(p%60==47, v=[1], if(p%60==49, v=[1], if(p%60==53, v=[1], if(p%60==59, v=[1], 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;))); } Now let's see if we save something... as we are now testing only 16 values of k from 60, we should get the results much faster. Again, we select 67, as it is the most difficult to factor from p<100. Code:
(23:42:08) gp > \r tf (23:42:11) gp > # timer = 1 (on) (23:42:18) gp > tf_60c(67,,10^10) M67 has a factor: 193707721 time = 241 ms. Your homework now is to implement 420 classes (add 7) Honestly I don't think that adding 11 (4620 classes for k) would speed up more. Due to overhead of the ifs (there will be 960 ifs) it will be in fact slower. Mfaktc does SIEVING of each class of k, and you can't compare interpreted pari with compiled executable cuda... But anyhow, with a good implementation, as I said in the past many times, this pari will be very efficient in eliminating small factors of big exponents (like from a billion to 10^10, or to 2^32, outside of GIMPS ranges, what James is doing). Last fiddled with by LaurV on 20121122 at 17:23 
20121122, 20:22  #37  
"James Heinrich"
May 2004
exNorthern Ontario
3,929 Posts 
Quote:
Code:
/* splitting k in 60 classes p must be a prime>5 and fromk must be 0 (mod 60), no verification done, for speed reasons*/ tf_60c(p,fromk=0,tok=10000)= { if(p%60== 1, v=[3,5,3,4,5,3,1,11,1,3,5,4,3,5,3,1], if(p%60== 7, v=[5,3,1,3,5,3,4,5,3,1,11,1,3,5,4,3], if(p%60==11, v=[1,3,5,4,3,5,3,1,3,5,3,4,5,3,1,11], if(p%60==13, v=[3,5,3,1,3,5,3,4,5,3,1,11,1,3,5,4], if(p%60==17, v=[3,1,3,5,3,4,5,3,1,11,1,3,5,4,3,5], if(p%60==19, v=[5,4,3,5,3,1,3,5,3,4,5,3,1,11,1,3], if(p%60==23, v=[1,11,1,3,5,4,3,5,3,1,3,5,3,4,5,3], if(p%60==29, v=[4,3,5,3,1,3,5,3,4,5,3,1,11,1,3,5], if(p%60==31, v=[5,3,1,11,1,3,5,4,3,5,3,1,3,5,3,4], if(p%60==37, v=[3,5,4,3,5,3,1,3,5,3,4,5,3,1,11,1], if(p%60==41, v=[3,1,11,1,3,5,4,3,5,3,1,3,5,3,4,5], if(p%60==43, v=[5,3,4,5,3,1,11,1,3,5,4,3,5,3,1,3], if(p%60==47, v=[4,5,3,1,11,1,3,5,4,3,5,3,1,3,5,3], if(p%60==49, v=[11,1,3,5,4,3,5,3,1,3,5,3,4,5,3,1], if(p%60==53, v=[3,4,5,3,1,11,1,3,5,4,3,5,3,1,3,5], if(p%60==59, v=[1,3,5,3,4,5,3,1,11,1,3,5,4,3,5,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;))); } Quote:
I'm not sure how much of a speedup to expect going from 60 to 420, nor do I trust my newlyfound knowledge enough to try it unassisted, but what you've given me here is very useful, thanks! 

20121122, 20:50  #38  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
this code: Code:
select(v>gcd(120,v)==1 && (v%8==7  v%8==1),vector(120,n,n)) Last fiddled with by science_man_88 on 20121122 at 20:51 

20121123, 02:29  #39 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3·5·683 Posts 
The GCD function should be available from very early versions of Excel, but it come as a separate plugin. You have to install (from the Tools/AdIns menu I think, unfortunately I updated all Office's including at home and work, but you can google for "excel 2003 gcd" or so) the additional package tool for analysis and engineering.
edit: Got it! Click on the first "How" on the text. Last fiddled with by LaurV on 20121123 at 02:31 
20121123, 02:42  #40 
"James Heinrich"
May 2004
exNorthern Ontario
3929_{10} Posts 
Oh, yes, of course, silly me  I'd forgotten about that. Of course, my Office install CD is cleverly buried away in storage where I won't have access to it for the next year or so, so I'll have to make do without it.

20121124, 14:19  #41  
Einyen
Dec 2003
Denmark
5·683 Posts 
Quote:
I tested mfactor on the same exponent 4294949947: Trialfactor to 2^58 (k=33,554,567): 7 sec Trialfactor to 2^59 (k=67,109,135): 12 sec Trialfactor to 2^60 (K=134,218,270): 21 sec So it's several orders of magnitudes faster. Last fiddled with by ATH on 20121124 at 14:20 

20121124, 15:41  #42 
"James Heinrich"
May 2004
exNorthern Ontario
3,929 Posts 
No, that was for a 1000run time trial. It would actually be 32ms.
Practically I'm currently getting about 30 candidates per second across 6 cores, at about 4.5% factor rate (~1.3 factors per second) on 20000<k<100000 using PARI. Using mfaktc to TF to 2^65 (k=18,359,596,156 around 1004M) takes about 9 seconds per candidate per instance (running 3 instances), at around 25% success rate (sometimes multiple factors are found per candidate, but that doesn't affect the factor/nofactor success rate) means I get about one factor every 12 seconds using mfaktc. So while mfaktc is generally very much faster than CPU TF on a given range, and certainly even "fasterer" than equivalent PARI code to TF an exponent to (for example) 2^65, for my particular application (breadthfirst TF to very low bitlevels) it turns out that on my machine, PARI can actually clear 15x more candidates per time interval than mfatkc can. Note the diminishing returns, however  at even lower levels (e.g. 0<k<10000) it was closer to 100x, and going much above k=100000 will pull efficiency down to 1:1 with mfaktc. There's no point using this PARI approach in the PrimeNet range since TF has universally been done up to 2^65+ already. 
20121124, 18:06  #43  
Einyen
Dec 2003
Denmark
5×683 Posts 
Quote:
Maybe you should make an array of p values from 1000M to 4000M (about 140million primes) and then loop kvalues from 1 to 20,000 and for each fixed k, you sieve the parray up to some low limit, before testing the 2kp+1 that survives the sieve. 

20121124, 19:02  #44 
"James Heinrich"
May 2004
exNorthern Ontario
3,929 Posts 
Explain further, please? I'm currently using approximately the code in post #37 above, except that the generated PARI code has hardcoded jumplist based on p%60 instead of doing that check in PARI.

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 