mersenneforum.org > Math Efficient Proth/PRP Test Proof Scheme
 Register FAQ Search Today's Posts Mark Forums Read

 2020-03-01, 14:04 #1 patnashev   "Pavel Atnashev" Mar 2020 22×11 Posts 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
2020-03-01, 16:51   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

750810 Posts

Quote:
 Originally Posted by patnashev 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,$

 2020-03-01, 17:00 #3 patnashev   "Pavel Atnashev" Mar 2020 22·11 Posts 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.
2020-03-01, 17:22   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

750810 Posts

Quote:
 Originally Posted by patnashev 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.

 2020-04-20, 11:49 #5 patnashev   "Pavel Atnashev" Mar 2020 22·11 Posts 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.
 2020-04-21, 00:44 #6 preda     "Mihai Preda" Apr 2015 5·172 Posts Please have a look at using VDFs for PRP verification: https://mersenneforum.org/showthread.php?t=24654
 2020-04-21, 05:17 #7 patnashev   "Pavel Atnashev" Mar 2020 4410 Posts preda, Pietrzak's VDF looks interesting. A similiar idea, using similiar tools, but more complicated proof calculation. Worth researching.
 2020-04-28, 17:40 #8 patnashev   "Pavel Atnashev" Mar 2020 1011002 Posts 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
 2020-04-30, 19:01 #9 patnashev   "Pavel Atnashev" Mar 2020 22×11 Posts 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); }
 2020-05-13, 08:09 #10 patnashev   "Pavel Atnashev" Mar 2020 22×11 Posts Pietrzak VDF testing started on the private GFN server. Typical task looks like this: Code: 7.14.2 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) ]]>
 2020-05-13, 08:17 #11 patnashev   "Pavel Atnashev" Mar 2020 22×11 Posts And I made infographic explaining how the scheme works. This is my original scheme: And this is Pietrzak VDF:

 Similar Threads Thread Thread Starter Forum Replies Last Post neomacdev Math 5 2019-04-27 20:08 paulunderwood Computer Science & Computational Number Theory 5 2017-06-09 14:02 VictordeHolland Hardware 5 2017-04-29 06:48 kurtulmehtap Math 13 2009-10-02 12:12 amcfarlane Math 1 2006-07-23 18:29

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

Tue Feb 7 20:26:38 UTC 2023 up 173 days, 17:55, 1 user, load averages: 1.81, 1.20, 1.11