Primo version 4 certificates

[danaj]

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.

[RichD]

Any updates when we might be able to start submitting v4.2 certs?

[danaj]

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]

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.

[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.

[henryzz]

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.

[bgbeuning]

"Clear code" is like "good taste".
Hard to define but you know it when you see it.

[henryzz]

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.

[RichD]

Originally Posted by RichD

Any updates when we might be able to start submitting v4.2 certs?

Bump. Any updates??

[danaj]

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.

[Jayder]

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.