mersenneforum.org > Math Possible values for k (in Mersenne factors)
 Register FAQ Search Today's Posts Mark Forums Read

2012-08-30, 16:32   #12
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

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.

Last fiddled with by science_man_88 on 2012-08-30 at 17:20

 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
2012-08-30, 19:11   #14
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

32×19×23 Posts

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

2012-08-30, 19:43   #15
bloodIce

Feb 2010
Sweden

173 Posts

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.

 2012-08-30, 22:46 #16 TheJudger     "Oliver" Mar 2005 Germany 100010110012 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
2012-08-31, 00:53   #17
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

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=$
(q-1)\over{(2*p)}$
and with properties of q and p we should be able to find properties of k. including modular properties.

2012-08-31, 13:26   #18
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by science_man_88 I realize now basically all I was saying is: $q=2*k*p+1$ -> k=$ (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(,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.

Last fiddled with by science_man_88 on 2012-08-31 at 13:27

 2012-11-21, 15:36 #19 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 32·19·23 Posts 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.
2012-11-21, 19:04   #20
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

203428 Posts

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.

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

"James Heinrich"
May 2004
ex-Northern Ontario

32·19·23 Posts

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.

2012-11-21, 19:24   #22
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

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.

Last fiddled with by science_man_88 on 2012-11-21 at 19:25

 Similar Threads Thread Thread Starter Forum Replies Last Post tapion64 Miscellaneous Math 21 2014-04-18 21:02 CRGreathouse Math 5 2013-06-14 11:44 ChriS Math 14 2006-04-12 17:36 asdf Math 17 2004-07-24 14:00 Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 11:31.

Mon Dec 5 11:31:53 UTC 2022 up 109 days, 9 hrs, 0 users, load averages: 0.62, 0.88, 1.07