leto / math--primality

Advanced primality-checking algorithms
http://duke.leto.net
8 stars 13 forks source link

Implement ECPP #13

Open danaj opened 11 years ago

danaj commented 11 years ago

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 commented 11 years ago

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

danaj commented 11 years ago

(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 commented 11 years ago

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:

leto commented 11 years ago

Thank you very much for the updates! They are fascinating :+1: