20200621, 02:30  #166  
"Mihai Preda"
Apr 2015
5×229 Posts 
Quote:
Specifically: half of the hashes are even; why is that a problem? Last fiddled with by preda on 20200621 at 02:40 

20200622, 09:11  #167 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{5}×3×73 Posts 
This is easier to code than I expected! I just created a power=8 proof of M216091 and successfully verified it.
Using 48bit hashes, the proof construction cost was the equivalent of 15K squarings. Serverside cost was 2K squarings. 
20200622, 09:43  #168 
"Pavel Atnashev"
Mar 2020
37 Posts 
Do you construct the full exponent for each point or group them?

20200622, 15:53  #169 
P90 years forever!
Aug 2002
Yeehaw, FL
1B60_{16} Posts 

20200622, 17:57  #170 
"Pavel Atnashev"
Mar 2020
37 Posts 
A time for hacking fun.
The random exponent is required to have no divisors <1000 in my code. After disabling this check I was able to "hide" a 321 prime by multiplying the result by 3rd root of unity. Every third certificate passes validation. Code:
***** cert.txt Certificate RES64: 2C2CCA7B6A1F7703 Time : 4.290 sec. 3*2^2291610+1 is not prime. Proth RES64: 0000000000000002 Time : 125.660 ms. ***** CERT_DC.TXT Certificate RES64: 2C2CCA7B6A1F7703 Time : 52.338 sec. ***** I strengthened the random to contain no divisors < 10^6. Can also check the gcd, but this doesn't look necessary for Proth numbers. 
20200622, 21:52  #171  
"Mihai Preda"
Apr 2015
5·229 Posts 
Quote:
Why do you use the 3rd root instead of the 2nd root of unity? (I would expect the factor "2" to be the worst in the hash, why not use that?) How would the attack look for a (small) mersenne number? 

20200622, 21:55  #172 
"Mihai Preda"
Apr 2015
5×229 Posts 

20200622, 22:51  #173  
"Pavel Atnashev"
Mar 2020
37 Posts 
Quote:
Because the last point is not the end of the test, there's also a short tail, a few squarings. If I used 2nd root it'd turn into 1 too soon and wouldn't survive until the end of test. Find a prime Mersenne number N. Find the smallest factor of N1 which is not 2. Find root = x^((N1)/factor) != 1. Multiply the last point by root. Pray that the random exponent has this factor too. 

20200622, 23:57  #174  
"Mihai Preda"
Apr 2015
5·229 Posts 
Quote:
Let's assume N1 has 3 as a factor. So you find R3!=1 such that R3^3==1, ok. You multiply Y (the final residue) by R3, this is the "faked result". What do you next? If you compute the middles in the usual way from the true saved residues, the proof would not verify.  isn't that so? Even if we say that *all* the random hashes are multiples of 3. 

20200623, 01:09  #175  
P90 years forever!
Aug 2002
Yeehaw, FL
2^{5}×3×73 Posts 
Quote:
I took "grouped" to mean that we do not raise a residue to the power of a product of hashes (e.g. r0 ^ (h0 * h1 * h2)). My proofofconcept proof generator is attached. calc_middle is the recursive routine that calculates a Middle value to output. Last fiddled with by Prime95 on 20200623 at 01:10 

20200623, 01:12  #176 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{5}·3·73 Posts 
I changed my random exponent to a prime number between 33 and 48 bits. Stole some Rosetta C code for MillerRabin test.
Last fiddled with by Prime95 on 20200623 at 01:12 
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 