ECPP-DJ

[danaj]

As mentioned on the Primo thread, I wrote an ECPP implementation for my Math::Prime::Util Perl module, and thought I'd release it as a standalone program. It's open source so please send me comments, suggestions, patches, etc. It should be portable to any platform with a standard C compiler and GMP. I've tested it on various Linuxes (x86, HP-PA, SPARC, Power7), Cygwin, Win32 (with gcc) and I have reports showing it working on FreeBSD, Solaris, OpenBSD, NetBSD, Dragonfly BSD, and Debian on 14 different platforms.

Download link: ecpp-dj-1.00.tar.gz

This also includes options for AKS and n-1 (BLS75 theorem 5 or 7) if you really want to play with them. Everything is single threaded. I should probably include an option for just BPSW testing (the code includes lots of primality testing pieces, all of which can be called from the Perl module, but not the standalone executable).

The good: It's open source. It's very fast for "small" numbers. It has lots of room for improvement. It outputs certificates (though the standalone version's cert format is lame and needs to be improved).

The bad: If you don't care about open source, then Primo will meet your needs and be a lot faster. I use a fixed set of discriminants, so large values can get stuck in factoring. This seems to happen very rarely under 500 digits, but becomes more of an issue with larger numbers. Because of this, the expected run time isn't very predictable once over 500 digits or so.

The certificate output from this version is really lame -- it's a dump of the text one of my Perl routines parses into a defined structure. It'd be nice to have it output Primo certificate format, but that isn't possible without completely changing my curve selection methods. Suggestions are welcome for something prettier.

Alternatives:

• Primo. Primo is awesome. Not open source however.
• Yafu 1.34 includes an APRCL implementation from WraithX. I haven't looked at the code, but this is really amazing. Like Pari's APRCL it has quite predictable performance with digit size. On my computer it is slower than my ECPP for numbers under 500 digits, and doesn't give certificates. Once in the titanic number range it's probably faster on average and a lot faster at the extremes.
• GMP-ECPP. Big kudos to the team -- it is an open source ECPP implementation and it works. However, it is pretty slow. Plugging in GMP-ECM for factoring would help a lot.
• Pari/GP. Includes n-1 and APR-CL (as of version 2.3). The n-1 is pretty comparable in speed to my BLS75, and both start straining after 80 digits or so. The APR-CL implementation follows the same trend I saw with Yafu/WraithX's APRCL -- it's a bit slower up to 500 or so digits, but a very smooth progression. After that my code is up and down. There is no certificate.

Let me know if there are others. I've seen various projects (e.g. Lindeman et al. student project modifying GMP-ECPP, Studholme's decade old ECPP using NTT) but haven't compared them.

Timing using the example numbers WraithX posted for his APR-CL implementation. ECPP-DJ v1.0, Yafu 1.34.5 APR-CL, GMP-ECPP atkin243. Run on an i7-3930k. GMP-ECPP uses random values for various things (ECM factors, root splitting, point selection) so will differ in time each run. ECPP-DJ uses randomness in point selection, root finding, and factoring if we reach stage 3 (only the last of these examples goes past stage 1), so it will be slightly different each run, but not much.

                                   :  ECPP-DJ :    YAFU  : GMP-ECPP
 100 digits : 5^143+2              :    0.07s :    0.23s :     7.22s
 150 digits : 3^313*4+5            :    0.18s :    0.59s :    75.58s
 200 digits : 7^235*9+2            :    0.42s :    1.33s :   170.44s
 250 digits : 5^356*8-1            :    0.90s :    2.72s :   312.83s
 300 digits : 424^114+3            :    2.35s :    5.13s :   148.39s
 350 digits : 1160^114+7           :    4.14s :    9.85s : >1700s
 400 digits : (291^163-1)/290      :    8.98s :   15.51s
 450 digits : 232^190+7            :   10.49s :   24.45s
 500 digits : 1014^166+7           :   22.24s :   36.13s
 550 digits : 10^549*9-7           :   58.20s :   59.35s
 600 digits : 1432^190+7           :   67.74s :   82.61s
 650 digits : 2^2159+375           :  118.91s :  101.04s
 700 digits : (157^319+319^157)/28 :  152.10s :  162.82s
 750 digits : 10^749*2+89          :  162.03s :  208.16s
 800 digits : (10^799*61-7)/9      :  174.49s :  284.33s
 850 digits : 2^2821-183           :  367.20s :  388.98s
 900 digits : (24^653-1)/23        :  367.68s :  444.32s
 950 digits : 10^949*4-9           :  819.76s :  592.22s
1000 digits : 10^999+7             : 7325.03s :  666.52s

The 1000-digit number caused my implementation quite a bit of trouble, as it ended up going to factoring stage 6 before finally finding a 'q' value. Adding discriminants or being able to generate Weber polynomials at runtime would fix this.

