mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2016-03-07, 03:29   #1
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38A16 Posts
Default 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.
danaj is offline   Reply With Quote
Old 2016-04-16, 20:09   #2
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

61518 Posts
Default

Any updates when we might be able to start submitting v4.2 certs?
RichD is offline   Reply With Quote
Old 2016-04-17, 02:28   #3
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2016-05-26, 18:48   #4
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

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
danaj is offline   Reply With Quote
Old 2016-05-26, 19:48   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2016-05-27, 14:12   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×3×479 Posts
Default

Quote:
Originally Posted by danaj View Post
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.
henryzz is offline   Reply With Quote
Old 2016-05-27, 15:22   #7
bgbeuning
 
Dec 2014

22×32×7 Posts
Default

"Clear code" is like "good taste".
Hard to define but you know it when you see it.
bgbeuning is offline   Reply With Quote
Old 2016-05-27, 15:32   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×3×479 Posts
Default

Quote:
Originally Posted by bgbeuning View Post
"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.
henryzz is offline   Reply With Quote
Old 2016-07-29, 00:55   #9
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

61518 Posts
Default

Quote:
Originally Posted by RichD View Post
Any updates when we might be able to start submitting v4.2 certs?
Bump. Any updates??
RichD is offline   Reply With Quote
Old 2016-07-29, 02:43   #10
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16128 Posts
Default

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
danaj is offline   Reply With Quote
Old 2016-10-30, 07:55   #11
Jayder
 
Jayder's Avatar
 
Dec 2012

2×139 Posts
Default

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.
Jayder is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primo ET_ FactorDB 126 2020-02-06 17:31
primo primality certificates - (un)lucky numbers klajok Factoring 0 2011-07-21 08:23
PRIMO 3.0.7 Cybertronic Five or Bust - The Dual Sierpinski Problem 17 2009-08-13 20:42
Where can I download the latest version of primo? aaa120 Software 7 2008-10-27 06:28
How RSA certificates worked in Hotmail 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

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.