20130614, 16:48  #12  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·3·151 Posts 
Quote:
Some thoughts off the top of my head. Using ECPP and going purely by the certificate required, we can do one step at a time. Given the n value, our job is to find a suitable m/q/a/b/x/y set. We can break this down into smaller and parallel pieces.


20130614, 17:58  #13 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{3}·719 Posts 
It is finding q that I suspect could be best made parallel.
How many factors are found leaving a large composite? Do you treat those composites any different to the original ones? They should be worth more effort as the size removed will be twice as big assuming the next factor leaves a prp. How difficult is it to generate the polynomials? It seems that your program runs with not many and could do with more. If you have a program that will generate more, I am willing to run it for a bit. It would be nice to try and push up the limit of where your code is better than primo. It looks like it would hopefully be possible to make it useful for smallish numbers even if primo takes over further up. Currently the factordb has a load of candidates 550600 digits which need processing. What is needed to improve that region? Last fiddled with by henryzz on 20130614 at 18:03 
20130614, 17:59  #14  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1110001010_{2} Posts 
Quote:
We first want to run a compositeness test on the number, as these are very fast compared to proofs, and some of the proofs can take ages to finish if given a composite. This may be a single MillerRabin test, MR with the first N prime bases, MR with N random bases, a BPSW variant, or BPSW + one or more MR tests. Depends on which decade you're living in and how paranoid you are. BPSW is what most people use these days (exceptions being libtommath and hence Perl 6, GMP's mpz_probab_prime_p, and old versions of most math software before they all switched to BPSW) If our number is small enough, we could be done right here. BPSW on numbers smaller than 2^64 is deterministic (people have handchecked the results). There are deterministic MR sets for small numbers  Primo uses an old set of these. Some proofs that don't give certificates:
For Factordb/Boinc use, I think the most crucial step is coming up with a well defined certificate format. Then we could use all sorts of software as long as it produces the correct format or could be transformed to it. I have scripts that turn GMPECPP and SAGE output into the certificates I use, for instance. I could do Primo if I implement a validator for its n+1 test. IMO we want:


