mersenneforum.org  

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

Reply
 
Thread Tools
Old 2002-09-26, 16:22   #12
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

5×2,351 Posts
Default

Quote:
Originally Posted by asdf
I have found this, but I am not sure about it (especially because it contains an error

Quote:
If p==1 mod 4 then k==3 or 0 mod 4. If p==3 mod 4 then k==0 or 1 mod 4
This gives us a nice try 2, skip 2 type pattern, so all that we have to do
is set the initial value the factor, then add 2p or 4p according to the
pattern.
Now, the 4p in that last part should be 6p. Is this statement correct? I am guessing in your statements that you say that p = 2qk+1, and this quote says that p is the exponent of the Mersenne.
Yes, it should be 2p and 6p, where here, whoever wrote this was using
p for the Mersenne exponent, rather than q (I believe this notation
is more common; I used q for the exponent to be consistent with the
notation used in the post i was replying to.) I encourage you to find
other such correlations (e.g exponent mod 3, 5, 7,...)

-Ernst
ewmayer is offline   Reply With Quote
Old 2004-07-17, 21:13   #13
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·17·101 Posts
Default

E.W.Mayer wrote:

Quote:
Another thing that bears mentioning is that in fact there are
additional rigorous correlations between the Mersenne exponent q
modulo 3,4,5,... and k mod 3,4,5,... . Exploiting the simplest
few of these can reduce the number of k's we need to try to
achieve a desired factor-size bound by 75-80%.
Quote:
Among other shortcuts, Prime95 trial factoring considers only the 16 congruence classes mod 120 (+-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49) that might contain prime Mersenne factors. Thus it skips fourteen of the mod 120 congruence classes (+-9, +-15, +-25, +-33, +-39, +-55, and +-57) which satisfy +-1 mod 8 but are never prime.
Are there even more correlations for k and d=2kp+1 besides the 16 congruence classes mod 120? If yes where can I find them?
ATH is offline   Reply With Quote
Old 2004-07-17, 21:16   #14
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

65528 Posts
Default

Are there any restrictions for factors of Mersenne numbers Mq where q is not prime for both even and odd q?
ATH is offline   Reply With Quote
Old 2004-07-19, 16:11   #15
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts
Default

Quote:
Originally Posted by ATH
Are there even more correlations for k and d=2kp+1 besides the 16 congruence classes mod 120? If yes where can I find them?
Well, you can further eliminate multiples of 7 by using congruence classes mod 840, and so on.
cheesehead is offline   Reply With Quote
Old 2004-07-20, 12:50   #16
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010111110012 Posts
Default

Quote:
Originally Posted by cheesehead
Well, you can further eliminate multiples of 7 by using congruence classes mod 840, and so on.
IIRC, sieving mod 840 does not help speeding up the algorithm...

Luigi
ET_ is offline   Reply With Quote
Old 2004-07-24, 02:32   #17
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by ET_
IIRC, sieving mod 840 does not help speeding up the algorithm...
My answer addressed the mathematics, not algorithmic or programming concerns. Going to an 840 mod would indeed speed up the algorithm, but when one looks at programming considerations, one may decide that the (small) speed gain is not enough to be worth the side effects.

Example: Originally, when Prime95 found a factor during trial factoring, it continued looking for a smaller factor during the uncompleted passes. (I.e., if it found a factor that was 7 mod 120, it continued looking in the 11 mod 120, 13 mod 120, ... and 119 mod 120 congruence classes.) One might decide that going to the more-numerous congruence classes mod 840 was not worth the side effect of having to trudge through the extra passes. It's not so much the teeny-tiny extra time involved as it is the psychological effect of users seeing it go through perhaps almost 100 more passes instead of only a dozen more. (I'm not saying this is a killer objection in particular. I'm saying this is an example of a side effect that deserved to be considered.) Also, once the mod 120 version had been tested and posted for use, changing to mod 840 or 9240 or whatever would require proportionally more testing and updating than they would have if originally used. Also, George W. considers the value to overall GIMPS throughput versus the required effort to make the change, in contrast to the value/effort ratios of a long list of other potential speedups.

Last fiddled with by cheesehead on 2004-07-24 at 02:41
cheesehead is offline   Reply With Quote
Old 2004-07-24, 14:00   #18
biwema
 
biwema's Avatar
 
Mar 2004

3×127 Posts
Default

Maybe there is a slight improvement, if you use 96 passes out of 840 or 960 passes out of 9240 instead of 16 out of 120. With that change you have 1/7 and 1/11 less candidates, but these are divisible by 7 and 11 and hence sieved in the first 2 loops anyway.
The only thing you get, is a little bit more dense sieving table, that you can put more candidates into the same space. Mathematically, the sieving gets more efficient, the bigger the sieving table gets, because the sieving limit can be higher. In the computer implementation, it is not recommended to define the table so large that the whole does not fit into the L1 cache. (I am pretty sure that George Woltman takes care of that).
One possibility to optimize the sieving process is to define the size of the array to a size which is the product of the next few primes. For 840, the array would be 11*13*17 or so. In that array, the composite candidates can already be marked and the array can be copied, that it can be directly be taken for the next steps. If the copying is faster than deleting the array sieving these three primes, it will improve the whole a bit (A sieve is least efficient at small primes, because the steps are small and more of them are needed.)
If we want to find factors as soon as possible, it makes sense to check the numbers in increasing order. Instead of finishing all stages for one bits, every stage can be sieved for 64 -64.1 bit first then 64.1 - 64.2 bit and so on. If these steps are too small (that can happen if the number of stages is too high), the time penalty for switching the stages is too high and we gain nothing. Here, an optimum needs to be found.
biwema is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 factoring attempts at smallest-remaining Mersenne numbers with no known factors UberNumberGeek Factoring 51 2017-02-13 20:30
Modular restrictions on factors of Mersenne numbers siegert81 Math 23 2014-03-18 11:50
Mersenne prime factors of very large numbers devarajkandadai Miscellaneous Math 15 2012-05-29 13:18
Mersenne Prime Factors of v.large numbers devarajkandadai Miscellaneous Math 6 2006-01-04 22:44
Factors of Mersenne numbers ? Fusion_power Math 13 2003-10-28 20:52

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


Thu Feb 2 11:59:03 UTC 2023 up 168 days, 9:27, 1 user, load averages: 0.75, 0.91, 0.97

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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