Implement ECPP

[danaj]

I just released a version of Math::Prime::Util::GMP with ECPP (Elliptic Curve Primality Proving). With a small set of fixed determinants, it's good for proving 700-bit (216 digit) primes in ~1 second, including a certificate. Adding this to Math::Primality would be nice.

There are a number of improvements that could be made to my implementation to support larger sizes -- at 400 digits or so it occasionally gets bogged down in factoring due to a FPS strategy (basically go depth first and don't backtrack even if we get stuck trying to crack factors off huge numbers that won't cooperate). Adding simple backtracking would help, but once we get much over 500 digits that starts breaking down also (if we get stuck at the top level there's nowhere to backtrack to). I can add more fixed discriminants which delays the issue at the expense of memory.

The algorithm itself is relatively straightforward, but it needs a lot of support polynomial functions as well as some basic factoring (a good Pollard n-1 works wonders, and a good ECM is recommended also). Some of these have CPAN modules that may or may not work (e.g. polynomial root finding), and a lot of the rest should be in Math::Polynomial (i.e. it's already there or should be added if not).

In the long run, making your own Hilbert and Weber polynomials using Math::MPFR would be a big win, especially if you have fast root finding.

[leto]

Wow! Very exciting. Can you provide references for Weber polynomials?

[danaj]

(Math::Prime::Util::GMP is where is it implemented, not Math::Prime::Util -- the latter will call it and will verify the proofs, but doesn't have code itself).

Atkin, Morain 1992 (Elliptic Curves and Primality Proving -- the primary ECPP reference)
Henri Cohen "A Course in Computational Algebraic Number Theory", 7.6.3 "Computing Weber Class Polynomials"
Valente's 1992 thesis (RPI)
Kaltofen, Valente, Yui 1989
Konstantinou, Stamatiou, Zaroliagis (CHES 2002)

I don't use them when d = 3 mod 8 because the degree is 3x higher so mapping roots gets really complicated, and when d = 0 mod 3 (they tend not to work, and Atkin/Morain mention that we assume d != 0 mod 3).

SAGE will calculate Hilbert Polynomials quite quickly, and I have a table with output of 0-10k from http://hilbert-class-polynomial.appspot.com/ as well.

[danaj]

I've made quite a few changes since the last comments. My ECPP now uses FAS instead of FPS, which lets it backtrack. With a decent size poly database it does pretty well to 2000 or so decimal digits. I haven't made runs past that size. Primo is still a lot faster, but it isn't open source. Based on the papers, Morain's fastECPP is much more sophisticated and more appropriate for really big numbers, but it is not available in any form.

I'm using Weber polys for everything other than d = 3 mod 8 now.

Strategies for polynomials include:

• Maintain a big database and attach it to the code. I do this, after trimming the database to some target size.
• Maintain a big database and read it as necessary. I will probably turn my standalone code into this.
• Keep the degree 1-4 polys on hand, and calculate the rest as needed. You'll probably quickly find yourself wanting to use better invariants than Hilbert.
• Keep the degree 1-4 polys on hand, and get the rest as needed from some sort of web service. E.g. http://echidna.maths.usyd.edu.au/echidna/dbs/index.html. This keeps you from having to calculate or store giant poly databases. The downside is that you get 2 weeks into a proof and then find you can't retrieve the necessary polynomial coefficients for the next step... ouch.

[leto]

Thank you very much for the updates! They are fascinating 👍