Collection of primality certificates and an open source tool that can be used to verify them.

Application can verify Atkin-Goldwasser-Kilian-Morain Certificate, Pocklington certificate and Brillhart, Lehmer, Selfridge certificate (Theorem 15) based primality proofs, commonly generated by the Primo application.

Read more on primality testing

When verifying primality certificates, it also checks if the number is not vulnerable to Special Number Field Sieve, as primes of this form have effective bit size reduced by a third (i.e. 3072 bit SNFS-vulnerable prime is about as easy to attack as a 2048 bit prime).

Download the most recent release .whl file from github:

curl -s https://api.github.com/repos/tomato42/ecpp-verifier/releases/latest \
| grep "browser_download_url.*whl" \
| cut -d : -f 2,3 \
| tr -d \" \
| wget -i -

Or manually, by visiting latest release and downloading the .whl file from there.

Install it using pip:

pip3 install ecpp-*.whl

Verify that it can be executed:

ecpp --help

Install gmpy2 package to double the performance of certificate verification:

pip3 install gmpy2

Clone this repository:

git clone https://github.com/tomato42/ecpp-verifier.git
cd ecpp-verifier

Install dependencies (for example on Fedora):

dnf install python3-ecdsa python3-gmpy2

Or from PyPI:

pip3 install ecdsa[gmpy2]

(Note: as gmpy2 is a binary package you will need to install development headers for python and the gmp library. Alternatively, you can skip installation of gmpy2 at the cost of halved performance).

Make sure you have installed ecdsa package version 0.15 or newer. Older versions have significant performance issues and certificate verification will take ages.

Run ecpp for the first time:

PYTHONPATH=src ./ecpp --help

To check if you have primality certificates for all the primes in your OpenSSH moduli file, you can use ecpp with -m switch:

ecpp -m /etc/ssh/moduli

This will succeed for example for moduli file released with OpenSSH 8.2p1, listing certificates for each prime.

To verify the matching certificates you can combine the -m switch with the -v switch:

ecpp -m /etc/ssh/moduli -v

This will succeed if the script finds matching certificates and verifies them as valid.

Note: it will require significantly more time to execute than just the -m option. It's also a single-threaded process, see #12.

If there are some primes without primality certificates, you can generate input files for Primo into in/ directory.

ecpp -m /etc/ssh/moduli -p

Now, open Primo downloaded from link above, extract archive and start GUI on a reasonably powerful machine (at this moment, Primo can work with up to 64 cores).

• From Menu, select Setup..., set number of cores your system have (hyper-threading is not much useful)
• In tab Certification, select 3000 dd (decimal digits) in Trial Division Parameters and click Build prime table button.
• Then click Load. Select all the .in files in the in/ directory created by the previous step and click Open.
• After long time, you will get certificates in *.out files in the same directory.

In previous step, we got certificates for primes. Now we need to verify them. This can be done with the following command for one certificate:

ecpp -i in/primo-B412D0397A9D9-07E.out

The job can be simply parallelized so if we want to verify all the certificates we got, we can use GNU parallel to get results in parallel, in this example using 16 parallel processes:

parallel -j16 "echo {} && ecpp -i {}" ::: in/*.out

Now, we can add the primality certificates to src/ecpp/certificates/ directory.

Running ecpp again as in the first example should confirm we have a certificate for each prime in the moduli file now.

ecpp -m /etc/ssh/moduli