Possible values for k (in Mersenne factors) - Page 2

science_man_88 · 2012-08-30, 16:32

Quote:

Originally Posted by ATH

Looking at the 16 possible values for q (mod 120) does not give any further restriction on k.

I can get what k*p is mod 120 from them, regardless of p but once p gets involved could it not figure it out ?

Edit:maybe it's because too many values can be prime mod 120.

rcv · 2012-08-30, 19:08

I think much of this thread is beyond the scope of James' question. I think the last 2 lines of my previous post and the first 5 lines of LaurV's post get to heart of James' question.

A lot of this thread is more about efficiency in hunting for factors than "plausibility". It isn't necessary to try candidates q=2kp+1 that are not prime, because if they are composite, their component factors are probably already known. 256999 (k=4431) is composite and is a factor of M(29). But we probably already knew that 233 (k=4) and 1103 (k=19) were factors of M(29). Most tf algorithms try to ensure q doesn't have any small prime factors before they undertake the divisibility test of M(p)/q.

@James: If you seek more than basic "plausibility", then I suggest you apply my plausibility test and *also* compute q=2kp+1. Then, depending on your application you can test q for primality (or probably primality) or you can trial factor q to some level of your choice. Are you "hunting" or "validating" values of k?

James Heinrich · 2012-08-30, 19:11

Quote:

Originally Posted by rcv

I think the last 2 lines of my previous post and the first 5 lines of LaurV's post get to heart of James' question.

Thanks, you are indeed correct. I appreciate all who responded (whether I really understood everything that was said or not

).

bloodIce · 2012-08-30, 19:43

Quote:

Originally Posted by LaurV

Only 960 classes survive the "filtering".

I wonder if there is only one factor in a class. Is there any way to check if there is one and only factor in each class. If that is true, then 1 class fells off, when a factor is found. If there are 8 or 9 known factors (such exponents are rear on this stage of the project), that will be additional ~1% filtering.

TheJudger · 2012-08-30, 22:46

Yes, it is possible. Those classes are artificial and are not directly related to mersenne numbers. They help to eleminate composite factor candidates (sieving) from the list more effecient.
You can freely choose the number of classes, but some numbers are "better" than others, e.g. with 4620 those classes remove all composite factor candidates which are a multiple of 3, 5, 7 or 11 and don't satisfy the q == 1 or 7 mod 8 rule. 960 classes survive (20.78%).
If you choose 4621 classes than 4620 classes survive (99.98%) because you can only eliminate factor candidates which are a multiple of 4621.

Oliver

science_man_88 · 2012-08-31, 00:53

Quote:

Originally Posted by James Heinrich

Thanks, you are indeed correct. I appreciate all who responded (whether I really understood everything that was said or not

).

I realize now basically all I was saying is: $q=2*k*p+1$ -> k= $<br /> (q-1)\over{(2*p)}$ and with properties of q and p we should be able to find properties of k. including modular properties.

science_man_88 · 2012-08-31, 13:26

Quote:

Originally Posted by science_man_88

I realize now basically all I was saying is: $q=2*k*p+1$ -> k= $<br /> (q-1)\over{(2*p)}$ and with properties of q and p we should be able to find properties of k. including modular properties.

I believe this goes to: k= ${q-1}\over{2*p}$ mod $\text {lcm(<modulus>,2*p)}\over{(2*p)}$

where <modulus> is the modulus used in the first section. and the modulus is used on 2*p in both sections.

James Heinrich · 2012-11-21, 15:36

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, but I'm unable to get it to run any faster than what I was originally using, which is just a "dumb" filter of skipping all k%4==2:

Code:

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(k%4==2,k++); 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;); k++;));
## = 31.913s

I tried some ideas, but (at least how I wrote it) it seems that the extra effort of checking whether a k-mod-something is allowed outweighs the benefit of filtering those values. Timings are based on 1000-iteration loop.

Code:

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, while(k%4!=0 && k%4!=1,k++); 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;); k++;));
## = 31.877s

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, 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;); k++;));
## = 32.168s

// on the assumption that 4294949947 % 4 == 3
for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(k%4==0||k%4==1,,k++); 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;); k++;));
## = 32.663s

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(((2*k*p+1)%6==1 || (2*k*p+1)%6==5) && ((2*k*p+1)%8==1 || (2*k*p+1)%8==7),,k++); q=2*k*p+1; if(lift(Mod(2,q)^p)==1, print("M"p" has a factor: "q); break;); k++;));
## = 42.424s

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(lift(Mod(2,2*k*p+1)^p) == 1, print("M"p" has a factor: "q); break;); k++;));
## = 52.559s

Any suggestions for making something than runs faster than what I'm using in the first code block above?

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

