Quote:
Originally Posted by LarsNet
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 dk, the prime factors of the "primitive part" of
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 PariGP script. I wrote the script in a text editor and filled in the exponent by hand for each run, and copypasted it into a PariGP session. I didn't bother trying to code user input.
Code:
{
p = 67;
n = 2^p  1;
q=1;
r=p%4;
r=4r;
a = 8*r*p;
d=2*r*p;
q=1;
c=0;
m=1;
until(m==0c>1000000,
q+=d;
c++;
d=ad;
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=4r;
a = 8*r*p;
d=2*r*p;
q=1;
c=0;
m=1;
until(m==0c>1000000,
q+=d;
c++;
d=ad;
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.
?