Thread: User TJAOI View Single Post
 2019-06-17, 21:43 #471 ATH Einyen     Dec 2003 Denmark 2·1,657 Posts 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