Testing Mersenne cofactors for primality?
 

I have a composite exponent n and I want to test the cofactor of 2^n-1 after dividing out 2^p-1 for each prime dividing n. What is the best way to do this?

I looked at the Cunningham project but their ranges are too small (as far as I can tell) -- my n is several million.

At the moment I'm feeding the numbers to PFGW. If there's a better approach, let me know!

(I did do a small amount of trial division with gp first.)

[QUOTE=CRGreathouse;342620]I have a composite exponent n and I want to test the cofactor of 2^n-1 after dividing out 2^p-1 for each prime dividing n.[/QUOTE]

If n has more than two prime divisors, there are more algebraic factors than this.

[QUOTE=wblipp;342637]If n has more than two prime divisors, there are more algebraic factors than this.[/QUOTE]

True -- but mine don't. :smile:

In particular I'm interested in the factorizations of [TEX]2^{p^2}-1[/TEX] for p prime (especially when p is a Mersenne exponent, because those are the only Mersenne numbers with composite exponents which might be semiprime).

Extending [URL]http://oeis.org/A156585[/URL], eh? :max:

[QUOTE=Batalov;342639]Extending [URL]http://oeis.org/A156585[/URL], eh? :max:[/QUOTE]
or [URL]http://oeis.org/A051156[/URL]

[QUOTE=CRGreathouse;342620]I looked at the Cunningham project but their ranges are too small (as far as I can tell) -- my n is several million.[/QUOTE]
Your chances of fully factorizing such a number are very slim. The reason the Cunningham project's ranges are so small is that factoring is just that hard. Yours will be more in the range of millions of digits. You basically have to hope for enough tiny factors that you find a large PRP cofactor. I'd guess that if you limit your search to 2^(p^2)-1, where p is a Mersenne prime exponent, you'll find no full factorizations (other than those already known).

[QUOTE=CRGreathouse;342620](I did do a small amount of trial division with gp first.)[/QUOTE]

Trialfactor limits I reached 2 years ago:
[URL="http://www.mersenneforum.org/showpost.php?p=244837&postcount=29"]http://www.mersenneforum.org/showpost.php?p=244837&postcount=29[/URL]

I think pfgw is about the best way to go for this.

I'd imagine that a base-3 PRP test on 2^(11213^2)-1/(2^11213-1) wouldn't be unreasonable on multi-core current hardware, and a p-1 factorisation attempt for q=2281 or q=4423 shouldn't be too painful (9941 or 11213 is more work) - you can put a premultiplier on the command line for gmp-ecm ('-go 368449') to account for the fact that q^2 | p-1

Second-stage of P-1 with gmp-ecm for 2^368449-1 seems slow; ECM with B1=10^3 is 75 seconds per curve.

gmp-ecm on 2^(2281^2)-1 at b1=1e4 b2=1678960 takes 4900 seconds for stage 1 and 8396MB and 2374 seconds for stage 2, on a 3.4GHz Sandy Bridge machine I'm trying; didn't find a factor.

On 2^(607^2)-1 at b1=1e5 it uses 3.2GB peak per process and about 2200 seconds per curve.

Testing the cofactor for rigorous primality is expensive, but PRP-testing (starting with the full LL residue) can be done similarly cheaply as cofactor-PRP testing is done for Fermat numbers (starting with a Pépin-test residue).

In the late 1990s I adapted the procedure used for Fermats to PRP-test a bunch of M(p) cofactors (and discovered numerous PRP cofactors up to my search limit of a then-lofty 20k digits or so). My version of the test needed a Pépin-style test residue to be generated for the target M(p), but Peter Montgomery [url=http://ndatech.com/mersenne/archives/digest/v01_0368.txt]showed me how to use an LL-test residue[/url], thus eliminating the redundant LL-test/Pépin-style-mod-powering effort.

[QUOTE=Mini-Geek;342656]Your chances of fully factorizing such a number are very slim.[/QUOTE]

I don't need full factorizations. I'm headstrong, not crazy. :smile:

[QUOTE=Mini-Geek;342656]I'd guess that if you limit your search to 2^(p^2)-1, where p is a Mersenne prime exponent, you'll find no full factorizations (other than those already known).[/QUOTE]

Finding what is already known is (part of) the point of this post! I don't know where to search, and I can think of nowhere better to ask than here. Edit: the answer appears to be "ATH knows all".

[QUOTE=ATH;342665]Trialfactor limits I reached 2 years ago:
[URL="http://www.mersenneforum.org/showpost.php?p=244837&postcount=29"]http://www.mersenneforum.org/showpost.php?p=244837&postcount=29[/URL][/QUOTE]

Thank you! Very helpful.

[QUOTE=fivemack;342666]I think pfgw is about the best way to go for this.

I'd imagine that a base-3 PRP test on 2^(11213^2)-1/(2^11213-1) wouldn't be unreasonable on multi-core current hardware, and a p-1 factorisation attempt for q=2281 or q=4423 shouldn't be too painful (9941 or 11213 is more work) - you can put a premultiplier on the command line for gmp-ecm ('-go 368449') to account for the fact that q^2 | p-1

Second-stage of P-1 with gmp-ecm for 2^368449-1 seems slow; ECM with B1=10^3 is 75 seconds per curve.

gmp-ecm on 2^(2281^2)-1 at b1=1e4 b2=1678960 takes 4900 seconds for stage 1 and 8396MB for stage 2 on a random machine I'm trying.[/QUOTE]

I've been working on 2281 for about a day now (~5 more to go IIRC) with pfgw. I have gmp-ecm but I don't understand the -go bit; can you explain this a bit more?

[QUOTE=ewmayer;342684]Testing the cofactor for rigorous primality is expensive, but PRP-testing (starting with the full LL residue) can be done similarly cheaply as cofactor-PRP testing is done for Fermat numbers (starting with a Pépin-test residue).

In the late 1990s I adapted the procedure used for Fermats to PRP-test a bunch of M(p) cofactors (and discovered numerous PRP cofactors up to my search limit of a then-lofty 20k digits or so). My version of the test needed a Pépin-style test residue to be generated for the target M(p), but Peter Montgomery [url=http://ndatech.com/mersenne/archives/digest/v01_0368.txt]showed me how to use an LL-test residue[/url], thus eliminating the redundant LL-test/Pépin-style-mod-powering effort.[/QUOTE]

Is there existing software that does this? In my experience what's out there is so optimized it's pretty hard to beat with hand-coding.