20200614, 05:12  #100 
P90 years forever!
Aug 2002
Yeehaw, FL
7×1,021 Posts 
With these advances in the cost of creating a proof, we need to consider power=11,12 ... maybe even 13 or more for a 100M test. Each halving of the work the verifier must perform makes an AWS solution more attractive (cheaper). If 600 PRP tests a day can be verified with ~600*100000000/4096 = 15 million PRP iterations, then just a few AWS instances could be running at spot pricing to easily keep up. We definitely need an experienced AWS person to weigh in on the feasibility and daily cost of such a setup. I really, really, really like all PRP proofs being verified by a single trusted setup rather than assignments to random folks on the internet.
The proof file format should change in a minor way. The preferred topK value should be the next multiple of 2^power above the exponent. That is what prime95 will do. Last fiddled with by Prime95 on 20200614 at 05:14 
20200614, 05:58  #101  
"Robert Gerbicz"
Oct 2005
Hungary
7×199 Posts 
Quote:
Maybe the original paper talked about 64 bit values, I'd say 16 bits would be still OK. 

20200614, 06:50  #102 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5^{2}×229 Posts 
Since the proof file is going to be deleted once it has been sufficiently checked, then I suggest to have the server permanently save the normal 64bit residue (like we have now) so that any interested parties can run a full test to verify the integrity.
If some future researcher were to randomly choose candidate exponents and check the PRP against the 64bit residue it would give good confidence that all the numbers were really run. 
20200614, 07:38  #103 
"Robert Gerbicz"
Oct 2005
Hungary
7×199 Posts 

20200614, 07:46  #104  
Jun 2003
13×19^{2} Posts 
Quote:


20200614, 08:07  #105  
"Mihai Preda"
Apr 2015
29×41 Posts 
Quote:
If the hashes are fixed ahead of time (including fixed "per exponent" as you propose), this kind of attack becomes possible: The verification is: (A^h * M)^q == M^h * B. (where q=2^k, but that's not important) If "h" is fixed, the attacker can satisfy the equality by using B:= (A^h)^q * M^(qh) which represents a cheat. (this line of attack does not work if "h" is backwarddependent on B) Last fiddled with by preda on 20200614 at 08:17 Reason: rusty algebra 

20200614, 08:20  #106 
"Mihai Preda"
Apr 2015
1189_{10} Posts 

20200614, 08:29  #107  
"Mihai Preda"
Apr 2015
29×41 Posts 
Quote:
(My initial idea of having topK a multiple of a fixed power of 2 originated from my desire to be able to generate proofs of different powers from the same set of "saved residues" from a PRP test; (this was mainly for debugging). I don't think we need this feature anymore, and thus the first multiple of 2^power is the natural choice for topK) I have an idea for how to speed up the proof generation for higher powers. Then power==14 becomes feasible. There a verification would cost about 8K iterations, yay! I'll try to validate this. Correction: with power==14 the tail (the iterations past E up to topK) will be 8K iterations on average, thus the total average cost of about 16K iterations, or 24K if the verifier also computes prp(9, topK  E) to decide compositeness. Thus power==14 is too large. power==13 would have a tail of 4K iterations on average. Thus total verification cost estimated to 2K + 12K + 2*4K == 22K iterations for a 100M exponent. power==12, tail of 2K, verification estimated 2K + 25K + 2*2K == 31K iterations. (the first 2K approximates the cost of the exponentiations in the "walking the middles" part of verification) power==11, tail of 1K, estimated cost 2K + 50K + 2*1K == 54K its. Maybe power==12 looks like a good choice then? Last fiddled with by preda on 20200614 at 08:53 

20200614, 09:04  #108 
"Mihai Preda"
Apr 2015
29·41 Posts 
Now the topK is not store in the file anymore. It is defined to be what we spec here. (an implicit value, not stored in the file, not hashed).

20200614, 09:13  #109  
"Mihai Preda"
Apr 2015
4A5_{16} Posts 
Quote:
I might agree with changing that to 32bits (even if that significantly reduces the "security" of the proof). But note also that reducing this size from 64b to 32b also does not gain much either. 

20200614, 11:47  #110  
"Mihai Preda"
Apr 2015
1189_{10} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
phi function  rula  Homework Help  3  20170118 01:41 
delay in crediting?  ixfd64  PrimeNet  7  20081020 20:45 
Why delay between posts?  JHagerson  Forum Feedback  1  20060513 21:30 
Minimum delay between server connections  vaughan  ElevenSmooth  5  20050908 17:17 
Stats delay  ltd  Prime Sierpinski Project  10  20050808 13:38 