science_man_88 · 2012-11-21, 19:04

Quote:

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, but I'm unable to get it to run any faster than what I was originally using, which is just a "dumb" filter of skipping all k%4==2:

Code:

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(k%4==2,k++); 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;); k++;));
## = 31.913s

I tried some ideas, but (at least how I wrote it) it seems that the extra effort of checking whether a k-mod-something is allowed outweighs the benefit of filtering those values. Timings are based on 1000-iteration loop.

Code:

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, while(k%4!=0 && k%4!=1,k++); 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;); k++;));
## = 31.877s

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, 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;); k++;));
## = 32.168s

// on the assumption that 4294949947 % 4 == 3
for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(k%4==0||k%4==1,,k++); 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;); k++;));
## = 32.663s

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(((2*k*p+1)%6==1 || (2*k*p+1)%6==5) && ((2*k*p+1)%8==1 || (2*k*p+1)%8==7),,k++); q=2*k*p+1; if(lift(Mod(2,q)^p)==1, print("M"p" has a factor: "q); break;); k++;));
## = 42.424s

for(i=1, 1000, p=4294949947; k=10000; while(k<20000, if(lift(Mod(2,2*k*p+1)^p) == 1, print("M"p" has a factor: "q); break;); k++;));
## = 52.559s

Any suggestions for making something than runs faster than what I'm using in the first code block above?

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

I think I have a few ideas though I ran both codes in version 2.5.1 of Pari:

Code:

? for(i=1, 1000, p=4294949947; k=10000; while(k<20000, while(k%4!=0 && k%4!=1,k++); 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;); k++;));
? ##
  ***   last result computed in 25,264 ms.
? p=4294949947;for(i=1,1000,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))))
? ##
  ***   last result computed in 21,501 ms.

this turns a few of the while loops into a forstep loop. it also declares p only once at the beginning of the code, instead of the 1000 times it got it's value in your code. I cancelled using the break since it wouldn't have worked in my version or Pari as written.

James Heinrich · 2012-11-21, 19:12

Quote:

Originally Posted by science_man_88

this turns a few of the while loops into a forstep loop.
it also declares p only once at the beginning of the code, instead of the 1000 times it got it's value in your code.

You actually want to keep everything inside the 1000-loop, that's just there to make the timing a little more consistent over 1000 iterations (~30 seconds) rather than just one (~30 milliseconds).

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

science_man_88 · 2012-11-21, 19:24

Quote:

Originally Posted by James Heinrich

You actually want to keep everything inside the 1000-loop, that's just there to make the timing a little more consistent over 1000 iterations (~30 seconds) rather than just one (~30 milliseconds).

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

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.

2012-08-30, 19:08	#13
rcv Dec 2011 11×13 Posts	I think much of this thread is beyond the scope of James' question. I think the last 2 lines of my previous post and the first 5 lines of LaurV's post get to heart of James' question. A lot of this thread is more about efficiency in hunting for factors than "plausibility". It isn't necessary to try candidates q=2kp+1 that are not prime, because if they are composite, their component factors are probably already known. 256999 (k=4431) is composite and is a factor of M(29). But we probably already knew that 233 (k=4) and 1103 (k=19) were factors of M(29). Most tf algorithms try to ensure q doesn't have any small prime factors before they undertake the divisibility test of M(p)/q. @James: If you seek more than basic "plausibility", then I suggest you apply my plausibility test and also compute q=2kp+1. Then, depending on your application you can test q for primality (or probably primality) or you can trial factor q to some level of your choice. Are you "hunting" or "validating" values of k? Last fiddled with by rcv on 2012-08-30 at 19:21

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Distribution of Mersenne Factors	tapion64	Miscellaneous Math	21	2014-04-18 21:02
Known Mersenne factors	CRGreathouse	Math	5	2013-06-14 11:44
A strange new (?) fact about Mersenne factors	ChriS	Math	14	2006-04-12 17:36
Factors of Mersenne Numbers	asdf	Math	17	2004-07-24 14:00
Factors of Mersenne numbers ?	Fusion_power	Math	13	2003-10-28 20:52

2012-08-30, 22:46	#16
TheJudger "Oliver" Mar 2005 Germany 2127₈ Posts	Yes, it is possible. Those classes are artificial and are not directly related to mersenne numbers. They help to eleminate composite factor candidates (sieving) from the list more effecient. You can freely choose the number of classes, but some numbers are "better" than others, e.g. with 4620 those classes remove all composite factor candidates which are a multiple of 3, 5, 7 or 11 and don't satisfy the q == 1 or 7 mod 8 rule. 960 classes survive (20.78%). If you choose 4621 classes than 4620 classes survive (99.98%) because you can only eliminate factor candidates which are a multiple of 4621. Oliver