-
Notifications
You must be signed in to change notification settings - Fork 0
MichaelBell/ecpp-dj
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
ECPP-DJ: Elliptic Curve Primality Proof. Copyright 2012-2016, Dana Jacobsen (dana@acm.org). Let me know if you find this software useful, and suggestions, comments, and patches are welcome. INSTALLATION: # See note 3 at the end of this file if you want to enable APRCL. make make test (optional) ./ecpp-dj -help (shows usage) # If you plan on doing proofs with numbers over 800 digits, consider: # wget http://probableprime.org/ecpp/cpd/huge/class_poly_data.h.gz # gunzip class_poly_data.h.gz This is a standalone version of the ECPP implementation written for the Perl module Math::Prime::Util::GMP in 2013. This uses a "Factor All" strategy, and closely follows the papers by Atkin and Morain. Most of the utility functions closely follow the algorithms presented in Cohen's book "A Course in Computational Algebraic Number Theory". Almost all the factoring is done with my p-1 implementation. The ECM factoring and manipulation was heavily inspired by GMP-ECM by Paul Zimmermann and many others. This includes a BPSW test (strong PRP-2 test followed by extra strong Lucas-Selfridge test). We use this to (1) detect composites, and (2) prove small numbers. BPSW has no counterexamples below 2^64, and this implementation has been verified against Feitsma's database. Using the -c option enables certificate generation. The format is described in the file proof-text-format.txt. Two verification programs are supplied: verify-cert.pl (Perl) vert.c (C+GMP) The Makefile should create the 'vcert' executable for you. Both programs will read both the MPU format and the PRIMO format. Performance is quite good for most sub-1000 digit numbers, but starts getting uneven over 500 digits. Much more work is possible here. For production proving of multi-thousand digit numbers, I recommend: Primo http://www.ellipsa.eu/public/primo/primo.html because of its large speed advantage for 1000+ digit numbers, especially on multi-processor machines. Quick performance comparisons: - Primo is slower under ~500 digits, *much* faster as input grows. - GMP-ECPP 2.49 is very, very slow. Nearly unusable once over 500 digits. - Morain's ancient 6.4.5a ECPP is similar under 300 digits, but gets slower. - David Cleaver's mpz_aprcl is a tiny bit slower under ~500 digits, but gets faster for larger inputs (2-3x faster at 2000 digits). Note that APR-CL does not produce a certificate. - Using the latest GMP (e.g. 6.0.0a or later) will substantially help performance of this code as well as mpz_aprcl. - AKS is not currently a viable method, with all known implementations being millions of times slower than alternative methods (ECPP or APR-CL). This code includes the fastest AKS implementation I know, but this still holds. Some areas to concentrate on: 1. The polynomials. We ought to generate Weber polynomials on the fly. I think it still makes a lot of sense to include a fixed set (e.g. all polys of degree 6 or smaller) for speed. However the lack of polynomials is a big issue with titanic numbers, as we run a good chance of not finding an easily splitable 'm' value and then get bogged down in factoring. The CM package from http://cm.multiprecision.org/ would be an excellent choice, with my only concern being the large dependency chain. 2. The factoring. In most cases this will stay in factoring stage 1 the entire time, meaning we are running my _GMP_pminus1_factor code with small parameters. Optimizing this would help (the stage 2 code certainly could be faster). I have tried GMP-ECM's n-1 and it is quite a bit slower for this purpose (let me be clear: for large B1/B2 values, GMP-ECM rocks, but in this application with small B1/B2, it ran slower for me). If you add the define USE_LIBECM, then GMP-ECM's ECM is used. This will probably be slower. Where using GMP-ECM would really help (I think) is in later factoring stages where we're in trouble and need to work hard to find a factor since there just aren't any easy ones to be found. At this point we want to unleash the full power of GMP-ECM. I have not tested this in this application, but for general factoring, GMP-ECM is much faster than my ECM code so I would expect something similar here. Note that this interacts with #1, as if we can efficiently generate polys or have a giant set, then we must trade off doing more factoring vs. more polys. Morain's fastECPP, for example, uses stupendously more discriminants than we do, so factoring isn't a big issue for them. They have very different polynomials and root finding algorithms however. 3. Parallelism. Currently the entire code is single threaded. There are many opportunities here. - Something I think would be useful and not too much work is parallelizing the dlist loop in ecpp_down, so all the discriminants can be searched at once. A more complicated solution would be a work queue including pruning so we could recurse down many trees at once. - If we have to run ECM, then clearly we can run multiple curves at once. - Finally, once we've hit STEP 2 of ecpp_down, we could do curve finding for the entire chain in parallel. This would be especially useful for titanic numbers where this is a large portion of the total time. 4. ecpp_down. There are a lot of little things here that can have big impacts on performance. For instance the decisions on when to keep searching polys vs. backtracking. The current code, for smallish numbers, will use a cheap factoring stage zero for a while before switching to stage 1. There is a lot of repeated work here that a rewrite could avoid. 5. The poly root finding takes a long time for large degree polys, and perhaps we could speed it up. Note 1: AKS is also included and you can use it via the '-aks' option. The default implentation includes improvements from Bernstein and Voloch, with a tuning heuristic from Bornemann. It is much faster than the version used by Brent (2006) for instance, but it is still very slow. Note 2: You can also force use of the BLS75 theorem 5/7 n-1 proof using the '-nm1' option. This is good for up to 70-80 digits or so. It performs similarly to Pari's n-1 implementation (though is presumably very different internally). Note 3: You can also run APRCL. Get WraithX's code from: http://sourceforge.net/projects/mpzaprcl/ , put the files in this directory, then add -DUSE_APRCL to the DEFINES in the Makefile. The '-aprcl' option will now be available.
About
Fork of standalone ecpp-dj
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published