20101023, 15:47  #1 
Mar 2006
13×41 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. 
20101024, 19:55  #2  
Sep 2008
Kansas
111011011011_{2} Posts 
Quote:
What is the format of the input file?  asked a newbie. A Google search yields lots of information about PDF format. 

20101024, 22:26  #3  
Mar 2006
533_{10} Posts 
Quote:
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 multithreaded. I think I will write one eventually, but I probably won't be able to get to it this year. 

20101024, 22:37  #4 
Mar 2006
Germany
2,999 Posts 
It's a textfile like this one of a certificate of (11^1024+7^1024)/56105593973157374815677701621882118146 (PRP 1029 digits).

20101024, 22:57  #5  
Sep 2008
Kansas
3,803 Posts 
Quote:
After rereading the first post my mistake. I read it as to produce certificates like Primo. 

20101024, 23:26  #6 
Sep 2008
Kansas
EDB_{16} Posts 

20101026, 07:26  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3^{2}×1,117 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 
20110110, 16:11  #8 
Sep 2004
UVic
1000110_{2} Posts 
32 bit Ubuntu 10.10 works well:
tcadigan@npdevel:~/Desktop$ ./primo_v i primoB32B0023ED0AD001.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. 
20130908, 10:25  #9 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}·101 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 ecppdj) 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 +/ (x3y)/2 where x and y are the solutions to x^2 + Dy^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 20130908 at 10:26 
20130908, 15:03  #10  
Mar 2006
1000010101_{2} Posts 
Quote:
Quote:
However, I wanted to point out that I don't quite follow some of your math from up above. For example: Quote:
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 20100914 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/notprime) **************************************************************/ 

20130908, 18:36  #11  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}·101 Posts 
Quote:
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:
Version 1.2 still outputs "Candidate certified composite" with the RET_COMPOSITE return code when given a prime with an invalid proof. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primo  ET_  FactorDB  214  20221116 15:36 
Primo Browser?  PawnProver44  Information & Answers  14  20160409 05:49 
factorDB verifier doesn't like my cert?  schickel  FactorDB  3  20150809 17:21 
PRIMO 3.0.7  Cybertronic  Five or Bust  The Dual Sierpinski Problem  17  20090813 20:42 
primo question  fivemack  Math  35  20090428 15:03 