Factoring Mersenne numbers
 

I have developed a method to factor some Mersenne numbers:

[CODE]{factorM(p)=local(n,x,m,g);n=2^p-1;x=Mod(3,n);m=2;while(m<=p,x=x^m;m++;);g=gcd(lift(x-1),n);if(g>1,print(p" "g))}[/CODE]

[CODE]? factorM(27143)
27143 642187644650465775694903687658288936692113743236475279
[/CODE]

Is this a known way?

[QUOTE=paulunderwood;465785]I have developed a method to factor some Mersenne numbers:

[CODE]{factorM(p)=local(n,x,m,g);n=2^p-1;x=Mod(3,n);m=2;while(m<=p,x=x^m;m++;);g=gcd(lift(x-1),n);if(g>1,print(p" "g))}[/CODE]

[CODE]? factorM(27143)
27143 642187644650465775694903687658288936692113743236475279
[/CODE]

Is this a known way?[/QUOTE]

I think there were some PRP tests talked about that used 3 raised to some value. really this is doing an exhaustive GCD with the set [TEX]\{s:s=3^{m!}-1\}[/TEX] edit:with slight changes I found a supposed factor of that same mersenne ( much lower) in under 5 seconds 60772750969048040777, but it's composite and already known based on the factors listed on mersenne.ca.

[QUOTE=paulunderwood;465785]I have developed a method to factor some Mersenne numbers:

[CODE]{factorM(p)=local(n,x,m,g);n=2^p-1;x=Mod(3,n);m=2;while(m<=p,x=x^m;m++;);g=gcd(lift(x-1),n);if(g>1,print(p" "g))}[/CODE]

[CODE]? factorM(27143)
27143 642187644650465775694903687658288936692113743236475279
[/CODE]

Is this a known way?[/QUOTE]

[url]https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm[/url]

[QUOTE=paulunderwood;465785]I have developed a method to factor some Mersenne numbers:

[CODE]{factorM(p)=local(n,x,m,g);n=2^p-1;x=Mod(3,n);m=2;while(m<=p,x=x^m;m++;);g=gcd(lift(x-1),n);if(g>1,print(p" "g))}[/CODE]

[CODE]? factorM(27143)
27143 642187644650465775694903687658288936692113743236475279
[/CODE]

Is this a known way?[/QUOTE]

Yes, as already pointed out, it's Pollard P-1. When m hits p, you'll find any factors f = k*p + 1 of 2^p - 1 for which k divides (p - 1)!, since these will divide 3^p! - 1.

Since (I'm guessing) it is unlikely you'll find anything [i]before[/i] m = p, the computation for this method looks to become prolonged if p is large.

With p = 27143, you actually found a number of prime factors at once:

? f=642187644650465775694903687658288936692113743236475279;factor(f)
time = 48 ms.
%1 =
[54287 1]

[868577 1]

[5211457 1]

[44948809 1]

[152000801 1]

[214809703 1]

[1780658591839 1]

I suppose it is possible to get especially lucky, and find a factor f = k*p + 1 for some k which does [i]not[/i] divide (p - 1)!. This is possible because what is important is the multiplicative order of Mod(3, f), and this can be a proper divisor of f - 1. No such luck here, though...

Thanks for your replies. I implemented this 3^p!-1 method in GWNUM. All big factors that I pump into mersenne.ca have already been found in 2008 and 2014. Eventually, I will stop running the program -- I am hoping for something big or some new factor... :smile:

I ran it up to the 11670th prime, 124247 and (partially) factored 7270 Mersenne numbers. The biggest factor was this 74 digit (composite) number:

[CODE]121021: 33679474100188397559599152526336011126242115877179269573447490457638685351[/CODE]

Is there somewhere I can upload my list to be checked for new factors? I doubt any are new :smile:

[QUOTE=paulunderwood;466016]I ran it up to the 11670th prime, 124247 and (partially) factored 7270 Mersenne numbers. The biggest factor was this 74 digit (composite) number:

[CODE]121021: 33679474100188397559599152526336011126242115877179269573447490457638685351[/CODE]

Is there somewhere I can upload my list to be checked for new factors? I doubt any are new :smile:[/QUOTE]

you could check it against the mersenne. ca lists for some : [url]http://www.mersenne.ca/exponent/121021[/url] for example

[QUOTE=science_man_88;466019]you could check it against the mersenne. ca lists: [url]http://www.mersenne.ca/exponent/121021[/url] for example[/QUOTE]

That is impractical as that would involve 7270x some number of clicks and eye-balling :ermm:

[QUOTE=paulunderwood;466020]That is impractical as that would involve 7270x some number of clicks and eye-balling :ermm:[/QUOTE]

with the "Look up many exponents:" you might be able to lessen that for the clicking in theory.

I found this: [url]https://www.mersenne.org/manual_result/[/url]. Can someone please tell me the format for factors.

[QUOTE=paulunderwood;466022]I found this: [url]https://www.mersenne.org/manual_result/[/url]. Can someone please tell me the format for factors.[/QUOTE]

[CODE]
Mxxxxxxxx has a factor: 1234567890123456789012
[/CODE]

This will give you a minimal amount of credit, though, since there is no ECM or P−1 information.