20130615, 09:47  #15  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 Posts 
Quote:
My FPS code stores all the partial factorizations so it can run each stage starting exactly where it left off. I chose a hackier solution for FAS, where every factor found after stage 1 is added to a list (sfacs). The first thing done for stage 2+ factoring is to trial divide by all the values on that list (which is usually empty or has only a few values). It's kind of ugly, but it works reasonably well and with FAS it rarely gets used anyway. My understanding of GMPECPP is that it refactors the numbers from scratch every time it increases Bmax or Dmax. There are also some possible speedups I'm not doing here. For instance, I just added some code that does simple n1 and n+1 reductions, which can create steps akin to Primo's type 1 and type 2 steps. This basically adds two more candidates. Additionally, it's worth looking at Crandall and Pomerance section 3.3 "Recognizing smooth numbers" (or Bernstein's paper). I believe this is what Primo is doing with its sieve parameter, but I'm just guessing. Basically there are some ways to trial factor a list of numbers that are very efficient, which would be great to use at the start. Quote:
For generation, SAGE and GMPECPP will generate polys, and NZMath put up the web service for small Hilbert polys. I have ~4000 generated  some of them are enormous so I didn't include them, and some of them fail root finding, which makes me think they aren't generated correctly. I'm sorry to say I don't have a nice standalone program that spits out readytouse polys. Valente, Cohen, Atkin/Morain, Crandall and Pomerance, Kaltofen et al., Konstantinou at al., etc are all good resources. Another thought is to ask someone like Marcel Martin or François Morain, since I'm sure both of them have files containing them as well as code to generate them. Either would be useful. Quote:
Quote:


20130721, 07:33  #16 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 Posts 
Version 1.01 is available: ecppdj1.01.tar.gz
Some of the changes:
This is a work in progress, so please give feedback. 
20130721, 10:29  #17 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·3·151 Posts 
Performance graph: [link to image]
Because of the scale (from under 0.0001 seconds to over 40,000) I've used a loglog graph. This does require some extra thought to interpret. 1 second is in the middle, differences below that line may look large but aren't a big deal for most uses. Differences near the top can be huge though, e.g. where GMPECPP swings between 2 minutes and 11 hours for various numbers. The numbers used are the ones from WraithX's timing data for his APRCL code. Using multiple numbers and showing some combination of min, max, average, median would be better for the ECPP algorithms whose times vary wildly with number. For the algorithms that allowed (BPSW, APRCL, ECPPdj) I ran multiple invocations until they passed 5 minutes to get more timing resolution (noting this results in an average time). I used a constant seed for GMPECPP and ECPPdj so the results would be repeatable. In gray I show the time for the extrastrong BPSW test. This of course will be faster than any of the other results. This is the strong probable prime test (e.g. MillerRabin) with base 2, followed by an extrastrong Lucas test. I recently switched from the strong LucasSelfridge test  the extra strong test runs faster, has fewer pseudoprimes, has similar residue class properties, and a reduced version of it has been good enough for Pari. The pale orange is the time for my Perl script to verify an ECPP certificate output by ECPPdj. The EC computations are sent to C+GMP, and are in fact the same code as used in my ECPP, but there is still a fair bit of Perl BigInt work. I'd expect a pure C+GMP version to be a little faster. This seems to run about 1.53x faster than the one by WraithX, but it also clearly hasn't gotten as much use nor eyes on it. The point here is that doing a verification takes much less time than the original proof  for the 2000 digit example it is ~80 seconds vs. 2.5 hours or more for the proof. The nice smooth blue line is WraithX's APRCL code. It does not produce a certificate, but it is quite fast and gives very predictable performance. This is similar in behaviour to the times I've seen from Pari's APRCL. The red line is my ECPP code, with the preliminary n1 test turned off (since I figured we were benchmarking ECPP). The real reason for the prelimitary test is to take care of some small inputs (typically under 30 digits) that can be done quickly, but as Morain's ECPP code shows, some of the example numbers are special cases where n1 is easy. Overall on these examples it is faster than APRCL until about 1000 digits, though with the caveat that any given number may be faster or slower based on how the factoring turns out. The dark green line is Morain's ECPP 6.4.5a from 2001. It is not open source, but is publicly available. He has moved on to different, better, faster code, but it is not available in any form. You can clearly see the numbers where it did a preliminary factoring step (e.g. 210 digits where the example number is 2^688 * 687  1). Past 310 digits it starts taking much longer to prove than my code. The pale blue is GMPECPP 2.46 (10 July 2013). I left everything as default and used "s 1" on the command line. Twiddling with #defines and parameters for each number can improve the performance a lot, but this makes the user guess as to how low POLY_SIZE can be set to before things segfault, and whether to lower or raise the precision (the default 10000 is far too high for small numbers, but probably too low for big numbers  Atkin/Morain 1992 as well as the plethora of papers by Konstantinou et al. discuss estimating the precision needed). As I found last time, it's much slower than the other implementations. GMPECPP prints out enough information to trivially create a certificate., which I verified for each of the results. ECPPdj was run with certificate output and the results verified (though with my own code, so take that with a grain of salt). One thing I see is that all these ECPP implementations start getting very choppy in performance once the size goes above a certain point. One thing I noticed with the 1000+ digit numbers is that finally my poly root finder is a bottleneck, which actually made me feel better, since many of the early papers indicate it was one of the largest performance issues, yet for "small" numbers it just didn't really come up for me. With the big numbers especially, it becomes a game of tradeoffs and heuristics deciding how deep to factor and whether to look at largedegree polynomials at all, knowing that they'll hurt in stage 2. I didn't put numbers for Primo here. Based on the earlier results it would be very fast. 
20130721, 15:33  #18 
Aug 2006
5,939 Posts 
Wonderful graph, thanks! Very helpful in seeing what's going on.

20130721, 23:00  #19 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{3}×719 Posts 
That looks like quite a nice improvement. It is a little hard to compare with primo as working out exact values is pretty much impossible. It looks like beating aprcl should be the aim for now.

20130722, 15:17  #20 
May 2012
2^{3} Posts 
Why does it require EC point multiplication in affine coordinates?

20130729, 07:21  #21 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·3·151 Posts 
It shouldn't actually require affine coordinates. I've thought about changing my code to do it in projective, which should be much faster (at certainly is for ECM). This won't change the proof times very much (so hasn't been high on my list), but is where almost all verification time is spent.

20130805, 16:33  #22  
Sep 2009
2·7·139 Posts 
Quote:
Chris 

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 