Primo Verifier...

[WraithX]

I've written a program in C and GMP to verify certificates that are produced by Primo. I'm posting the code here for anyone who'd like to verify Primo certificates. If anyone encounters any problems, I'd be glad to try and fix the program. Maybe we can also post compiled binaries in this thread too. Hopefully we can ask a Moderator to update this first post with new source files, or binaries that we come up with.

Let me know if you have any questions or comments about the code. I'd also like to hear how well this runs for anyone who tries it.

[RichD]

Originally Posted by WraithX

Maybe we can also post compiled binaries in this thread too. Hopefully we can ask a Moderator to update this first post with new source files, or binaries that we come up with.

It looks like I might have a good compile on a G4 Mac.

What is the format of the input file? - asked a newbie.

A Google search yields lots of information about PDF format.

[WraithX]

Originally Posted by RichD

It looks like I might have a good compile on a G4 Mac.

What is the format of the input file? - asked a newbie.

A Google search yields lots of information about PDF format.

That's good to hear that you could compile it on a G4 Mac. Did you have to modify the source?

The format for the input file is a Primo Certificate. Primo is a program that can certify numbers as prime or composite using ECPP (elliptic curve primality proving). When it is finished running, it produces a certificate that is relatively quick to check compared to the time to produce the certificate. Primo is developed and maintained by Marcel Martin. You can find Primo at the following link: http://www.ellipsa.eu/ I don't see an executable there for any platform other than windows.

I've been asked about writing my own ECPP program, one that would be portable (linux, mac, windows) and multi-threaded. I think I will write one eventually, but I probably won't be able to get to it this year.

[kar_bon]

Originally Posted by RichD

What is the format of the input file? - asked a newbie.

It's a text-file like this one of a certificate of (11^1024+7^1024)/56105593973157374815677701621882118146 (PRP 1029 digits).

[RichD]

Originally Posted by WraithX

That's good to hear that you could compile it on a G4 Mac. Did you have to modify the source?

The format for the input file is a Primo Certificate.

It compiled as released. I was also able to compile the source on a G5 (64-bit) Mac with the -m64 option, as released.

After re-reading the first post my mistake. I read it as to produce certificates like Primo.

[RichD]

Originally Posted by kar_bon

It's a text-file like this one of a certificate of (11^1024+7^1024)/56105593973157374815677701621882118146 (PRP 1029 digits).

Thanks kar_bon,

Both the G4 (32-bit) and G5 (64-bit) verified the certificate, using the code as released, for the number given.

[Batalov]

