20130612, 17:27  #1 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2^{2}×227 Posts 
ECPPDJ
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, HPPA, 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: ecppdj1.00.tar.gz This also includes options for AKS and n1 (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:
Timing using the example numbers WraithX posted for his APRCL implementation. ECPPDJ v1.0, Yafu 1.34.5 APRCL, GMPECPP atkin243. Run on an i73930k. GMPECPP uses random values for various things (ECM factors, root splitting, point selection) so will differ in time each run. ECPPDJ 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. Code:
: ECPPDJ : YAFU : GMPECPP 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*81 : 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^1631)/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*97 : 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*617)/9 : 174.49s : 284.33s 850 digits : 2^2821183 : 367.20s : 388.98s 900 digits : (24^6531)/23 : 367.68s : 444.32s 950 digits : 10^949*49 : 819.76s : 592.22s 1000 digits : 10^999+7 : 7325.03s : 666.52s 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. GMPECM and GMPECPP were very helpful. 
20130612, 20:23  #2 
Oct 2006
Berlin, Germany
2×3×101 Posts 
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 
20130613, 03:55  #3 
Sep 2005
127 Posts 
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 GMPECPP's o switch ( or similar). That way the factordb can store all the chains (2) I _believe_ I've made GMPECPP reasonably stateoftheart, 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 
20130613, 08:22  #4  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2^{2}·227 Posts 
Quote:
Quote:
Edit: Perhaps you can give times you see with GMPECPP for the 250, 300, and 350 digit numbers above, so we can be on the same page with times. Perhaps I'm missing something. Quote:
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. GMPECPP (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. Last fiddled with by danaj on 20130613 at 08:29 

20130613, 09:41  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×2,909 Posts 
factordb uses an independently written certificate checker so primo produces correct results.

20130613, 16:41  #6 
Sep 2009
2×7×11×13 Posts 
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 
20130613, 18:28  #7 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·2,909 Posts 
The other one worth adding to the table is primo.

20130613, 18:39  #8  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1110001100_{2} Posts 
Quote:
Code:
* It is far, far slower than PRIMO. * I suspect it is slower than the 1020 year old work of François Morain. For his 20 512bit examples, I get about the same time (average 0.25s per number). His larger 222digit examples takes 0.91s with his software, 0.93s with mine. The 400 digit example from the first post ((291^1631)/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 13yearold executables. Quote:
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). 

20130613, 18:41  #9 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2^{2}·227 Posts 
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.

20130613, 22:13  #10  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
16BA_{16} Posts 
Quote:
In terms of BOINC, I would like to see it where a huge number is proved by cooperation from many people. Last fiddled with by henryzz on 20130613 at 22:15 

20130614, 16:04  #11 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1614_{8} Posts 
Updated table, including Primo (one core) and reruns with GMPECPP after playing more with parameters. Times are in seconds.
Code:
: Primo : ECPPDJ : YAFU : GMPECPP 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*81 : 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^1631)/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*97 : 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*617)/9 : 75.56 : 174.49 : 284.33 850 digits : 2^2821183 : 86.07 : 367.20 : 388.98 900 digits : (24^6531)/23 : 96.36 : 367.68 : 444.32 950 digits : 10^949*49 : 117.89 : 819.76 : 592.22 1000 digits : 10^999+7 : 186.42 : 7325.03 : 666.52 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New ECPP record  mjm  Computer Science & Computational Number Theory  33  20200213 14:50 
ECPP on Windows?  CRGreathouse  Software  10  20150914 12:32 
Can I just leave this here? (ECPP)  trhabib  Miscellaneous Math  6  20110819 16:34 
Looking for ECPP software  nuggetprime  Software  14  20100307 17:09 
new ECPP article  R. Gerbicz  GMPECM  2  20060913 16:24 