mersenneforum.org > Math factors of Mersenne numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-09-13, 20:20 #12 LarsNet   Mar 2021 2C16 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.
2021-09-14, 00:20   #13
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

22·1,481 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:
 count, jump, formula to generate prime, and 0 56 117 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 7 bits factor candidate above here (1 trial factor between 64 and 128) 0 86 175 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 1 114 233 Factor Found 8 bits factor candidates above here (2 trial factors between 128 and 256) 1 144 291 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 2 172 349 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 2 202 407 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 3 230 465 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 9 bits factor candidates above (4 trial factors between 256 and 512) 3 260 523 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 4 288 581 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 4 318 639 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 5 346 697 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 5 376 755 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 6 404 813 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 6 434 871 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 7 462 929 Factor Not Found 7 492 987 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 10 bits factor candidates above (9 trial factors between 512 and 1024) 8 520 1045 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 8 550 1103 Factor Found 9 578 1161 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 9 608 1219 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 10 636 1277 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 10 666 1335 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 11 694 1393 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 11 724 1451 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 12 752 1509 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 12 782 1567 Factor Not Found 13 810 1625 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 13 840 1683 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 14 868 1741 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 14 898 1799 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 15 926 1857 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 15 956 1915 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 16 984 1973 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 16 1014 2031 Factor Not Found /candidate factor composite, or not 1 or 7 mod 8, a waste of time 11 bits factor candidates above (18 trial factors between 1024 and 2048) 17 1042 2089 Factor Found 12 bits So our 17th iteration is already at 1042.
(end of annotated 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 ~(2089-117)/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 274 = 18,889,465,931,478,580,854,784; mfaktx more-classes covers a sub-range 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, 285 to 286 for ~1G, 285/4620/2/1G ~4,186,756,085,245 (~4 trillion) members per class. https://www.mersenne.ca/exponent/999999937
Attached Files
 wheel.pdf (44.5 KB, 38 views) wheel71.pdf (44.8 KB, 41 views)

Last fiddled with by kriesel on 2021-09-14 at 00:38

2021-09-14, 00:54   #14
LarsNet

Mar 2021

22·11 Posts

Quote:
 Originally Posted by kriesel 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. (end of annotated quote)
Thank you for the great explanation and pdf attachments. I feel very informed and have seen information i wasn't aware of. BTW, where in these forums would be a good explanation of these methods, i'd like to learn more about them.

2021-09-14, 01:22   #15
Dr Sardonicus

Feb 2017
Nowhere

7·733 Posts

Quote:
 Originally Posted by LarsNet Just go with me on this, if you look at the right column,
Quote:
 0 56 117 Wasted effort 0 86 175 Factor Not Found 1 114 233 Factor Found 1 144 291 Wasted effort 2 172 349 Wasted effort 2 202 407 Factor Not Found 3 230 465 Factor Not Found 3 260 523 Wasted effort 4 288 581 Wasted effort 4 318 639 Factor Not Found 5 346 697 Factor Not Found 5 376 755 Wasted effort 6 404 813 Wasted effort 6 434 871 Factor Not Found 7 462 929 Factor Not Found 7 492 987 Wasted effort 8 520 1045 Wasted effort 8 550 1103 Factor Found 9 578 1161 Factor Not Found 9 608 1219 Wasted effort 10 636 1277 Wasted effort 10 666 1335 Factor Not Found 11 694 1393 Factor Not Found 11 724 1451 Wasted effort 12 752 1509 Wasted effort 12 782 1567 Factor Not Found 13 810 1625 Factor Not Found 13 840 1683 Wasted effort 14 868 1741 Wasted effort 14 898 1799 Factor Not Found 15 926 1857 Factor Not Found 15 956 1915 Wasted effort 16 984 1973 Wasted effort 16 1014 2031 Factor Not Found 17 1042 2089 Factor Found
FTFY

2021-09-14, 01:36   #16
LarsNet

Mar 2021

22×11 Posts

Quote:
 Originally Posted by Dr Sardonicus FTFY
haha, thanks Dr. Sardonicus! Maybe i shouldn't waste so much effort, lol

2021-09-14, 01:51   #17
Dr Sardonicus

Feb 2017
Nowhere

513110 Posts

Quote:
 Originally Posted by LarsNet haha, thanks Dr. Sardonicus! Maybe i shouldn't waste so much effort, lol
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.

2021-09-14, 02:00   #18
LarsNet

Mar 2021

22×11 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.
Thanks for that info. I am interested in this for personal reasons,so i'll try that out

2021-09-14, 02:44   #19
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

22×1,481 Posts

Quote:
 Originally Posted by LarsNet where in these forums would be a good explanation of these methods, i'd like to learn more about them.
Follow the link in post 9. And the links it leads to. Read, think, understand. Mfaktc development thread from the beginning too.

2021-09-14, 12:30   #20
Dr Sardonicus

Feb 2017
Nowhere

7×733 Posts

Quote:
Originally Posted by LarsNet
Quote:
 Originally Posted by Dr Sardonicus 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.
Thanks for that info. I am interested in this for personal reasons,so i'll try that out
I can not improve on the sources already cited. The information you are thanking me for here, I had already given you in a previous post, and is also in the reference with link provided in this post. It is disappointing to see you have not been availing yourself of the information we have been spending time and effort to make easily available to you.

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 re-discoverer 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 math-based 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 2p - 1.

1) Then (Fermat's "little theorem") q divides 2q-1 - 1. It follows that p divides q-1.
Proof (probably known to Fermat, certainly to Euler) left as exercise. Feel free to look it up. Note: Since p is odd and q-1 is even, 2p also divides q-1.

2) q == 1 or 7 (mod 8).
Sketch of proof: Since 2p divides q - 1, p divides $\frac{q-1}{2}$. Thus, since q divides 2p - 1, q also divides $2^{\frac{q-1}{2}}\;-\;1$. 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 2p - 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 2021-09-14 at 12:32 Reason: insert missing word; fignix posty

 2021-09-14, 22:56 #21 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 134448 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.
2021-09-15, 02:07   #22
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24×613 Posts

Quote:
 Originally Posted by Dr Sardonicus While it can be disappointing to the re-discoverer 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 math-based projects.
Very sir! (I mean, all of it, not only quoted part).
(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^p-1" in the beginning )

Last fiddled with by LaurV on 2021-09-15 at 02:16

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post a nicol Miscellaneous Math 1 2020-10-15 09:53 bhelmes Miscellaneous Math 8 2020-09-14 17:36 devarajkandadai Miscellaneous Math 6 2006-01-04 22:44 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 13:46.

Sat Dec 4 13:46:00 UTC 2021 up 134 days, 8:14, 0 users, load averages: 0.77, 0.94, 0.98

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