20210913, 20:20  #12 
Mar 2021
54_{8} Posts 
The math might work, it might be an error on my side with double the bit_length(). I'll look into it if anyone asks.

20210914, 00:20  #13  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
5,783 Posts 
heavily annotated quote follows. program that produced the quoted section seems not in evidence. Also note k=1 2kp+1 = 59 does not appear. It's ok in this case since it is not 1 or 7 mod 8, but the smallest factors (smallest k) are the most commonly occurring factors.
Quote:
Your method is very inefficient. Try using it on M71 or M163. It is generating a lot of false candidate factors (30 out of 35 above) that have small easily avoided factors themselves, or do not meet the 1 or 7 mod 8 requirement. That is, they can not be prime factors of the number you wish to factor, since they are not prime themselves, or are not possible factors of Mersennes. It's progressing through the number line at ~(2089117)/34 ~ 58 =2p per trial performed on M29. That you numbered most of them in pairs, only obscures, does not change, that. Using a modest wheel of 60 instead: 16 initial candidates, which sieving reduced to 6, over a span of 3480. 3480/6= 580 = 20p per trial, ten times as fast, after some wheel setup. Testing 6 surviving candidates against the Mersenne prime M29, we find three of those are factors, and the small Mersenne number is then fully factored, before the 6th candidate, so stop at 5 tests. Generally in GIMPS we stop after 1 factor found, or completion of the class or bit level in which the smallest factor was found. The advantage of the wheel is greater when the Mersenne to be factored is much larger, so the wheel's initial setup gets reused many (millions or billions or trillions of) times on the same p and bit level. At ~M106M, taking 74 bits to 75, the range is 2^{74} = 18,889,465,931,478,580,854,784; mfaktx moreclasses covers a subrange 4620 * 2 * ~106M ~ 979,440,000,000 ("per revolution of the wheel"). And for each of the 4620 classes, the mod 3, mod 5, mod 7, mod 11, and mod 8 tests would have been applied at most ONCE per class to usually weed out an entire class of many billions of candidate factors simultaneously. One can think of those classes as going out one radial spoke at a time, each spoke corresponding to a class that survived the initial setup,or didn't, which is all candidate trial factors in the bit range that are the same x value modulo wheel size. How does that work? We know that if a base number for a class is divisible by some small prime, such as 3, that is a factor of the wheel size, adding any multiples of the wheel size, the sums will also be divisible by that small prime. Each of the 960 surviving classes would have ~19,285,985,800 members, which would then get about optimally sieved for total throughput performance, informed by prior benchmarking. Going further up the scale, 2^{85} to 2^{86} for ~1G, 2^{85}/4620/2/1G ~4,186,756,085,245 (~4 trillion) members per class. https://www.mersenne.ca/exponent/999999937 Last fiddled with by kriesel on 20210914 at 00:38 

20210914, 00:54  #14  
Mar 2021
2C_{16} Posts 
Quote:


20210914, 01:22  #15  
Feb 2017
Nowhere
5×997 Posts 
Quote:


20210914, 01:36  #16 
Mar 2021
2^{2}·11 Posts 

20210914, 01:51  #17 
Feb 2017
Nowhere
5·997 Posts 
Just to be clear, the lines were marked "Wasted effort" because the candidates were congruent to 3 or 5 (mod 8), hence ineligible. Simply avoiding those candidates would cut the run time of your routine approximately in half.

20210914, 02:00  #18 
Mar 2021
2^{2}×11 Posts 
Thanks for that info. I am interested in this for personal reasons,so i'll try that out

20210914, 02:44  #19 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
5,783 Posts 

20210914, 12:30  #20  
Feb 2017
Nowhere
5×997 Posts 
Quote:
What I would implore you to consider, is the fact that people have been thinking about this subject for a long, long time, and it is therefore not only possible, but very likely, that any elementary result anyone discovers these days, has already been known for many years. While it can be disappointing to the rediscoverer to learn that their fresh, new discovery has actually been known for centuries, it should also be reassuring to realize that their rediscovery is at least correct. It's happened to me. It's probably happened to just about everyone who's done serious work in mathematics or mathbased projects. Then there is the matter of coding. I would consider my own Pari script as nothing more than illustrative of the results (1) and (2) below for small prime exponents p. For serious effort at finding factors, I would recommend using the software provided by people who have familiarized themselves with the known mathematical results, understand how computers do what they do, and have for decades been writing, optimizing, and debugging code to do trial factorization, etc of Mersenne numbers. Let p be an odd prime, and q an odd prime such that q divides 2^{p}  1. 1) Then (Fermat's "little theorem") q divides 2^{q1}  1. It follows that p divides q1. Proof (probably known to Fermat, certainly to Euler) left as exercise. Feel free to look it up. Note: Since p is odd and q1 is even, 2p also divides q1. 2) q == 1 or 7 (mod 8). Sketch of proof: Since 2p divides q  1, p divides . Thus, since q divides 2^{p}  1, q also divides . Therefore, 2 is a quadratic residue (mod q), and the result follows. Note: This certainly would have been known to Gauss. 3) Let k be a positive integer. Suppose p = 4*k + 3 and q = 2p + 1 = 8*k + 7 are both prime. Then q divides 2^{p}  1. Proof left as exercise. Hint: Apply result (2). Note: Whether there are infinitely many k for which p = 4*k + 3 and q = 2*p + 1 = 8*k + 7 are both prime, is an open question. There are conjectured asymptotic formulas, supported by limited numerical data, that would say "Yes" to this and a host of similar questions. The conjectures indicate that the proportion of prime p = 4*k + 3 for which q = 8*k + 7 is also prime, slowly decreases toward 0 as k increases without bound. Last fiddled with by Dr Sardonicus on 20210914 at 12:32 Reason: insert missing word; fignix posty 

20210914, 22:56  #21 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
5,783 Posts 
A little additional reading is available in the KNL thread showing the techniques and process by which TF code was being developed for CPU types. There are pages after that post; click the thread at upper right.

20210915, 02:07  #22  
Romulan Interpreter
Jun 2011
Thailand
2^{4}·13·47 Posts 
Quote:
(edit: nitpicking: in (3), change q to q', or r, or post it as independent paragraph  using q makes is circular, you stated the hypothesis "q divides 2^p1" in the beginning ) Last fiddled with by LaurV on 20210915 at 02:16 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factors for the differences between Mersenne numbers  a nicol  Miscellaneous Math  1  20201015 09:53 
factors of Mersenne numbers  bhelmes  Miscellaneous Math  8  20200914 17:36 
Mersenne Prime Factors of v.large numbers  devarajkandadai  Miscellaneous Math  6  20060104 22:44 
Factors of Mersenne Numbers  asdf  Math  17  20040724 14:00 
Factors of Mersenne numbers ?  Fusion_power  Math  13  20031028 20:52 