View Single Post
Old 2021-09-13, 14:18   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

500910 Posts
Default

Quote:
Originally Posted by LarsNet View Post
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.
Assuming your code is supposed to do trial division of 2^k - 1 for odd k by numbers congruent to 1 (mod 2k) (and maybe it's just me, but I found your code to be excessively obscure), I note the following:

1) If k is odd and composite, not all prime factors of 2^k - 1 are congruent to 1 (mod 2k). If d|k, the prime factors of the "primitive part" of \Phi_{d}\(2\) are congruent to 1 (mod 2d). They do not have to be congruent to 1 (mod 2k). For example, the factor 2^3 - 1 = 7 of 2^39 - 1 is congruent to 1 (mod 6) but not congruent to 1 (mod 78); and the factor 2^5 - 1 = 31 of 2^65 - 1 is congruent to 1 (mod 10) but not congruent to 1 (mod 65).

2) If p is an odd prime, it is well known that the prime factors of 2^p - 1 are congruent to 1 (mod 2p), and also congruent to 1 or 7 (mod 8).

3) If p is of any size at all, trial division up to the square root of 2^p - 1 is totally impracticable.

4) Also, if p is of any size at all, the number of candidates q == 1 (mod 2p) and 1 or 7 (mod 8) can be reduced significantly by excluding those with small prime factors.

I incorporated the facts in (2) into an otherwise totally mindless Pari-GP script. I wrote the script in a text editor and filled in the exponent by hand for each run, and copy-pasted it into a Pari-GP session. I didn't bother trying to code user input.

Code:
 {
p = 67;
n = 2^p - 1;
q=1;
r=p%4;
r=4-r;
a = 8*r*p;
d=2*r*p;
q=1;
c=0;
m=1;
until(m==0||c>1000000,
q+=d;
c++;
d=a-d;
m=n%q;
if(m==0,
print("Try number "c" found the factor "q" of 2^"p" - 1.")
);
if(c>1000000,print("No factors found in a million tries."))
)
}
Try number 722790 found the factor 193707721 of 2^67 - 1.
? {
p = 101;
n = 2^p - 1;
q=1;
r=p%4;
r=4-r;
a = 8*r*p;
d=2*r*p;
q=1;
c=0;
m=1;
until(m==0||c>1000000,
q+=d;
c++;
d=a-d;
m=n%q;
if(m==0,
print("Try number "c" found the factor "q" of 2^"p" - 1.")
);
if(c>1000000,print("No factors found in a million tries."))
)
}
No factors found in a million tries.
?
Dr Sardonicus is offline   Reply With Quote