This software was developed with the help of many resources. Cohen's book "A Course in Computational Algebraic Number Theory" and the papers by Atkin and Morain were exceptionally helpful. Crandall & Pomerance's book was useful. Lots of other papers helped. GMP is awesome. GMP-ECM and GMP-ECPP were very helpful.

[yoyo]

Thanks for starting this thread. I don't have any clue about the math behind prime certificate generation and prime proving and would enjoy that other experts join the discussion and generate a good open source tool for it.

I'm really interested to use it to set up a Boinc project to check PRP and generate prime certificates and store them in the factordb. This would be also for PRP with more than 1000 digits.

yoyo

[bearnol]

Hi again yoyo et al.
I'd like to mention 3 things:
(1) If you're using an ECPP prover with factordb.com ( sounds like a cool idea, btw) you don't actually need to fully certify each PRP, just the _first_ step for each number ie you can just use GMP-ECPP's -o switch ( or similar). That way the factordb can store all the chains
(2) I _believe_ I've made GMP-ECPP reasonably state-of-the-art, at least wrt larger numbers, especially in the light of point (3) below
(3) are we 100% sure that Primo, and other FAS provers, don't give false positives. I'd like to see Primo runs on some known _pseudo_primes from the factordb. I believe the math requires all parts of a step before one can claim primality, and I don't see how this is compatible with FAS.
J

[danaj]

Originally Posted by bearnol

Hi again yoyo et al.
I'd like to mention 3 things:
(1) If you're using an ECPP prover with factordb.com ( sounds like a cool idea, btw) you don't actually need to fully certify each PRP, just the _first_ step for each number ie you can just use GMP-ECPP's -o switch ( or similar). That way the factordb can store all the chains

I'm not involved in factordb so maybe I'm not following this. You could stop partway, but why not just do the full proof and enter every q value? That way factordb gets the whole chain entered, but we also know each value actually is prime and has a full proof.

(2) I _believe_ I've made GMP-ECPP reasonably state-of-the-art, at least wrt larger numbers, especially in the light of point (3) below

I tested vs. atkin243 which was the latest version I saw. Even using small POLY_SIZE, -B, -p, and -e values it is still 100x slower than ecpp-dj, and much slower for large values. I haven't seen any newer code -- is it somewhere other than Sourceforge?

Edit: Perhaps you can give times you see with GMP-ECPP for the 250, 300, and 350 digit numbers above, so we can be on the same page with times. Perhaps I'm missing something.

(3) are we 100% sure that Primo, and other FAS provers, don't give false positives. I'd like to see Primo runs on some known _pseudo_primes from the factordb. I believe the math requires all parts of a step before one can claim primality, and I don't see how this is compatible with FAS.
J

I have code for FPS and it's easily callable (call the _GMP_ecpp_fps function instead of _GMP_ecpp). I didn't put a command line option for it though. It's great up to 200ish digits, which is where it would get bogged down in factoring pretty often. FAS gives cheap and easy backtracking, and I stopped working on my FPS routine.

I can't answer for Primo, but I'd be quite surprised if he hadn't thought of this. Especially since it generates certificates that have been independently verified.

The math does require all parts of a step -- FAS just does them in a different order. I do check the curve finding, and if it failed, then I invalidate that D and start looping again (this is disastrous for performance, and typically would indicate the polynomial data is incorrect). I've never seen it happen with the current data set, but it could -- but as noted it will not claim primality. GMP-ECPP (atkin243) has some bugs (e.g. the polynomial root finder) that will make the curve finding fail when it really shouldn't -- this doesn't make it produce incorrect results, but does make it waste time and maybe gives the impression that FAS would have to deal with this a lot.

I'd also point out that we should spend some time on the certificate validation. If we believe that is correct, then it doesn't matter how we generate the certificates -- FPS, FAS, or Ouija board. All results should go through a verifier before being entered (and once entered the certificate should be readily available for a user to verify themselves).

My code obviously doesn't have the use that Primo has, so clearly I'd feel better with validation and would want to hear about anything that failed, since it is really important to not generate bad certificates. It's ok (if disappointing) if it exits with "probably prime", but it should never say "definitely prime" unless it really is.

A test suite would be nice too.

[henryzz]

factordb uses an independently written certificate checker so primo produces correct results.

[chris2be8]

How does ECPP from http://www.lix.polytechnique.fr/Labo...p.english.html compare for speed etc?

