mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2013-06-06, 02:49   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

587110 Posts
Default 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.)
CRGreathouse is offline   Reply With Quote
Old 2013-06-06, 06:17   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

93616 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
wblipp is offline   Reply With Quote
Old 2013-06-06, 06:28   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10110111011112 Posts
Default

Quote:
Originally Posted by wblipp View Post
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
CRGreathouse is offline   Reply With Quote
Old 2013-06-06, 07:16   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

27×71 Posts
Default

Extending http://oeis.org/A156585, eh?
Batalov is offline   Reply With Quote
Old 2013-06-06, 11:13   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Batalov View Post
Extending http://oeis.org/A156585, eh?
or http://oeis.org/A051156
science_man_88 is offline   Reply With Quote
Old 2013-06-06, 11:55   #6
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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).
Mini-Geek is offline   Reply With Quote
Old 2013-06-06, 13:58   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3·5·193 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
(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
ATH is offline   Reply With Quote
Old 2013-06-06, 14:26   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18D116 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2013-06-06, 19:55   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1143110 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2013-06-07, 02:05   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

133578 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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 View Post
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
CRGreathouse is offline   Reply With Quote
Old 2013-06-07, 02:14   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·19·103 Posts
Default

Quote:
Originally Posted by ATH View Post
Trialfactor limits I reached 2 years ago:
http://www.mersenneforum.org/showpos...7&postcount=29
Thank you! Very helpful.

Quote:
Originally Posted by fivemack View Post
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 View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
gpuOwL: an OpenCL program for Mersenne primality testing preda GpuOwl 2393 2020-08-07 17:09
Search for prime Gaussian-Mersenne norms (and G-M-cofactors) Cruelty Proth Prime Search 158 2020-07-31 22:23
Manual Testing ECM on cofactors? yih117 PrimeNet 24 2018-02-03 15:46
Feasibility of testing Fermat cofactors JeppeSN And now for something completely different 6 2017-02-24 10:17
Testing an expression for primality 1260 Software 17 2015-08-28 01:35

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

Sat Aug 15 05:16:05 UTC 2020 up 2 days, 1:51, 0 users, load averages: 2.76, 2.81, 2.80

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.