Under Linux64 OpenSUSE 11.3 works nicely:
./primo_v -i 90007prime/*out
Verifying certificate for N, which has 2916 decimal digits
working on section 234 of 415
working on section 415 of 415
TRK time: 415 banks in 0.051 seconds
Tnm1 time: 10 tests in 0.020 seconds
Tnp1 time: 6 tests in 0.377 seconds
Tec3 time: 59 tests in 80.392 seconds
Tec4 time: 339 tests in 1214.423 seconds
-------------------------------------
Total time = 21 minutes 35.212 seconds
The program returned 0
Candidate number certified prime.

Verifying certificate for N, which has 4269 decimal digits
working on section 23 of 611...
in progress

[tcadigan]

32 bit Ubuntu 10.10 works well:

tcadigan@npdevel:~/Desktop$ ./primo_v -i primo-B32B0023ED0AD-001.out -v
Verifying certificate for N, which has 7334 decimal digits
working on section 949 of 949
TRK time: 949 banks in 0.167 seconds
Tnm1 time: 9 tests in 13.032 seconds
Tnp1 time: 12 tests in 11.175 seconds
Tec3 time: 57 tests in 5915.697 seconds
Tec4 time: 870 tests in 224284.696 seconds
-------------------------------------
Total time = 3837 minutes 4.600 seconds
The program returned 0
Candidate number certified prime.

[danaj]

I created a certificate for this PRP 339 with Primo 4.0.3 today, and was wondering why factordb kept it on the PRP list and kept handing it to me in the candidate list even though I'd downloaded the certificate.

It turns out that both your validator and mine (previous to my update for this issue) choke on the certificate, and interestingly my ECPP software creates a certificate that we both choke on also. Primo itself can verify the certificate.

Certificate in Primo format (from Primo 4.0.3)
Certificate in MPU format (from ecpp-dj)

The problem are the conditions (g) and (h):
g) (R*S) >= (N - 2*N^(1/2) + 1)
h) (R*S) <= (N + 2*N^(1/2) + 1)

In the case of D=-3, m (R*S in primo's terms) = one of the set of 6 values:

N+1 +/- x
N+1 +/- (x+3y)/2
N+1 +/- (x-3y)/2

where x and y are the solutions to x^2 + |D|y^2 = 4N, and |D| >= 3. Hence the limits (g) and (h).

In this particular example, D = -3, x = sqrt(n)+2 and y = sqrt(n), hence N+1+(x+3y)/2 = N+1+2sqrt(n)+1 and exceeds the limit.

Loose bounds would be treating x and y independently and saying:
x <= 2sqrtN
y <= sqrt(4/3N)
So m has a max of N+1+(x+3y)/2 < N+1+(11/4)sqrt(N) < N+1+3sqrt(N)

Using the example, we just need to go up/down by one more. I've updated my verifier to use a bound one farther.

Thoughts on what the tightest bounds are?

[WraithX]

Originally Posted by danaj

I created a certificate for this PRP 339 with Primo 4.0.3 today, and was wondering why factordb kept it on the PRP list and kept handing it to me in the candidate list even though I'd downloaded the certificate.

It turns out that both your validator and mine (previous to my update for this issue) choke on the certificate, and interestingly my ECPP software creates a certificate that we both choke on also. Primo itself can verify the certificate.

Good job on finding a problem certificate. It's always good to have test cases that can stress our software.

Originally Posted by danaj

Certificate in Primo format (from Primo 4.0.3)
Certificate in MPU format (from ecpp-dj)

The problem are the conditions (g) and (h):
g) (R*S) >= (N - 2*N^(1/2) + 1)
h) (R*S) <= (N + 2*N^(1/2) + 1)

I've updated my code so that it takes the ceiling(square-root(n)) in the above calculations, this seems to have fixed the problem in my code.

However, I wanted to point out that I don't quite follow some of your math from up above. For example:

Originally Posted by danaj

where x and y are the solutions to x^2 + |D|y^2 = 4N, and |D| >= 3. Hence the limits (g) and (h).

In this particular example, D = -3, x = sqrt(n)+2 and y = sqrt(n), hence N+1+(x+3y)/2 = N+1+2sqrt(n)+1 and exceeds the limit.

x = sqrt(n)+2
y = sqrt(n)
x^2 + 3y^2 = 4n
n + 4*sqrt(n) + 4 + 3*n = 4n
4*n + 4*sqrt(n) + 4 = 4n, (false)
I'm not sure what x and y should be, but it doesn't look like the above values work.

Here is a copy of my updated primo_v. I've made several improvements to the code since 1.0, but it looks like I forgot to post v1.1 here. Here are the changes I've made in v1.1 and v1.2:

/*************************************************************
primo_v.c - created 2010-09-14 by WraithX 
This code is based on verifier.txt written by Marcel Martin.
The text of verifier.txt is provided after the code.
If a number is verified prime, the program returns 0
If a number is verified composite, the program returns 1
If a certificate file is invalid, the program returns 2
If an error was encountered before getting to the certificate, the program returns 3

Updated 2012/05/11 to version 1.1 by WraithX
- increased max line length to 25000
- made key reading a little more robust,
  can handle up to CHECK_AGAIN_LIMIT unexpected lines between key values
- removed any need for <math.h>
- updated the printing of error messages so you can see after which key the error occurred

Updated 2013/09/08 to version 1.2 by WraithX
- fixed a bug in verify_elliptic_conditions where, in conditions g and h,
  we now use the ceil(sqrt(n)) in the calculations instead of floor(sqrt(n)).
  (The floor had caused some proven prime certs to appear invalid/not-prime)
**************************************************************/

[danaj]

Originally Posted by WraithX

However, I wanted to point out that I don't quite follow some of your math from up above. For example:

x = sqrt(n)+2
y = sqrt(n)
x^2 + 3y^2 = 4n
n + 4*sqrt(n) + 4 + 3*n = 4n
4*n + 4*sqrt(n) + 4 = 4n, (false)
I'm not sure what x and y should be, but it doesn't look like the above values work.

n =10^338*4+10^169*6+3.
floor(sqrt(n)) = 2*10^169+1.
x = floor(sqrt(n))+2
y = floor(sqrt(n))
x^2 + 3*y^2 = 4*n

All calculations are integer -- I should have made it clearer by writing floor(sqrt(n)). So y = floor(sqrt(n)) (or ceil) does not imply y^2 =n.

Here is a copy of my updated primo_v. I've made several improvements to the code since 1.0, but it looks like I forgot to post v1.1 here. Here are the changes I've made in v1.1 and v1.2:

Thanks! I saw the bit on another thread about old files sometimes having oddball extra variables in them -- I should add something like that to mine.

Version 1.2 still outputs "Candidate certified composite" with the RET_COMPOSITE return code when given a prime with an invalid proof.