mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2014-10-20, 08:30   #34
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

Apologies, but no, it cannot. factordb is running this verifier, but has a pre-step 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 N-1 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 M-R 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 2014-10-20 at 08:31 Reason: "The problem is" was too vague
danaj is offline   Reply With Quote
Old 2014-10-20, 14:27   #35
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5×347 Posts
Default

Thanks for the response. I don't suppose there's any chance of getting FactorDB to accept certificates from ECPP-DJ 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 2014-10-20 at 14:32
wombatman is offline   Reply With Quote
Old 2014-10-21, 03:16   #36
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

7×331 Posts
Default

Do you have any idea what might account for the large discrepancy in speed between ECPP-DJ and Primo? Architectural differences? Implementation of algorithms? Optimizations?
ixfd64 is offline   Reply With Quote
Old 2014-10-21, 06:24   #37
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

3·43·79 Posts
Default

Quote:
Originally Posted by wombatman View Post
Thanks for the response. I don't suppose there's any chance of getting FactorDB to accept certificates from ECPP-DJ and Primo since Primo is only available for Linux now...

Oh well. It's a great program and worked very quickly.
WINE?
xilman is offline   Reply With Quote
Old 2014-10-21, 06:55   #38
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

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 ECPP-DJ 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 non-Hilbert/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 non-Hilbert 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.
danaj is offline   Reply With Quote
Old 2014-10-21, 07:00   #39
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

Quote:
Originally Posted by wombatman View Post
Thanks for the response. I don't suppose there's any chance of getting FactorDB to accept certificates from ECPP-DJ and Primo since Primo is only available for Linux now..
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.
danaj is offline   Reply With Quote
Old 2014-10-21, 07:42   #40
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

44158 Posts
Default

I guess you could contact Morain and ask if he is willing to contribute to ECPP-DJ, 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 2014-10-21 at 07:44
ixfd64 is offline   Reply With Quote
Old 2014-10-21, 08:22   #41
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
I guess you could contact Morain and ask if he is willing to contribute to ECPP-DJ, or at least offer suggestions. He may not want to make Primo open source, but that doesn't mean he won't share ideas.
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.
danaj is offline   Reply With Quote
Old 2014-10-21, 16:35   #42
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5·347 Posts
Default

Quote:
Originally Posted by xilman View Post
WINE?
I actually have an Ubuntu box that's off in the corner (literally). I was just hoping to have a primality tester I could use on my Windows boxes and upload certificates directly.
wombatman is offline   Reply With Quote
Old 2014-10-21, 23:10   #43
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5,743 Posts
Default

Quote:
Originally Posted by wombatman View Post
I actually have an Ubuntu box that's off in the corner (literally). I was just hoping to have a primality tester I could use on my Windows boxes and upload certificates directly.
You could use a virtual machine.
henryzz is online now   Reply With Quote
Old 2014-10-22, 05:05   #44
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

173510 Posts
Default

This is true. Maybe I'll set one up--it'd be good to learn about them. Do you have a recommendation for virtualization software? I've heard VirtualBox thrown around a good bit?
wombatman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New ECPP record mjm Computer Science & Computational Number Theory 33 2020-02-13 14:50
ECPP on Windows? CRGreathouse Software 10 2015-09-14 12:32
Can I just leave this here? (ECPP) trhabib Miscellaneous Math 6 2011-08-19 16:34
Looking for ECPP software nuggetprime Software 14 2010-03-07 17:09
new ECPP article R. Gerbicz GMP-ECM 2 2006-09-13 16:24

All times are UTC. The time now is 12:58.

Tue Nov 24 12:58:25 UTC 2020 up 75 days, 10:09, 4 users, load averages: 2.33, 2.30, 2.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.