mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-03-01, 14:04   #1
patnashev
 
"Pavel Atnashev"
Mar 2020

43 Posts
Default Efficient Proth/PRP Test Proof Scheme

Executive Summary

Double checking is long considered necessary for coordinated search for prime numbers. Indeed, a prime missed due to hardware error, software misconfiguration or credit cheating can mean years, decades or even centuries of additional work. But the price is high, the resources needed to test a candidate are doubled. Recent developments in hardware error detection (Gerbicz check) allow more certainty in the performance of hardware, but search coordinators still can't be sure that all participants run their software properly, with hardware checks enabled and no malicious intent present.

Proposed scheme does not eliminate the double check, but allows more efficient validation of the original result. Instead of redoing the full test, only ~5% of work is need to validate the result. This comes at a price of additional amounts of data needed to be transmitted from the tester to the coordinator, about 10 MB per million decimal digits of tested number. But this data doesn't need to be stored, after a relatively fast processing it is turned into a certificate the size of the number, which is stored and transmitted to a double checker for validation.


Implementation Summary

The scheme borrows heavily from the Gerbicz check. It's the same idea of verifying a sequence by transforming each member into the next one by a single operation. The coordinator receives s checkpoints at regular interval M from the tester. It is convenient (and reliable) to save the checkpoints right after L^2 Gerbicz check, so it's advised to make M a multiple of L^2. Naturally, we can compute the result by M/2 iterations on average starting from the last checkpoint, but we need to prove the correctness of the last checkpoint first. Instead of proving each checkpoint in the sequence individually, we tag each of them with a random number and multiply all of them into one. The resulting certificate can be proven by M iterations, which requries 1/s of original work. Combined with computing the result, the verification work averages to 1.5/s of total. By keeping s in 20..40 range, we can ensure the verification to be less than 10% while keeping the amount of data transmitted at reasonable level.

Note that the certificate is salted with a sequence of random numbers, which makes the information in it scrambled and unusable for any other purpose but verification. Even if the double checker is the same person as the original tester, it gives him no advantage because without knowing the salt one can neither speed up the calculation nor tamper with its outcome. The result of the verification process is sent to the coordinator who compares it with the result obtained during construction of the certificate.

Also note that due to checkpoints being saved after the Gerbicz check, no hardware error can cause the verification to fail. A failure of the verification is a strong indicator of cheating and should result in permanent ban in most cases.

I've implemented the scheme (and the Gerbicz check) using LLR source code as a base. My implementation can be downloaded here:
https://www.dropbox.com/s/1uidmmbw5o...Proof.zip?dl=1
It contains Windows and Linux binaries, bat files with all the steps as well as readme file which describes each step in detail. Note that for b!=2 the test is ~17% slower than the original LLR.


Theory Summary

The scheme requires the test to be an exponentiation to a power which is itself a power of a relatively small number. So, it works for Proth and Fermat tests of numbers of the form N = k*b^n+c. Both of these tests require exponentiation of a^k to b^n power.
\text{ 1. Let } M = L^2, \, r_0 = a^k, \, r_1 = {r_0}^{2^M}, ..., \, r_s = {r_{s-1}}^{2^M} = {r_0}^{2^{s \cdot M}}=a^{k \cdot 2^{\lfloor n/M \rfloor \cdot M}} \\ \\ \text{ 2. Let } x_i = random(1,2^{64}), \, P_D = {\prod_{0}^{s-1} {r_i}^{x_i}}, \, P_S = {\prod_{1}^{s} {r_i}^{x_{i-1}}} \\ \\ \text{ 3. Compute } P_{DC} = {P_D}^{2^M}  \\ \\ \text{ 4. } P_S = P_{DC} \text{ only if all } r_i \text{ are correct }

Step 1 is performed by the tester, Step 2&4 by the coordinator, Step 3 by a double checker. 2's in the formulas can be replaced with b, a^k is double checked in Step 2, x_i do not need to be stored, and a residue of P_S is enough for Step 4.

While proving the correctness of the scheme rigorously is challenging for me, I've run some simulations. For N=5*2^11+1, a=3, s=3, M=3, 10 sets of random x_i, exhaustive search of (Z/NZ)^s yielded only one solution, the correct one. This proves that the general solution is unique. Probabilistic simulations with r_0 = a^k, r_1 = ... = r_{s-1} = 1, r_s = (a^k)^(2^m) yielded the false positive rate very close to 1/X_MAX. For X_MAX = 2^64 the probability of cheating the scheme is the same as guessing RES64 for a regular test.
Attached Thumbnails
Click image for larger version

Name:	proof.png
Views:	105
Size:	17.2 KB
ID:	21829  
patnashev is online now   Reply With Quote
Old 2020-03-01, 16:51   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by patnashev View Post


Theory Summary

The scheme requires the test to be an exponentiation to a power which is itself a power of a relatively small number. So, it works for Proth and Fermat tests of numbers of the form N = k*b^n+c. Both of these tests require exponentiation of a^k to b^n power.
\text{ 1. Let } M = L^2, \, r_0 = a^k,
Please define L and a.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-01, 17:00   #3
patnashev
 
"Pavel Atnashev"
Mar 2020

43 Posts
Default

L is the constant of Gerbicz check. Can be selected to keep s in 20..40 range. If L = 1024, M is about a million.

a is the parameter of Fermat and Proth tests.Usually a = 3 for big numbers.
patnashev is online now   Reply With Quote
Old 2020-03-01, 17:22   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by patnashev View Post
L is the constant of Gerbicz check. Can be selected to keep s in 20..40 range. If L = 1024, M is about a million.

a is the parameter of Fermat and Proth tests.Usually a = 3 for big numbers.
I have not looked deeply, but the scheme seems workable.
R.D. Silverman is offline   Reply With Quote
Old 2020-04-20, 11:49   #5
patnashev
 
