mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2010-10-23, 15:47   #1
WraithX
 
WraithX's Avatar
 
Mar 2006

23×59 Posts
Default 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
File Type: zip primo_v_1.0.zip (9.3 KB, 148 views)
WraithX is offline   Reply With Quote
Old 2010-10-24, 19:55   #2
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

25×3×31 Posts
Default

Quote:
Originally Posted by WraithX View Post
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.
RichD is offline   Reply With Quote
Old 2010-10-24, 22:26   #3
WraithX
 
WraithX's Avatar
 
Mar 2006

1110110002 Posts
Default

Quote:
Originally Posted by RichD View Post
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.
WraithX is offline   Reply With Quote
Old 2010-10-24, 22:37   #4
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

28×11 Posts
Default

Quote:
Originally Posted by RichD View Post
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
File Type: zip primo-Cert.zip (68.2 KB, 96 views)
kar_bon is offline   Reply With Quote
Old 2010-10-24, 22:57   #5
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

25·3·31 Posts
Default

Quote:
Originally Posted by WraithX View Post
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 is offline   Reply With Quote
Old 2010-10-24, 23:26   #6
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

25·3·31 Posts
Default

Quote:
Originally Posted by kar_bon View Post
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.
RichD is offline   Reply With Quote
Old 2010-10-26, 07:26   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

235F16 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2011-01-10, 16:11   #8
tcadigan
 
tcadigan's Avatar
 
Sep 2004
UVic

2×5×7 Posts
Default

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.
tcadigan is offline   Reply With Quote
Old 2013-09-08, 10:25   #9
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

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
danaj is offline   Reply With Quote
Old 2013-09-08, 15:03   #10
WraithX
 
WraithX's Avatar
 
Mar 2006

23×59 Posts
Default

Quote:
Originally Posted by danaj View Post
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 View Post
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 View Post
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
- 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)
**************************************************************/
Attached Files
File Type: zip primo_v_1.2.zip (9.9 KB, 62 views)
WraithX is offline   Reply With Quote
Old 2013-09-08, 18:36   #11
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

Quote:
Originally Posted by WraithX View Post
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.
danaj 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 Browser? PawnProver44 Information & Answers 14 2016-04-09 05:49
factorDB verifier doesn't like my cert? schickel FactorDB 3 2015-08-09 17:21
PRIMO 3.0.7 Cybertronic Five or Bust - The Dual Sierpinski Problem 17 2009-08-13 20:42
primo question fivemack Math 35 2009-04-28 15:03

All times are UTC. The time now is 00:20.

Sat Jul 4 00:20:21 UTC 2020 up 100 days, 21:53, 1 user, load averages: 1.09, 1.36, 1.35

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.