Possible values for k (in Mersenne factors)

[James Heinrich]

Originally Posted by science_man_88

just found a logic error 10000 is 0 mod 4 a class you don't want so the first number should be 10002 not 10000 sorry. it still should take about the same though.

I'm not sure I agree with you. I think 10002 (10002%4==2) is the one value I wouldn't want to use (going right back to the footnote in my first post). I can give you a bunch of examples of known factors with k=10000, 10001 or 10003 but none with k=10002.

[science_man_88]

Originally Posted by James Heinrich

I'm not sure I agree with you. I think 10002 (10002%4==2) is the one value I wouldn't want to use (going right back to the footnote in my first post). I can give you a bunch of examples of known factors with k=10000, 10001 or 10003 but none with k=10002.

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.

[James Heinrich]

Originally Posted by James Heinrich

However your forstep change did provide a 10% performance improvement, so that's a good start.

Actually I don't think this is useful. It's faster because it's skipping k values in a way I don't think it should be. If I change

forstep(k=20000,99999,[1,3],

to

forstep(k=19999,99999,[1,1,2],

it replicates the functionality of

if(k%4==2,k++);

but also negates the speed improvement.

[science_man_88]

Originally Posted by James Heinrich

Actually I don't think this is useful. It's faster because it's skipping k values in a way I don't think it should be. If I change

forstep(k=20000,99999,[1,3],

to

forstep(k=19999,99999,[1,1,2],

it replicates the functionality of

if(k%4==2,k++);

but also negates the speed improvement.

the jump values depend on the start value. since 10000 mod 4=0 we want 10000,10001,10004,10005, since 19999 is 3 mod 4 and we get 19999,20000,20001,20003, with the jumps which don't fit 0 or 1 mod 4 we can prove some of these not needed to be checked.

[James Heinrich]

Originally Posted by science_man_88

with the jumps which don't fit 0 or 1 mod 4 we can prove some of these not needed to be checked.

Going back to rcv's post #7 above I see where you're going with your jump values. [1,3] is appropriate for 4294949947 because it's mod4=3, but I would need to swap that to [3,1] if p%4==1, such as for 4294899893:

// 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==1||q%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==1||q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;));

[science_man_88]

Originally Posted by James Heinrich

Going back to rcv's post #7 above I see where you're going with your jump values. [1,3] is appropriate for 4294949947 because it's mod4=3, but I would need to swap that to [3,1] if p%4==1, such as for 4294899893:

// 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==1||q%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==1||q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;));

actually what I was talking about was that since jumping [1,3] repeatedly from 19999 doesn't come to all possible values of k that could lead to a prime q, it doesn't hit all possible factors, so it could miss some factors 19999%4=3 3+1 = 0 mod 4 0+3 = 3 mod 4 so this only hits 0 and 3 mod 4 we need to hit 0 and 1 mod 4 that means to get into the 1,3 we need to jump 2 once and only once first. we need a value that fits the criteria to work the easiest with a forstep any value only works easy with a normal for loop. even with 1,1,2 we get 3,0,1,... repeating mod 4 we test 3/4 values when with we could cut it down to 2/4 ( in fact using mod 120 we can get it as low as 32/120 maybe lower),

[LaurV]

@James, a side question, as I am sure you are reading this thread: are you still working on those P-1 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 i7-920 should finish everything in one-two days or so]

[ATH]

Originally Posted by James Heinrich

Going back to this thread after some time, I've been playing with my PARI code and trying to incorporate some of the ideas presented here

What is your goal? Do you want to trial factor large mersenne numbers? Then mfactor is pretty fast I think: http://www.mersenneforum.org/showthread.php?t=4939



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 k-values up to some limit say 1e6 or 1e8, and then sieve them up to some limit.

For each sieveprime you find the lowest k-value 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 k-value where sieveprime is a factor of 2kp+1. Now you can remove all these values from your k-array: 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 k-values in your array.


a, b, x, y, lastx, lasty, tempx, tempy, quot, rem are all temporary variables.

a=p; b=sieveprime; lastx=1; lasty=0; x=0; y=1;
if (a%b!=0)
{
	do
	{
		quot=a/b; rem=a%b;
		tempx=lastx-quot*x;
		tempy=lasty-quot*y;
		a=b; b=rem; lastx=x; lasty=y; x=tempx; y=tempy;
	} while(rem!=1);
	x=0-x;
	if (x<0) { x=x+sieveprime; }
	if ((x%2)==1) { x=x+sieveprime; }
	k=x/2;
}

[ATH]

Originally Posted by ATH

Now you can remove all these values from your k-array: k, k+2p, k+4p, k+6p ... since they all have the factor: sieveprime.

Sorry, this is not right, it's of course: k, k+sieveprime, k+2*sieveprime, k+3*sieveprime, .... which can be removed from the k-array.

[LaurV]

Originally Posted by James Heinrich

LaurV's nice description of primorial class filtering was unfortunately beyond my ability to translate into code.

Well, that is not complicate if you understand the process.

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.

       1    3
  0    1    1
  1    3    7  
  2    5    5
  3    7    3

Then we mark with gray the unacceptable q's. 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.

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

[James Heinrich]

Originally Posted by ATH

What is your goal? Do you want to trial factor large mersenne numbers? Then mfactor is pretty fast I think: http://www.mersenneforum.org/showthread.php?t=4939

Short-term goal is to continue my pre-factoring project for 1000M-4294M. I've previously taken the range up to k=20000 and eliminated 50-million of 150-million candidates. I know returns will diminish drastically, but my plan is now to continue this up to k=100000 and squeeze a few more factors out. There's just slightly over 100-million candidates, and so far I'm getting about 4.8% factor rate, so I expect roughly 5-million factors at the end of this run. Candidate processing rate with PARI is approximately 5 candidates per second (per core). At this rate it'll take about 40 days (at 100% CPU and 24h/day, neither of which will actually happen, so probably about 100 real days).

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.

Naturally I'm also running mfaktc, but it's horribly-inefficient 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.