Possible values for k (in Mersenne factors)

[James Heinrich]

Originally Posted by LaurV

It is very easy to see that, assuming we start with a k which is a multiple of 4, we do not need to test all k's, and we can "skip" some of them. If p is 1 (mod 4), we first skip 3, then skip 1. If p is 3 (mod 4), we first skip 1, then skip 3.

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.

[LaurV]

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.

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

Then, same as in the first case, we mark with gray the q's which are 3 or 5 (mod 8) (i.e. 3, 5, 11, 13, 19, 21 (mod 24)) and we mark in blue (just for clarity) values as 9, 15, etc whose gcd with 24 is 3, as they are not prime. Those all are "unwanted" and what is left (black) in the table, we can count. It is very easy to see that, assuming we start with a k which is a multiple of 12, we do not need to test all k's, and we can "skip" some of them. If p is 1 (mod 12), we first skip 3, then skip 5, then skip another 3, then skip 1 (read the first column). If p is 5 (mod 12), we skip to 3, 1, 3, 5.

Let's put this in a piece of pari 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;)));
}

Now let's see if we save something...

(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.

Well, as expected, instead of testing half of the values (two from 4), now we test only a third (4 from 12) for each possible p. The program is 33% faster.

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.

[LaurV]

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:

/* 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;)));
}

Remark that the program works only for p being 1 or 7 (mod 60), for the other you have to look into the table an fill the right vectors, otherwise the program still works, but is testing every k. That is the homework , and it should be easy done in few minutes if you understood the procedure. As a double check, adding all components of each vector v must give 60 (just in case you did not spot this already, as you cycle to 60 every time). And you better check my lines (and the table) too, it is late here and I might have made some mistakes...

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.

(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.

Well, this is indeed an improvement!

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

[James Heinrich]

Originally Posted by LaurV

You have to look for "conditional formatting" formula to see how I grayed the cells

Remark that the program works only for p being 1 or 7 (mod 60), for the other you have to look into the table an fill the right vectors, otherwise the program still works, but is testing every k. That is the homework , and it should be easy done in few minutes if you understood the procedure.

I see that. Unfortunately the GCD function is unknown in Excel 2003, so everything show there as blue. But fortunately Google's spreadsheet can read it fine, so I got what I needed. And I have done the homework (part 1):

/* 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;)));
}

Originally Posted by LaurV

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.

In my particular implementation I can bypass the overhead of the ifs and just define the step list directly into the generated PARI code.
I'm not sure how much of a speedup to expect going from 60 to 420, nor do I trust my newly-found knowledge enough to try it unassisted, but what you've given me here is very useful, thanks!

[science_man_88]

Originally Posted by James Heinrich

I see that. Unfortunately the GCD function is unknown in Excel 2003, so everything show there as blue. But fortunately Google's spreadsheet can read it fine, so I got what I needed. And I have done the homework (part 1):

/* 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;)));
}

In my particular implementation I can bypass the overhead of the ifs and just define the step list directly into the generated PARI code.
I'm not sure how much of a speedup to expect going from 60 to 420, nor do I trust my newly-found knowledge enough to try it unassisted, but what you've given me here is very useful, thanks!

this code:

select(v->gcd(120,v)==1 && (v%8==7 || v%8==1),vector(120,n,n))

shows the values v<120 such that 120*u+v doesn't divide by a factor of 120 that also fit 1 or 7 mod 8, in earlier versions of Pari the argument order reverses. these are the values mod 120 which q can be to be prime and fit other arguments.

[LaurV]

Originally Posted by James Heinrich

Unfortunately the GCD function is unknown in Excel 2003,

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.

[James Heinrich]

Originally Posted by LaurV

The GCD function should be available from very early versions of Excel, but it come as a separate plugin.

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.

[ATH]

Originally Posted by James Heinrich

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 runtime-per-exponent beyond what I'm willing to invest for this purpose right now.

Why does it matter if it is not optimized for small runs, if it is still much faster? How long are you spending now getting candidates to k=20000? From your pari before it was 32sec for M4294949947?

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.

[James Heinrich]

Originally Posted by ATH

From your pari before it was 32sec for M4294949947?

No, that was for a 1000-run 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 (breadth-first 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.

[ATH]

Originally Posted by James Heinrich

No, that was for a 1000-run time trial. It would actually be 32ms.

Ok, then I understand it. It's still 50x slower per k but if you want a big range of exponents instead of a deep search then I understand.

Maybe you should make an array of p values from 1000M to 4000M (about 140million primes) and then loop k-values from 1 to 20,000 and for each fixed k, you sieve the p-array up to some low limit, before testing the 2kp+1 that survives the sieve.

[James Heinrich]

Originally Posted by ATH

Maybe you should make an array of p values from 1000M to 4000M (about 140million primes) and then loop k-values from 1 to 20,000 and for each fixed k, you sieve the p-array up to some low limit, before testing the 2kp+1 that survives the sieve.

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.