Primo is a primality proving program based on the ECPP (Elliptic Curve Primality Proving) algorithm. Given positive odd integers, it tests whether these integers are prime, and if they are it produces primality certificates. With PRIMO, one can check crypto-primes and prove whether they are actually prime... or not.
 |
A short description of the ECPP algorithm can be found at Elliptic Curve Primality Proving by Eric Weisstein (from MathWorld — A Wolfram Web Resource).
In addition to primality certificates, Primo generates task reports that allow to quickly see which integers were certified or not. The following report was produced while processing (for certification) a list of four 1024-bit random pseudoprime integers.
| [PRIMO - Task Report] Version=3.0.9 WebSite=http://www.ellipsa.eu/ Task=Certification ID=B2FE7043B539A Created=12/25/2009 00:00:00 AM [Common] Path=C:\primo\bench\1024\ Selected=4 Processed=4 Certified=4 Candidate #1=Certified, 5.99s Candidate #2=Certified, 7.25s Candidate #3=Certified, 6.95s Candidate #4=Certified, 5.58s [Candidate #1] Input=prime01.in Output=primo-B2FE7043B539A-001.out <See Certificate> Status=Candidate certified prime [Candidate #2] Input=prime02.in Output=primo-B2FE7043B539A-002.out Status=Candidate certified prime [Candidate #3] Input=prime03.in Output=primo-B2FE7043B539A-003.out Status=Candidate certified prime [Candidate #4] Input=prime04.in Output=primo-B2FE7043B539A-004.out Status=Candidate certified prime |
v3.0.9
- The [Comments] sections of input files are reported in the [Comments] sections of output files.
v3.0.8
- Added a Double file management option. It might be useful when dealing with very big numbers.
v3.0.7
- This version can certify integers having more than 10,000 bits.
v3.0.6
- A [Comments] section has been added to input and output files.
- An incoherence reported by Norman Luhn has been fixed (when verifying a certificate, if there was an expression in the [Candidate] section, Primo did not check whether this expression was equal to the candidate value).
v3.0.5
- A bug has been fixed. Under rare circumstances, Primo could "forget" to delete some temporary files.
- Bigger discriminant tables. The 5 tables contain more than 870,000 discriminants.
v3.0.3
- Use of 5 discriminant tables. These tables contain more than 760,000 discriminants.
- This version cannot certify integers having more than 10,000 bits.
v2.3.1
- Fixed a bug that could lead to the internal error 2.15.2. Thanks to Wolfgang Ehrhardt who reported it.
v2.3.0
- Use of new class invariants. Thanks to Michael Scott who kindly computed the needed modular functions.
v2.1.2
- Installation problem fixed. Thanks to Sergey Lopatin who reported it.
v2.1.0
- Backtrack tuning modified.
- Faster elliptic curve computations. The elliptic curve point multiplication is on average 10% faster.
- Certificate format modified. The new certificates are more compact, possibly up to 30% for the biggest ones.
- Certification reports added. Among other things, these reports contain the R values of backtracked tests (if any).
v2.0.1 (main changes since versions 1.x.x)
- New interface.
- New input file format.
Expressions like N=10^700 + 7 are allowed. - New certificate format.
- Automatic backtrack
- Verification and signature of certificates.
- The certifications are done in two phases: The 1st phase consists in finding a sequence of pseudoprimes. The 2nd phase consists in factoring class polynomials and computing elliptic curves and points.
- During the 1st phase, the work in progress is automatically saved every 10 minutes.
- It is possible (and easy) to resume an aborted certification.
Last update July 19, 2010
Copyright © 2010, Marcel Martin. All rights reserved.