20130606, 02:49  #1 
Aug 2006
3×1,993 Posts 
Testing Mersenne cofactors for primality?
I have a composite exponent n and I want to test the cofactor of 2^n1 after dividing out 2^p1 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.) 
20130606, 06:17  #2 
"William"
May 2003
New Haven
23×103 Posts 

20130606, 06:28  #3  
Aug 2006
3·1,993 Posts 
Quote:
In particular I'm interested in the factorizations of 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 20130606 at 06:31 

20130606, 07:16  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,229 Posts 
Extending http://oeis.org/A156585, eh?

20130606, 11:13  #5  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:


20130606, 11:55  #6 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
4,271 Posts 
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).

20130606, 13:58  #7 
Einyen
Dec 2003
Denmark
3,253 Posts 
Trialfactor limits I reached 2 years ago:
http://www.mersenneforum.org/showpos...7&postcount=29 
20130606, 14:26  #8 
(loop (#_fork))
Feb 2006
Cambridge, England
14464_{8} Posts 
I think pfgw is about the best way to go for this.
I'd imagine that a base3 PRP test on 2^(11213^2)1/(2^112131) wouldn't be unreasonable on multicore current hardware, and a p1 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 gmpecm ('go 368449') to account for the fact that q^2  p1 Secondstage of P1 with gmpecm for 2^3684491 seems slow; ECM with B1=10^3 is 75 seconds per curve. gmpecm 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 20130607 at 08:53 
20130606, 19:55  #9 
∂^{2}ω=0
Sep 2002
República de California
26647_{8} Posts 
Testing the cofactor for rigorous primality is expensive, but PRPtesting (starting with the full LL residue) can be done similarly cheaply as cofactorPRP testing is done for Fermat numbers (starting with a Pépintest residue).
In the late 1990s I adapted the procedure used for Fermats to PRPtest a bunch of M(p) cofactors (and discovered numerous PRP cofactors up to my search limit of a thenlofty 20k digits or so). My version of the test needed a Pépinstyle test residue to be generated for the target M(p), but Peter Montgomery showed me how to use an LLtest residue, thus eliminating the redundant LLtest/Pépinstylemodpowering effort. 
20130607, 02:05  #10  
Aug 2006
3·1,993 Posts 
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". Last fiddled with by CRGreathouse on 20130607 at 02:33 

20130607, 02:14  #11  
Aug 2006
5979_{10} Posts 
Quote:
Quote:
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2751  20220103 14:57 
Search for prime GaussianMersenne norms (and GMcofactors)  Cruelty  Proth Prime Search  158  20200731 22:23 
Manual Testing ECM on cofactors?  yih117  PrimeNet  24  20180203 15:46 
Feasibility of testing Fermat cofactors  JeppeSN  And now for something completely different  6  20170224 10:17 
Testing an expression for primality  1260  Software  17  20150828 01:35 