
Quote:
Originally Posted by Dr Sardonicus
Of course, since n _{0} < f/2, the cofactor (2*n _{0}^2  1)/f < f/2. So if the cofactor is prime, it is certainly less than f.
Since I could think of no reason why the cofactor should always be prime, as a programming exercise I wrote a mindless script to look for counterexamples for 2^p  1 with small prime exponent p.
I told it to print out the exponent p, the smallest factor f of 2^p  1, the value n _{0}, and the factorization of the cofactor (2*n _{0}^2  1)/f when this was composite.
The smallest exponent giving a counterexample is p = 47. To my surprise, with the smallest example 47 (f = 2351, n _{0} = 240) and 113 (f = 3391, n _{0} = 700) the cofactor (2*n _{0}^2  1)/f is the square of a single prime. The smallest prime exponent for which the cofactor (2*n _{0}^2  1)/f has at least two distinct prime factors is 59.
Code:
? {
forprime(p=3,200,
M=factor(2^p1);
f=M[1,1];
m=factormod(2*x^21,f);
n=lift(polcoeff(m[1,1],0,x));
if(n+n>f,n=fn);
N=factor((2*n^21)/f);
if(#N[,1]>1(#N[,1]==1&&N[1,2]>1),print(p" "f" "n" "N))
)
}
47 2351 240 Mat([7, 2])
59 179951 77079 [7, 1; 9433, 1]
67 193707721 66794868 [191, 1; 241177, 1]
71 228479 76047 [23, 1; 31, 1; 71, 1]
97 11447 5670 [41, 1; 137, 1]
101 7432339208719 3616686326055 [7, 1; 17, 1; 23, 1; 1583, 1; 812401, 1]
103 2550183799 270087243 [23, 1; 241, 1; 10321, 1]
109 745988807 298036466 [17, 1; 14008369, 1]
113 3391 700 Mat([17, 2])
137 32032215596496435569 6857964810884905735 [2503, 1; 358079, 1; 3276376633, 1]
151 18121 2513 [17, 1; 41, 1]
163 150287 31486 [79, 1; 167, 1]
173 730753 162850 [7, 1; 10369, 1]
179 359 170 [7, 1; 23, 1]
193 13821503 2664653 [7, 1; 146777, 1]
199 164504919713 50650852663 [7, 1; 4455809207, 1]
?

Dr. Sardonicus, i have found the all factors of mersenne primes follow a pattern that follows the bit_length() of the number which can be climbed from a starting number of the bit_length + the bit_length()1 as shown in the quote below. At each climb you can do the tests inside the quote to check for a factor. This is obviously suboptimal and a faster way to generate the factors would be beneficial.
Just pointing this out as i found you post informing and wanted to point out the formula for generating the factors of prime numbers which are then used to create a mersenne number. You may already know this but just wanting to point it out to those interested in where those numbers ( factors ) come from.
On a side note, kind of wondering if trial division for mersenne numbers employ this climbing technique already as it chops out a lot of unnecessary tests
Quote:
Each OUT here can be tested as a factor of the mersenne via OUT*2+3 and (OUT+1)*2+3. and modding to see if the answer is zero. If you reach the sqrt of the number and no factors are found, then the mersenne is prime. Otherwise it had factors with a modulus of M[x]%(OUT*2) + 3 and M[x]%(OUT+1)*2+3.
In [3342]: 46+47 * 2
Out[3342]: 140
In [3343]: 140+47 * 2
Out[3343]: 234
In [3344]: 234+47 * 2
Out[3344]: 328
In [3345]: 328+47 * 2
Out[3345]: 422
In [3346]: 422+47 * 2
Out[3346]: 516
In [3347]: 516+47 * 2
Out[3347]: 610
In [3348]: 610+47 * 2
Out[3348]: 704
In [3349]: 704+47 * 2
Out[3349]: 798
In [3350]: 798+47 * 2
Out[3350]: 892
In [3351]: 892+47 * 2
Out[3351]: 986
In [3352]: 986+47 * 2
Out[3352]: 1080
In [3353]: 1080+47 * 2
Out[3353]: 1174
In [3354]: 1174*2+3
Out[3354]: 2351
Python CODE That does the above:
def getfactorsfromoffset2(n):
factors = []
x = gmpy2.mpz(31)
xr = gmpy2.bit_length(31)
r = gmpy2.bit_length(n)
jump = r  xr + 4
tsqrt = gmpy2.isqrt(n)
count = 0
while True and jump < tsqrt:
sjo = ( jump + r  1 ) % n
sjt = ( jump + r*2 ) % n
jump = sjt
if n%(((sjo+1)*2)+3) == 0:
print(count, (sjo+1)*2+3, "Factor Found")
break
elif n%(((sjt)*2)+3) == 0:
print(count, (sjt)*2+3, "Factor Found")
break
#r *= 2 % sjt
##if count > 15000: break
count+=1
In [3366]: getfactorsfromoffset2(2**431)
1 431 Factor Found Offset for each jump is bit_length 43
In [3367]: getfactorsfromoffset2(2**531)
29 6361 Factor Found Offset for each jump is bit_length 53
In [3368]: getfactorsfromoffset2(2**671)
722789 193707721 Factor Found Offset for each jump is bit_length 67
In [3391]: getfactorsfromoffset2(2**551)
3 881 Factor Found Offset for each jump is bit_length 55
In [3392]: getfactorsfromoffset2(2**571)
141 32377 Factor Found Offset for each jump is bit_length 57
In [3393]: getfactorsfromoffset2(2**591)
761 179951 Factor Found Offset for each jump is bit_length 59
In [3394]: getfactorsfromoffset2(2**631)
367 92737 Factor Found Offset for each jump is bit_length 63
In [3395]: getfactorsfromoffset2(2**651)
30 8191 Factor Found Offset for each jump is bit_length 65
In [3396]: getfactorsfromoffset2(2**671)
722789 193707721 Factor Found Offset for each jump is bit_length 67
In [3372]: getfactorsfromoffset2(2**331)
14 2047 Factor Found Offset for each jump is bit_length 33
In [3373]: getfactorsfromoffset2(2**351)
877 122921 Factor Found Offset for each jump is bit_length 35
In [3374]: getfactorsfromoffset2(2**371)
0 223 Factor Found Offset for each jump is bit_length 37
In [3375]: getfactorsfromoffset2(2**391)
51 8191 Factor Found Offset for each jump is bit_length 39
In [3376]: getfactorsfromoffset2(2**411)
80 13367 Factor Found Offset for each jump is bit_length 41
In [3377]: getfactorsfromoffset2(2**431)
1 431 Factor Found Offset for each jump is bit_length 43
In [3378]: getfactorsfromoffset2(2**451)
2 631 Factor Found Offset for each jump is bit_length 45
In [3379]: getfactorsfromoffset2(2**471)
11 2351 Factor Found Offset for each jump is bit_length 47

Last fiddled with by LarsNet on 20210913 at 01:29