Would it be possible to use ECM on a GPU to speed up the process (sorry if I've misunderstood the relation between ECM for factoring and primality proving)?

Chris

[henryzz]

The other one worth adding to the table is primo.

[danaj]

Originally Posted by chris2be8

How does ECPP from http://www.lix.polytechnique.fr/Labo...p.english.html compare for speed etc?

I tried running that in early May and I didn't get it to run (it segfaults after entering the number). With some help from strace I've got it running now (v6.4.5a). I wrote in the comments at the top of ecpp.c:

 * It is far, far slower than PRIMO.
 * I suspect it is slower than the 10-20 year old work of François Morain.

purely based on what he describes in his papers.

For his 20 512-bit examples, I get about the same time (average 0.25s per number). His larger 222-digit examples takes 0.91s with his software, 0.93s with mine. The 400 digit example from the first post ((291^163-1)/290) takes 50.9s with his software, 8.9s with mine. The 500 digit example takes 106.4s with his software, 22.0s with mine. This is just a sampling -- he may have made choices that cost something in these digit ranges that pays off for larger ranges. These are also 13-year-old executables.

Would it be possible to use ECM on a GPU to speed up the process (sorry if I've misunderstood the relation between ECM for factoring and primality proving)?

Yes and no. For most numbers I've found just running a simple p-1 with very low B values works well. I've tried plugging in LIBECM and it doesn't seem to help, though I obviously haven't tried every permutation of parameters. For ECPP at step [i], I have a big set of numbers (say 140) and I'm trying to find one that gives me a prime factor in the correct range. For any given number I can try harder, or move on to the next one. With FAS I can decide it just isn't working out and go back to step [i-1] and get another set of numbers. More discriminants will give me more candidates. There seem to be a lot of heuristics here -- trade off effort vs. moving on, perhaps don't pick the first one but find the "best" (smallest) q value from the set, and so on.

Atkin and Morain 1992 and Morain 2005 are full of information about possible heuristics, optimizations, observations, and so on. My code definitely doesn't implement all of them (which is one reason I speculated above that Morain's software would be faster than mine if it was written and run on a circa 2010 platform).

This is all good except for stage 0. I can't backtrack from there, so that's where having good factoring would come in handy (or more discriminants so I have more candidates to factor).

[danaj]

Originally Posted by henryzz

The other one worth adding to the table is primo.

With one core or 12? I can make arguments both ways in terms of fairness. If Boinc is the goal, then it's easy enough to load up the machine with N numbers all individually running in serial. But if your goal is to sit down and prove one number on your machine, then Primo has a big advantage.

[henryzz]

Originally Posted by danaj

With one core or 12? I can make arguments both ways in terms of fairness. If Boinc is the goal, then it's easy enough to load up the machine with N numbers all individually running in serial. But if your goal is to sit down and prove one number on your machine, then Primo has a big advantage.

I think one core makes sense as it is a per cpu time comparison.

In terms of BOINC, I would like to see it where a huge number is proved by cooperation from many people.

[danaj]

Updated table, including Primo (one core) and reruns with GMP-ECPP after playing more with parameters. Times are in seconds.

• Primo v 4.0.3 LX64, 22 bits (4.0.1 with 26 bits is a little faster with smaller sizes). Using only one core.
• ecpp-dj v1.00
• yafu 1.34.5 (time yafu, aprcl(...), quit)
• GMP-ECPP atkin243 compiled with g++ -O3 -fomit-frame-pointer. POLY_SIZE set to 1024. Parameters: for 100-300: "-p 1000 -B 2000 -s 123". Parameters for 350+: "-B 2000 -s 123". Runs with different seeds can have substantially different runtimes.
• i3930k, gcc 4.6.2, GMP 4.3.2.
• Primo results all validated with WraithX's code. GMP-ECPP and ecpp-dj results validated with my code.

                                   :  Primo : ECPP-DJ :   YAFU  : GMP-ECPP
 100 digits : 5^143+2              :   0.28 :    0.07 :    0.23 :    12.07
 150 digits : 3^313*4+5            :   0.35 :    0.18 :    0.59 :    24.55
 200 digits : 7^235*9+2            :   0.94 :    0.42 :    1.33 :    54.88
 250 digits : 5^356*8-1            :   2.02 :    0.90 :    2.72 :    91.00
 300 digits : 424^114+3            :   2.29 :    2.35 :    5.13 :   340.36
 350 digits : 1160^114+7           :   3.42 :    4.14 :    9.85 :  2509.18
 400 digits : (291^163-1)/290      :   6.57 :    8.98 :   15.51 :   805.18
 450 digits : 232^190+7            :   8.25 :   10.49 :   24.45 :  2651.61
 500 digits : 1014^166+7           :  10.18 :   22.24 :   36.13 :  8946.62
 550 digits : 10^549*9-7           :  12.16 :   58.20 :   59.35 :  6341.44
 600 digits : 1432^190+7           :  20.90 :   67.74 :   82.61
 650 digits : 2^2159+375           :  31.36 :  118.91 :  101.04
 700 digits : (157^319+319^157)/28 :  29.43 :  152.10 :  162.82
 750 digits : 10^749*2+89          :  49.62 :  162.03 :  208.16
 800 digits : (10^799*61-7)/9      :  75.56 :  174.49 :  284.33
 850 digits : 2^2821-183           :  86.07 :  367.20 :  388.98
 900 digits : (24^653-1)/23        :  96.36 :  367.68 :  444.32
 950 digits : 10^949*4-9           : 117.89 :  819.76 :  592.22
1000 digits : 10^999+7             : 186.42 : 7325.03 :  666.52

I could add Morain's 6.4.5a to the list.