Thread: User TJAOI
View Single Post
Old 2019-06-17, 21:43   #471
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·1,657 Posts
Default

I can try to show each of the 3 methods here.



Factors of Mersenne numbers 2p - 1 : q = 2*k*p + 1



"Search by p" (standard GIMPS method)

Choose prime exponent p to trial factor for example p=85000007.

Mfaktc will create an array of k-values in the desired bit range, and then remove all k-values where 2*k*85000007 + 1 is not one of the 16 possible values mod 120 which is needed to be a Mersenne factor (1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119).

Then Mfaktc will remove all k-values from the array where 2*k*85000007+1 has factors up to the limit set in mfaktc.ini (Default GPUSievePrimes=82486. Which is the 82486th prime: 1,055,143).

All the surviving factors 2*k*85000007+1 from the array will then be trial divided into 285000007-1 to check if we found a factor.

Code:
.
.
2*1000*85000007+1
2*1001*85000007+1
2*1002*85000007+1 (prime but is 109 mod 120)
2*1003*85000007+1
2*1004*85000007+1
2*1005*85000007+1
2*1006*85000007+1
2*1007*85000007+1
2*1008*85000007+1
2*1009*85000007+1
2*1010*85000007+1
2*1011*85000007+1
2*1012*85000007+1
2*1013*85000007+1
2*1014*85000007+1 (prime but is 37 mod 120)
2*1015*85000007+1
.
.


"Search by k"

Choose a single k value for example k=1017. Create an array of all 50,847,534 primes p below 1 billion.
Remove all p-values from the array where 2*1017*p + 1 is not one of the 16 possible values mod 120.
Remove all the values 2*1017*p + 1 in the array with small factors up to a certain point where the removal gets slower than the time to trial divide.
Trial divide the surviving candidates, where each 2*1017*p + 1 is trial divided into the corresponding Mersenne number 2p-1.
Code:
2*1017*2+1
2*1017*3+1
2*1017*5+1
2*1017*7+1
2*1017*11+1
2*1017*13+1
.
.
2*1017*100129+1
2*1017*100151+1
2*1017*100153+1
2*1017*100169+1
2*1017*100183+1
2*1017*100189+1
2*1017*100193+1
2*1017*100207+1
2*1017*100213+1
2*1017*100237+1
2*1017*100267+1
2*1017*100271+1
.
.
2*1017*999999883+1
2*1017*999999893+1
2*1017*999999929+1
2*1017*999999937+1


"Search by q".

This is the slightly odd method TJAOI uses, the benefit is that factors are found consecutively.

Check each prime q = 2*k*p + 1 one at the time, but only those that are equal to one of the possible 16 values mod 120.
For example near 2^65 where TJAOI is working: q=36893488147419103457
Factor k*p = (q-1)/2 = 18446744073709551728 = 2^4 * 1723 * 2447 * 273451615243

Now each of the prime factors of k*p could be the prime exponent p, and then the remaining part of k*p would be the k-value.
Trial divide q into each Mersenne number corresponding to each factor of k*p below 1 billion, here in the example 21723 - 1 and 22447 - 1.

Continue to the next prime q (with the correct mod 120 value).

Instead of spending time finding prime q's, he might be using a PRP test only or only trial dividing a q-array, so he tests all q which has no small factors...


Edit: Now that I think about it, he is probably trial factoring an array of q-values. When he is doing "q mod small primes" if he gets 0 he can remove that q from the array, but if he gets 1 then that small prime is a factor of q-1 = 2kp which he can save and use for the next step.


Code:
.
.
q=36893488147419103363
q=36893488147419103397
q=36893488147419103439   =>  k*p = 18446744073709551719 = 7*311*8473469946582247
q=36893488147419103457   =>  k*p = 18446744073709551728 = 2^4*1723*2447*273451615243
q=36893488147419103463   =>  k*p = 18446744073709551731 = 557*33118032448311583
q=36893488147419103493
q=36893488147419103693
q=36893488147419103747
q=36893488147419103769   =>  k*p = 18446744073709551884 = 2^2*19*35323*6871452502883
q=36893488147419103807   =>  k*p = 18446744073709551903 = 3*19*11171*28970288157949
q=36893488147419103877
.
.

Last fiddled with by ATH on 2020-01-27 at 18:14
ATH is offline   Reply With Quote