20141020, 08:30  #34 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 Posts 
Apologies, but no, it cannot. factordb is running this verifier, but has a prestep that ensures the uploaded certificate is in the Primo format. This is arguably a good thing in that we don't want lots of different formats being used (what if someone uploaded a certificate that I didn't know how to verify? It would offer little value).
The problem I have generating certificates in Primo format is that Primo assumes the curves/points are of a specific form. ECPP (the algorithm) doesn't require them to be that type, but that is what Primo uses and encodes. My way of generating the curves/points follows the method described in most papers, which don't make values of that form, hence cannot be represented in his format. I tried some experiments tonight and in some cases I can generate his type 4. I'll have to look into the other cases to see if I can create them in his type 3 or 4 form. That's the main holdup. There are some other differences: I use BLS75 theorems 3 and 15 for the N1 and N+1 tests, while Primo uses Pocklington and a similar subset of T15. I could do something to force the Primo limitations. I allow a BLS75 theorem 5 proof since sometimes this can be generated much faster. Easy to turn off. I stop at 2^64 with a BPSW test, Primo continues down to 34*10^13 with a deterministic MR test. This should be a simple matter of ignoring the BPSW result until it is less than Primo's cutoff. Then the output has to be changed, which should be relatively straightforward barring the signature. Last fiddled with by danaj on 20141020 at 08:31 Reason: "The problem is" was too vague 
20141020, 14:27  #35 
I moo ablest echo power!
May 2013
5×347 Posts 
Thanks for the response. I don't suppose there's any chance of getting FactorDB to accept certificates from ECPPDJ and Primo since Primo is only available for Linux now...
Oh well. It's a great program and worked very quickly. Last fiddled with by wombatman on 20141020 at 14:32 
20141021, 03:16  #36 
Bemusing Prompter
"Danny"
Dec 2002
California
7×331 Posts 
Do you have any idea what might account for the large discrepancy in speed between ECPPDJ and Primo? Architectural differences? Implementation of algorithms? Optimizations?

20141021, 06:24  #37 
Bamboozled!
"ð’‰ºð’ŒŒð’‡·ð’†·ð’€"
May 2003
Down not across
3·43·79 Posts 

20141021, 06:55  #38 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·3·151 Posts 
I don't have any special insight into Primo's internals. I believe it is better algorithms for the first step. Certainly Primo has been worked on for much longer. Small implementation optimizations are a relatively small part  it means ECPPDJ is faster at small values, but the better curve finding algorithm dominates once past 500 or so digits and is crushing once past 1000 or so digits. Some of the things:
* Searching for factors. I use a big GMP gcd (for tiny factors) followed by simple factoring. This follows the method used by the earlier Atkin/Morain papers. Primo's "sieve parameters" and behavior make me think he is using either something like section 3.3 of Crandall and Pomerance (Bernstein's batch smoothness test), or perhaps what Morain describes in 5.3 of his fastECPP paper. These are possible to do, and would help, but the next item is more important at large sizes. * Determinants. He has far more to choose from. This is the critical limitation, I believe. This lets one spend less time looking for factors one each one since there are so many more choices. It also prevents the backtracking when we've run out of options (this still happens to Primo, but usually up in the 15k digit range unless a tiny sieve is used). Primo stores the parameters pretty compactly in the .d?? files, while my expanded poly sets are enormous. He may be using something other than Weber polys (Morain's fastECPP mentions he uses different polys and says "it is crucial in practice"), or it might be calculating them. If using nonHilbert/Weber polys one has to be able to generate appropriate curves/points from them  this was a step I looked into and wasn't able to easily make work. * Root finding. I use a very traditional root finding method, that I think runs reasonably fast. It's basically what Morain describes in section 3.6 of fastECPP. There are, I believe, faster ways (e.g. Sutherland or Morain section 5.3.4), but they're beyond my mathematics. I think Primo runs this step a little faster, but not by much. * Primo runs on multiple threads. This isn't really important in this discussion, but does indicate that there is a whole second optimization level revolving around load balancing once the serial algorithm is done. The first two are what Morain calls "step 1" in his fastECPP paper and notes "This is the crucial step." I think what needs to happen is (1) change to the "fastECPP" method to find D values, (2) speed up the process of pulling out small factors, (3) be able to efficiently produce nonHilbert polys for any selected D on the fly. Item (3) looks like it can be done by Enge's CM. I'd appreciate hearing any other thoughts. It's possible I'm looking at the wrong things. 
20141021, 07:00  #39 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·3·151 Posts 
I'm sure there is a chance, but I'm not the person to ask :). The other option is one I have control over (or anyone else since it is open source), which is adjusting the code to create Primo certificates. A free weekend plus this at the top of my curiousity queue would have a decent chance.

20141021, 07:42  #40 
Bemusing Prompter
"Danny"
Dec 2002
California
4415_{8} Posts 
I guess you could contact Morain and ask if he is willing to contribute to ECPPDJ, or at least offer suggestions. He may not want to make Primo open source, but that doesn't mean he won't share ideas.
Last fiddled with by ixfd64 on 20141021 at 07:44 
20141021, 08:22  #41 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·3·151 Posts 
Good point. While FranÃ§ois Morain (author of numerous ECPP papers) would have lots of good ideas, for this purpose Marcel Martin (author of Primo) would be the person to talk to.

20141021, 16:35  #42 
I moo ablest echo power!
May 2013
5·347 Posts 

20141021, 23:10  #43 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5,743 Posts 

20141022, 05:05  #44 
I moo ablest echo power!
May 2013
1735_{10} Posts 
This is true. Maybe I'll set one upit'd be good to learn about them. Do you have a recommendation for virtualization software? I've heard VirtualBox thrown around a good bit?

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 