Elliptic Curve Primality Proving for Pari/GP

Atelier home

People involved

• Jared Assuncion
• Jean-Pierre Flori
• Dana Jacobsen

Tasks

Jared has an initial implementation. Will be released in a branch <? when ?>. Currently working on using better class groups.

Comments from Dana

• My standalone GMP ECPP: ecpp-dj. This seems to be the fastest open source implementation, and is competitive with Pari’s APR-CL to ~2000 digits. See, for example: graph of performance. The biggest downside (IMO) is hard-coded class polynomials. This ships with Perl’s ntheory module, so is easily available on Windows and most Linux distributions (though with the default Perl installation it uses a very small set of polynomials).

• Pari has a plethora of functions dealing with class polynomials, including getting one or all roots, finding the j-invariant, etc. This should be a massive help for implementing ECPP.

• Also included is a verifier in C that understands Primo, Primo 4.1, and MPU certificate formats. There is a description of the MPU format. If Pari/GP chooses a different certificate format, it should be a relatively simple matter to add to this verifier or make a converter (assuming the certificate has numbers similar to Morain’s papers or a well-written description of how to easily obtain them, like Primo does).

• Important to me as a user is that the certificate be well specified. Please include a single line header with format name and version number. Without that it’s impossible for a program to determine what is being given to it, or to change the output later. For running a verifier for a certificate you’ve just created is one application, storing these certificates for use many years later is a critical application, and if the output is just a jumble of numbers then it’s basically useless.