mersenneforum.org Primo version 4 certificates
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-03-07, 03:29 #1 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38A16 Posts Primo version 4 certificates Version 4.20 of Primo was released a couple days ago, and includes a new certificate format. I'll be updating my verifier in the next few days. Related, have we considered using certificates for N-1/N+1 proofs? The verifier allows BLS75-T5 currently. I was debating adding T17 (similar to T5 but with n+1) and either Corollary 11 or Theorem 21 (combined n-1 / n+1). I'm not sure how necessary a Konyagin and Pomerance ($n^{3/10}$ n-1) test is. Right now PFGW seems to be used with a "trust me" algorithm.
 2016-04-16, 20:09 #2 RichD     Sep 2008 Kansas 61518 Posts Any updates when we might be able to start submitting v4.2 certs?
 2016-04-17, 02:28 #3 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2×3×151 Posts Sorry, started a new job and main computer died, so I haven't been able to work on it. Ordering a new computer this weeked.
 2016-05-26, 18:48 #4 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2×3×151 Posts Code is working parsing and verifying version 4.2.1 certificates. Tested on 100 certs made with 4.2.1, about 50 older certs from factordb, and some MPU certificates from the latest code. I'll get it out in the next few days. Sorry for delay. Only a few hours of coding, but ... life. The parsing is ugly and won't handle cases where Primo is told to output numbers in a non-default method. This doesn't seem to have been an issue with the old files. Last fiddled with by danaj on 2016-05-26 at 19:05
 2016-05-26, 19:48 #5 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 11100010102 Posts On the related note, I added some more work on BLS75 theorems, so have: Theorem 3 (one large factor of N-1, just used for ECPP) Corollary 1 (N-1 factored to square root, slightly faster than T5) Theorem 5 (N-1 factored to cube root) Theorem 7 (adds trial factor limit to T5 to reduce the limit) Theorem 15 (one large factor of N+1, just used for ECPP) Corollary 8 (N+1 factored to square root, slightly faster than T17) Theorem 17 (N+1 factored to cube root) Theorem 19 (adds trial factor limit to T17 to further reduce limit) Theorem 20 (combined N-1 and N+1, using trial factor limits and an m value, both used to reduce the needed factoring amount) One thing PFGW does that I don't have is a method for handing in known factors. That's especially useful for factordb since it doesn't want to be spending lots of time factoring. I'll look into this. PFGW uses gwnum rather than GMP so multi-thousand digit inputs will be faster, especially for the N+1 cases which use Lucas sequences rather than the basic modular exponentiation. I believe these will need less factoring than PFGW, but I find it very hard to follow the internals of PFGW (it looks like the combined test is using Corollary 11 which is a simplification of T20, but it isn't stated). This makes me concerned for factordb -- we have an ECPP certificate, but for N-1 / N+1 / combined we just trust PFGW's boolean output. Having a certificate would be a big plus. I don't mean this as a disparagement of PFGW, just that this proof form is highly amenable to certificates and IMO we should have them.
2016-05-27, 14:12   #6
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

22×3×479 Posts

Quote:
 Originally Posted by danaj On the related note, I added some more work on BLS75 theorems, so have: Theorem 3 (one large factor of N-1, just used for ECPP) Corollary 1 (N-1 factored to square root, slightly faster than T5) Theorem 5 (N-1 factored to cube root) Theorem 7 (adds trial factor limit to T5 to reduce the limit) Theorem 15 (one large factor of N+1, just used for ECPP) Corollary 8 (N+1 factored to square root, slightly faster than T17) Theorem 17 (N+1 factored to cube root) Theorem 19 (adds trial factor limit to T17 to further reduce limit) Theorem 20 (combined N-1 and N+1, using trial factor limits and an m value, both used to reduce the needed factoring amount) One thing PFGW does that I don't have is a method for handing in known factors. That's especially useful for factordb since it doesn't want to be spending lots of time factoring. I'll look into this. PFGW uses gwnum rather than GMP so multi-thousand digit inputs will be faster, especially for the N+1 cases which use Lucas sequences rather than the basic modular exponentiation. I believe these will need less factoring than PFGW, but I find it very hard to follow the internals of PFGW (it looks like the combined test is using Corollary 11 which is a simplification of T20, but it isn't stated). This makes me concerned for factordb -- we have an ECPP certificate, but for N-1 / N+1 / combined we just trust PFGW's boolean output. Having a certificate would be a big plus. I don't mean this as a disparagement of PFGW, just that this proof form is highly amenable to certificates and IMO we should have them.
Rouge has said several times that PFGW is overly complex and hard to understand the code. I wonder whether it would be worth starting again adding its features to a cleaner codebase.
There are several sections to the code that would need to be implemented:
1. Supporting the pfgw file types: ABC, ABC2, ABCD. This would include parsing mathematical strings.
2. Various types of tests, prp N-1 N+1 ECPP etc. It would be nice if this was more extensive than PFGW. Certificates for primes.
3. Trial factoring code - Rouge has tried a few times to add better code. Pretty certain he never got the best working. Would P-1 or ECM be worth adding?
4. Script files - possibly optional although it would be nice. The current script language is a bit hard to use as you have to jump back to labels rather than use loops. It would be nice if this made an easy way of harnessing GWNUM.

That sounds a fair bit of work. I suspect it might be easier than improving the pfgw codebase such that things can be added easily. I think we have most of these things individually. Anyone good at clear coding and got some time? It would be worth making sure we have sufficient ideas to make it better rather than just implementing it.

 2016-05-27, 15:22 #7 bgbeuning   Dec 2014 22×32×7 Posts "Clear code" is like "good taste". Hard to define but you know it when you see it.
2016-05-27, 15:32   #8
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

22×3×479 Posts

Quote:
 Originally Posted by bgbeuning "Clear code" is like "good taste". Hard to define but you know it when you see it.
Several people have said that the pfgw code isn't clear. Most of the code on this forum is fairly clear.

2016-07-29, 00:55   #9
RichD

Sep 2008
Kansas

61518 Posts

Quote:
 Originally Posted by RichD Any updates when we might be able to start submitting v4.2 certs?

 2016-07-29, 02:43 #10 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 16128 Posts I thought it was in place. I got a message from Syd on June 28th. I just added a prime and tried to upload the Primo 4.2.0 certificate (which my verifier will parse). Factordb says "No input number found in file." I think whatever process is used to filter the certificates before sending to the verifier is not understanding the new format. I don't know what process that is. Last fiddled with by danaj on 2016-07-29 at 02:44
 2016-10-30, 07:55 #11 Jayder     Dec 2012 2×139 Posts Is there a way for us to have our format 4 certificates converted into format 3? I just spent two hours trying to figure it out, but I am much too stupid to understand how to turn W back into R.

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ FactorDB 126 2020-02-06 17:31 klajok Factoring 0 2011-07-21 08:23 Cybertronic Five or Bust - The Dual Sierpinski Problem 17 2009-08-13 20:42 aaa120 Software 7 2008-10-27 06:28 koders333 Science & Technology 1 2005-10-02 04:34

All times are UTC. The time now is 18:09.

Thu Nov 26 18:09:46 UTC 2020 up 77 days, 15:20, 3 users, load averages: 2.54, 1.98, 1.52