mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2010-11-17, 06:25   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10110111001102 Posts
Default Primality proving

I'm sure this is very basic, but where can I find Linux software for proving primality of large general numbers? Fran├žois Morain's ECPP is limited to about 2000 decimal digits. Pari/GP is happy to attempt a primality proof for large numbers, but its algorithms are not competitive at that size.

Last fiddled with by CRGreathouse on 2010-11-17 at 06:25
CRGreathouse is offline   Reply With Quote
Old 2010-11-17, 06:46   #2
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

227810 Posts
Default

GMP-ECPP?

http://sourceforge.net/projects/gmp-ecpp/
ixfd64 is online now   Reply With Quote
Old 2010-11-17, 07:16   #3
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I'm sure this is very basic, but where can I find Linux software for proving primality of large general numbers? Fran├žois Morain's ECPP is limited to about 2000 decimal digits. Pari/GP is happy to attempt a primality proof for large numbers, but its algorithms are not competitive at that size.
Primo has been used to effect proof of very large (by general-form standards) numbers as great as 11,467 digits (the current Primo record); that particular number was done with a somewhat arcane process by which Primo can be run over multiple cores, but it was doable in a number of months (though as I understand it, it required a lot of babysitting). This is the fastest generally-available way to prove large PRPs.

Numbers as big as 20,562 digits have been proven prime with the FastECPP software distributed over multiple computers, albeit with what appears to be a specially-modified, not-generally-available version of the program.
mdettweiler is offline   Reply With Quote
Old 2010-11-17, 14:27   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
Primo has been used to effect proof of very large (by general-form standards) numbers as great as 11,467 digits (the current Primo record); ... This is the fastest generally-available way to prove large PRPs.
Primo is natively a Windows application. He's specifically asking for Linux software. Unless it's still faster than other options when run through Wine, or there's a Linux port I'm unaware of, Primo isn't a good option in this case.
Mini-Geek is offline   Reply With Quote
Old 2010-11-17, 15:46   #5
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

17×593 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Primo is natively a Windows application. He's specifically asking for Linux software. Unless it's still faster than other options when run through Wine, or there's a Linux port I'm unaware of, Primo isn't a good option in this case.
Or unless he wants to run a Windows OS on a virtual machine. I run XP on a Fedora-hosted VirtualBox when Windoze is particularly necessary. Virtualization overhead seems to be reasonably small and XP in that environment appears to be much more compatible with XP on a real machine than is Wine on a general Linux box.

Paul
xilman is offline   Reply With Quote
Old 2010-11-17, 20:29   #6
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Primo is natively a Windows application. He's specifically asking for Linux software. Unless it's still faster than other options when run through Wine, or there's a Linux port I'm unaware of, Primo isn't a good option in this case.
As Paul suggested, a VM could do the trick, though Wine has been used before with success to run Primo on Linux. Gary (a.k.a. gd_barnes) did a large proof for the Five or Bust project that way on one of his Linux boxes and from what I observed the overhead was minimal if at all present. I'm not sure how this compares with a virtual machine, but it was definitely more convenient to set up and use.

Last fiddled with by mdettweiler on 2010-11-17 at 20:29
mdettweiler is offline   Reply With Quote
Old 2010-11-18, 14:57   #7
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

17·31 Posts
Default

I could indeed get Primo to work with wine.

BTW long ago (~2001) I ran some command-line .exe number crunching program under Wine and they were faster than under Windows.
ldesnogu is offline   Reply With Quote
Old 2011-01-23, 04:03   #8
davar55
 
davar55's Avatar
 
May 2004
New York City

3·1,409 Posts
Default

Is primo good for primes less than ten million?
davar55 is offline   Reply With Quote
Old 2011-01-29, 08:22   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

32×631 Posts
Default

Quote:
Originally Posted by davar55 View Post
Is primo good for primes less than ten million?
For primes that small http://en.m.wikipedia.org/wiki/Mille...primality_test shows what bases need testing for a number to be definitely prime. This should be faster than primo though trial factoring m
ight
be faster still.
henryzz is offline   Reply With Quote
Old 2011-01-29, 11:06   #10
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default

For potential prime numbers less than 10^300,Pari-GP's isprime() function is reasonably fast(altough it doesn't print out a certificate). Pari-GP runs on linux and you can get it from:
http://pari.math.u-bordeaux.fr
(or install it via your distribution's package manager)
nuggetprime is offline   Reply With Quote
Old 2011-01-29, 17:04   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

Quote:
Originally Posted by nuggetprime View Post
For potential prime numbers less than 10^300,Pari-GP's isprime() function is reasonably fast(altough it doesn't print out a certificate).
Quite fast even -- for numbers of 100-250 digits it's possibly the fastest out there.

It does have the ability to certify primality with isprime(n, 1), though it's very slow.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Unit Differences for Primality Proving Trejack Miscellaneous Math 11 2016-05-12 04:15
Use Pepin's Tests for proving primality of Mersenne numbers ? T.Rex Math 12 2016-04-03 22:27
Primality proving of DB factors? jasonp FactorDB 3 2011-10-17 18:04
"New primality proving test from Alex Petrov" ewmayer Math 11 2007-04-23 19:07
fastest general number primality-proving algorithm? ixfd64 Math 3 2003-12-17 17:06

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

Fri Jul 10 05:41:54 UTC 2020 up 107 days, 3:14, 0 users, load averages: 1.34, 1.23, 1.23

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.