mersenneforum.org Primo Verifier...
 Register FAQ Search Today's Posts Mark Forums Read

2010-10-23, 15:47   #1
WraithX

Mar 2006

10000011102 Posts
Primo Verifier...

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.
Attached Files
 primo_v_1.0.zip (9.3 KB, 344 views)

2010-10-24, 19:55   #2
RichD

Sep 2008
Kansas

3×7×179 Posts

Quote:
 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.

2010-10-24, 22:26   #3
WraithX

Mar 2006

10168 Posts

Quote:
 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.

2010-10-24, 22:37   #4
kar_bon

Mar 2006
Germany

BA616 Posts

Quote:
 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).
Attached Files
 primo-Cert.zip (68.2 KB, 293 views)

2010-10-24, 22:57   #5
RichD

Sep 2008
Kansas

1110101011112 Posts

Quote:
 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.

2010-10-24, 23:26   #6
RichD

Sep 2008
Kansas

3×7×179 Posts

Quote:
 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.

 2010-10-26, 07:26 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22·11·227 Posts 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
 2011-01-10, 16:11 #8 tcadigan     Sep 2004 UVic 2×5×7 Posts 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.
 2013-09-08, 10:25 #9 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 11100011012 Posts 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? Last fiddled with by danaj on 2013-09-08 at 10:26
2013-09-08, 15:03   #10
WraithX

Mar 2006

2·263 Posts

Quote:
 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.

Quote:
 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:
Quote:
 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:
Code:
/*************************************************************
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
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)
**************************************************************/
Attached Files
 primo_v_1.2.zip (9.9 KB, 256 views)

2013-09-08, 18:36   #11
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

90910 Posts

Quote:
 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.

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ FactorDB 214 2022-11-16 15:36 PawnProver44 Information & Answers 14 2016-04-09 05:49 schickel FactorDB 3 2015-08-09 17:21 Cybertronic Five or Bust - The Dual Sierpinski Problem 17 2009-08-13 20:42 fivemack Math 35 2009-04-28 15:03

All times are UTC. The time now is 16:13.

Sun Dec 4 16:13:50 UTC 2022 up 108 days, 13:42, 0 users, load averages: 0.77, 1.06, 1.00