"Pavel Atnashev"
Mar 2020

43 Posts
Default

Setting L = sqrt(n/s) moves the last checkpoint almost to the end of the test. It allows to save on the calculation of the result, and makes s (the number of uploaded checkpoints) the main configurable parameter of the scheme. If s = 16, the verification of a certificate requires 6% of the work, upload size is 6MB per 1M decimal digits.
patnashev is online now   Reply With Quote
Old 2020-04-21, 00:44   #6
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

1,291 Posts
Default

Please have a look at using VDFs for PRP verification:
https://mersenneforum.org/showthread.php?t=24654
preda is offline   Reply With Quote
Old 2020-04-21, 05:17   #7
patnashev
 
"Pavel Atnashev"
Mar 2020

43 Posts
Default

preda, Pietrzak's VDF looks interesting. A similiar idea, using similiar tools, but more complicated proof calculation. Worth researching.
patnashev is online now   Reply With Quote
Old 2020-04-28, 17:40   #8
patnashev
 
"Pavel Atnashev"
Mar 2020

4310 Posts
Default

We started testing this scheme, as well as Gerbicz check implementation, on the private GFN server.
http://boincvm.proxyma.ru:30080/test4vm/

Invitation code "PrimeGrid", select "LLR2 testing" and "Run test applications" in the settings.

Source code for LLR2:
https://github.com/patnashev/llr2
patnashev is online now   Reply With Quote
Old 2020-04-30, 19:01   #9
patnashev
 
"Pavel Atnashev"
Mar 2020

2B16 Posts
Default

I'm very excited about Pietrzak VDF. It has potential to decrease the upload to 2MB per million decimal digits for 6% validation work.

I've implemented it in LLR2, pushed to GitHub already. Not tested yet though.
My implementation looks like this:
Code:
        int[] Prove(int t, int[] r) // t - depth, r - checkpoints
        {
            int i, j, k, e;
            int[] h = new int[t]; // hashes
            int[] u = new int[t]; // products
            int s = 1 << t; // number of points

            int PS = r[s]; // the result
            u[0] = r[s/2];

            for (i = 1; i < t; i++)
            {
                h[i] = hash(PS);
                PS = mul(PS, pow(u[i - 1], h[i]));

                u[i] = 1;
                for (j = 0; j < (1 << i); j++)
                {
                    e = 1;
                    for (k = 0; k < i; k++)
                        if ((j & (1 << k)) == 0)
                            e *= h[i - k];
                    u[i] = mul(u[i], pow(r[(1 + j*2) << (t - i - 1)], e));
                }
            }

            return u;
        }

        Cert BuildCert(int t, int r0, int rs, int[] u)
        {
            int i, h;
            int PD = r0; // a^k
            int PS = rs; // the result
            
            for (i = 0; i < t; i++)
            {
                h = hash(PS);
                PD = mul(u[i], pow(PD, h));
                PS = mul(PS, pow(u[i], h));
            }

            h = random();
            PD = pow(PD, h);
            PS = pow(PS, h);

            if (PS == 0 || gcd(PS, N) != 1)
                throw new Exception();

            return new Cert(PD, PS);
        }
patnashev is online now   Reply With Quote
Old 2020-05-13, 08:09   #10
patnashev
 
"Pavel Atnashev"
Mar 2020

43 Posts
Default

Pietrzak VDF testing started on the private GFN server. Typical task looks like this:

Code:
<core_client_version>7.14.2</core_client_version>
<![CDATA[
<stderr_txt>
BOINC PrimeGrid wrapper 2.01 (May  8 2020 09:10:05)
running ../../projects/boincvm.proxyma.ru_30080_test4vm/llr2_win64_200511.exe -v
LLR2 Program - Version 0.9.3, using Gwnum Library Version 29.8
running ../../projects/boincvm.proxyma.ru_30080_test4vm/llr2_win64_200511.exe -oGerbicz=1 -oProofName=proof -oProofCount=8 -oProductName=prod -oPietrzak=1 -oCachePoints=1 -pSavePoints -q19*2^3588874+1 -d -oDiskWriteTime=1
Starting Proth prime test of 19*2^3588874+1
Using all-complex AVX FFT length 200K, Pass1=640, Pass2=320, clm=2, a = 3, L2 = 899*499, M = 448601
Compressed 8 points to 3 products.  Time : 22.330 sec.
Testing complete.
07:28:01 (4572): called boinc_finish(0)

</stderr_txt>
]]>
patnashev is online now   Reply With Quote
Old 2020-05-13, 08:17   #11
patnashev
 
"Pavel Atnashev"
Mar 2020

43 Posts
Default

And I made infographic explaining how the scheme works. This is my original scheme:
Click image for larger version

Name:	ProofInfo.png
Views:	170
Size:	52.5 KB
ID:	22292

And this is Pietrzak VDF:
Click image for larger version

Name:	ProofInfoP.png
Views:	166
Size:	53.6 KB
ID:	22293
patnashev is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Proof for the efficient algorithm used in trial factoring? neomacdev Math 5 2019-04-27 20:08
Efficient Test paulunderwood Computer Science & Computational Number Theory 5 2017-06-09 14:02
Intel Xeon naming scheme change VictordeHolland Hardware 5 2017-04-29 06:48
proof the lucas lehmer test kurtulmehtap Math 13 2009-10-02 12:12
Proth Test Limits amcfarlane Math 1 2006-07-23 18:29

All times are UTC. The time now is 18:48.

Mon Oct 26 18:48:28 UTC 2020 up 46 days, 15:59, 0 users, load averages: 2.41, 2.14, 2.11

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.