Primality proving

[CRGreathouse]

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.

[ixfd64]

GMP-ECPP?

http://sourceforge.net/projects/gmp-ecpp/

[mdettweiler]

Originally Posted by CRGreathouse

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.

[TimSorbet]

Originally Posted by mdettweiler

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.

[xilman]

Originally Posted by Mini-Geek

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

[mdettweiler]

Originally Posted by Mini-Geek

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.

[ldesnogu]

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.

[davar55]

Is primo good for primes less than ten million?

[henryzz]

Originally Posted by davar55

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.

[nuggetprime]

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)

[CRGreathouse]

Originally Posted by nuggetprime

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.