View Single Post
Old 2021-09-14, 00:20   #13
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

22·3·13·37 Posts
Default

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
File Type: pdf wheel.pdf (44.5 KB, 20 views)
File Type: pdf wheel71.pdf (44.8 KB, 21 views)

Last fiddled with by kriesel on 2021-09-14 at 00:38
kriesel is offline   Reply With Quote