mersenneforum.org Testing Mersenne cofactors for primality?
 Register FAQ Search Today's Posts Mark Forums Read

 2013-06-06, 02:49 #1 CRGreathouse     Aug 2006 2×3×977 Posts 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.)
2013-06-06, 06:17   #2
wblipp

"William"
May 2003
New Haven

2×32×131 Posts

Quote:
 Originally Posted by CRGreathouse 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.
If n has more than two prime divisors, there are more algebraic factors than this.

2013-06-06, 06:28   #3
CRGreathouse

Aug 2006

586210 Posts

Quote:
 Originally Posted by wblipp If n has more than two prime divisors, there are more algebraic factors than this.
True -- but mine don't.

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

Last fiddled with by CRGreathouse on 2013-06-06 at 06:31

 2013-06-06, 07:16 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100011011100112 Posts Extending http://oeis.org/A156585, eh?
2013-06-06, 11:13   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Batalov Extending http://oeis.org/A156585, eh?
or http://oeis.org/A051156

2013-06-06, 11:55   #6
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts

Quote:
 Originally Posted by CRGreathouse I looked at the Cunningham project but their ranges are too small (as far as I can tell) -- my n is several million.
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).

2013-06-06, 13:58   #7
ATH
Einyen

Dec 2003
Denmark

1011001110112 Posts

Quote:
 Originally Posted by CRGreathouse (I did do a small amount of trial division with gp first.)
Trialfactor limits I reached 2 years ago:
http://www.mersenneforum.org/showpos...7&postcount=29

 2013-06-06, 14:26 #8 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 11000110100012 Posts 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. Last fiddled with by fivemack on 2013-06-07 at 08:53
 2013-06-06, 19:55 #9 ewmayer ∂2ω=0     Sep 2002 República de California 1137810 Posts 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 showed me how to use an LL-test residue, thus eliminating the redundant LL-test/Pépin-style-mod-powering effort.
2013-06-07, 02:05   #10
CRGreathouse

Aug 2006

2×3×977 Posts

Quote:
 Originally Posted by Mini-Geek Your chances of fully factorizing such a number are very slim.
I don't need full factorizations. I'm headstrong, not crazy.

Quote:
 Originally Posted by Mini-Geek 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).
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".

Last fiddled with by CRGreathouse on 2013-06-07 at 02:33

2013-06-07, 02:14   #11
CRGreathouse

Aug 2006

2×3×977 Posts

Quote:
 Originally Posted by ATH Trialfactor limits I reached 2 years ago: http://www.mersenneforum.org/showpos...7&postcount=29

Quote:
 Originally Posted by fivemack 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.
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:
 Originally Posted by ewmayer 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 showed me how to use an LL-test residue, thus eliminating the redundant LL-test/Pépin-style-mod-powering effort.
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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Cruelty Proth Prime Search 158 2020-07-31 22:23 preda GpuOwl 2368 2020-07-21 22:33 yih117 PrimeNet 24 2018-02-03 15:46 JeppeSN And now for something completely different 6 2017-02-24 10:17 1260 Software 17 2015-08-28 01:35

All times are UTC. The time now is 10:05.

Mon Aug 3 10:05:12 UTC 2020 up 17 days, 5:51, 0 users, load averages: 1.16, 1.20, 1.17