Fastest software for Mersenne primality test?

JonathanM · 2012-01-25, 21:31

What is the fastest software for checking if a Mersenne number is prime? (has to be free/non-binding, preferably for Windows 64 bit)

Also, approximately how long does checking a 1 billion digit Mersenne prime take?

firejuggler · 2012-01-25, 21:48

llravx and aproximately 1 year for current harware.

cheesehead · 2012-01-25, 22:15

Quote:

Originally Posted by firejuggler

llravx

Oh? How does llravx run faster than prime95 when testing a Mersenne number?

Dubslow · 2012-01-25, 22:24

LLR tests Mersenne numbers?

Prime95 is the fastest as far as x86 processors go, and it is mostly free, except that if you discover a prime with it, you must abide by the Great Internet Mersenne Prime Search prize-distribution rules (you'll get a third of the EFF prize for a 100M digit prime, or a few thousand dollars or so for just a 'regular' prime).

If even that is too much of a restriction (it isn't really, I encourage you to read http://mersenne.org/legal) then try Mlucas or Glucas which are programmed in Fortran and C respectively (as opposed to x86 Assembly for Prime95). I am unsure about their license terms, though if I had to guess I'd say they're free (as in freedom, and definitely free-gratis).

Prime95 includes 64 bit optimizations, although they're not really significant for LL tests.

As for a billion digit number, I highly recommend you give up any hope of testing it with any program available. It will be impossible for (AT LEAST) the next 20 years. For more details, see here and here. From the second page: You're looking at around 95,000 GHz days to do one test. One core of my Intel i7-2600K is able to do ~5 GHz-Days per day, that would take me around 50 years. (You could use all four cores, but you'd get less than 15 GHz-Days per day, because the LL test isn't very well parallelizable).

*Note: It also just occurred to me that Prime95 (and presumably the other testing programs) can't even test numbers that are a billion digits long. The maximum Prime95 exponent is 596M, whereas the lowest prime exponent that produces a billion digits is 3,321M. Note the order of magnitude difference of the exponents.

**Note 2: I also just realized that this link from above is not an exponent to be tested, because that link shows it's already been factored.

firejuggler · 2012-01-25, 22:33

cause prime95 v26.6 doesn't support avx?

chalsall · 2012-01-25, 23:23

Quote:

Originally Posted by Dubslow

Prime95 is the fastest as far as x86 processors go, and it is mostly free, except that if you discover a prime with it, you must abide by the Great Internet Mersenne Prime Search prize-distribution rules (you'll get a third of the EFF prize for a 100M digit prime, or a few thousand dollars or so for just a 'regular' prime).

Let us run a thought experiment...

Imagine that someone can factor really quickly... Perhaps by using Quantum Uncertainty...

And imagine that a few thousand dollars or so was small change.

Would they advertise that ability?

Dubslow · 2012-01-26, 00:01

Quote:

Originally Posted by Dubslow

Prime95 is the fastest as far as x86 processors go, and it is mostly free, except that if you discover a prime with it, you must abide by the Great Internet Mersenne Prime Search prize-distribution rules (you'll get a third of the EFF prize for a 100M digit prime, or a few thousand dollars or so for just a 'regular' prime).

***Note 3: As far as ~~anyone~~ the public knows.

Uncwilly · 2012-01-26, 00:38

Quote:

Originally Posted by JonathanM

What is the fastest software for checking if a Mersenne number is prime? (has to be free/non-binding, preferably for Windows 64 bit)

Also, approximately how long does checking a 1 billion digit Mersenne prime take?

Quote:

Originally Posted by firejuggler

llravx and aproximately 1 year for current harware.

Basically nothing handles LL testing of numbers that large. And it would take too long.
From the wiki:

Quote:

There isn't hope of really finding such a prime with today's technology and algorithms. A Lucas-Lehmer primality test is estimated to require 852 years.

Dubslow · 2012-01-26, 04:06

I actually got around 50 years on one core of my Sandy Bridge.

Uncwilly · 2012-01-26, 05:57

Quote:

Originally Posted by Dubslow

I actually got around 50 years on one core of my Sandy Bridge.

What FFT size are you setting it for?

Dubslow · 2012-01-26, 18:07

Using James' estimate of 95K GHzDays, and assuming I can get 5/day.
http://www.wolframalpha.com/input/?i...+days+to+years
Maybe closer to 55 or 60, but still way less than 100.

2012-01-25, 21:31	#1
JonathanM Jan 2012 1 Posts	Fastest software for Mersenne primality test? What is the fastest software for checking if a Mersenne number is prime? (has to be free/non-binding, preferably for Windows 64 bit) Also, approximately how long does checking a 1 billion digit Mersenne prime take?

2012-01-25, 21:48	#2
firejuggler "Vincent" Apr 2010 Over the rainbow 2²·7·103 Posts	llravx and aproximately 1 year for current harware. Last fiddled with by firejuggler on 2012-01-25 at 21:49

2012-01-25, 22:24	#4
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	LLR tests Mersenne numbers? Prime95 is the fastest as far as x86 processors go, and it is mostly free, except that if you discover a prime with it, you must abide by the Great Internet Mersenne Prime Search prize-distribution rules (you'll get a third of the EFF prize for a 100M digit prime, or a few thousand dollars or so for just a 'regular' prime). If even that is too much of a restriction (it isn't really, I encourage you to read http://mersenne.org/legal) then try Mlucas or Glucas which are programmed in Fortran and C respectively (as opposed to x86 Assembly for Prime95). I am unsure about their license terms, though if I had to guess I'd say they're free (as in freedom, and definitely free-gratis). Prime95 includes 64 bit optimizations, although they're not really significant for LL tests. As for a billion digit number, I highly recommend you give up any hope of testing it with any program available. It will be impossible for (AT LEAST) the next 20 years. For more details, see here and here. From the second page: You're looking at around 95,000 GHz days to do one test. One core of my Intel i7-2600K is able to do ~5 GHz-Days per day, that would take me around 50 years. (You could use all four cores, but you'd get less than 15 GHz-Days per day, because the LL test isn't very well parallelizable). Note: It also just occurred to me that Prime95 (and presumably the other testing programs) can't even test numbers that are a billion digits long. The maximum Prime95 exponent is 596M, whereas the lowest prime exponent that produces a billion digits is 3,321M. Note the order of magnitude difference of the exponents. Note 2: I also just realized that this link from above is not an exponent to be tested, because that link shows it's already been factored. Last fiddled with by Dubslow on 2012-01-25 at 22:31*

2012-01-26, 18:07	#11
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	Using James' estimate of 95K GHzDays, and assuming I can get 5/day. http://www.wolframalpha.com/input/?i...+days+to+years Maybe closer to 55 or 60, but still way less than 100. Last fiddled with by Dubslow on 2012-01-26 at 18:09

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New Mersenne primality test	Prime95	Miscellaneous Math	19	2014-08-23 04:18
A (new) old, (faster) slower mersenne-(primality) PRP test	boldi	Miscellaneous Math	74	2014-04-17 07:16
The fastest primality test for Fermat numbers.	Arkadiusz	Math	6	2011-04-05 19:39
LLT Cycles for Mersenne primality test: a draft	T.Rex	Math	1	2010-01-03 11:34
Mersenne Primality Test in Hardware	Unregistered	Information & Answers	4	2007-07-09 00:32

2012-01-25, 22:33	#5
firejuggler "Vincent" Apr 2010 Over the rainbow 2²·7·103 Posts	cause prime95 v26.6 doesn't support avx?

2012-01-26, 04:06	#9
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 16065₈ Posts	I actually got around 50 years on one core of my Sandy Bridge.