mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-08-30, 16:32   #12
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts
Default

Quote:
Originally Posted by ATH View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-08-30, 19:08   #13
rcv
 
Dec 2011

11·13 Posts
Default

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
rcv is offline   Reply With Quote
Old 2012-08-30, 19:11   #14
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

32×19×23 Posts
Default

Quote:
Originally Posted by rcv View Post
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 ).
James Heinrich is offline   Reply With Quote
Old 2012-08-30, 19:43   #15
bloodIce
 
bloodIce's Avatar
 
Feb 2010
Sweden

173 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
bloodIce is offline   Reply With Quote
Old 2012-08-30, 22:46   #16
TheJudger
 
TheJudger's Avatar
 
"Oliver"
Mar 2005
Germany

100010110012 Posts
Default

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
TheJudger is offline   Reply With Quote
Old 2012-08-31, 00:53   #17
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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 is offline   Reply With Quote
Old 2012-08-31, 13:26   #18
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.

Last fiddled with by science_man_88 on 2012-08-31 at 13:27
science_man_88 is offline   Reply With Quote
Old 2012-11-21, 15:36   #19
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

32·19·23 Posts
Default

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.
James Heinrich is offline   Reply With Quote
Old 2012-11-21, 19:04   #20
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

203428 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-11-21, 19:12   #21
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

32·19·23 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
James Heinrich is offline   Reply With Quote
Old 2012-11-21, 19:24   #22
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