mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-06-24, 03:49   #188
patnashev
 
"Pavel Atnashev"
Mar 2020

3710 Posts
Default

It's a model to calibrate your hashes against. Btw, x^(h0*h0) is not modular and can be precomputed.

Last fiddled with by patnashev on 2020-06-24 at 04:27
patnashev is online now   Reply With Quote
Old 2020-06-24, 19:48   #189
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7,013 Posts
Default

Some data (now using the attached sliding window exponentiation routine)

Proof level 8:
Proof generator does 15489 or 20632 squarings (48-bit vs 64-bit hash)
Server does 1080 or 1414 squarings
Proof verifier does 390625 squarings (assuming 100,000,000 exponent)

Proof level 9:
Proof generator does 31485 or 41925 squarings (48-bit vs 64-bit hash)
Server does 1207 or 1577 squarings
Proof verifier does 195312 squarings (assuming 100,000,000 exponent)

From a total system point of view, we can see that proof level 10 is currently optimal. Compared to level 9, generator does 42K more squarings to save the verifier 97K squarings.

If 800 PRP tests a day are reported to the server, I think it can handle 1.2M squarings a day. My quad core Haswells can generate 10 million squarings a day.

For me, at proof level 9, the 10500 squarings saved for 48-bit vs. 64-bit hash represents 1/2 PRP test a year.
Attached Files
File Type: c exponentiate.c (4.3 KB, 9 views)
Prime95 is offline   Reply With Quote
Old 2020-06-24, 20:02   #190
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7,013 Posts
Default

Quote:
Originally Posted by preda View Post
The attack would be so-much-more less practical for 48 or 64 bit hash. So, I'd take the above attack more like an indication of "lack of a practical attack", right?
In choosing the hash function, we are really guarding against a researcher discovering a weakness in the system that is not presently known.

If the future weakness is a reduction in brute force effort, then a longer hash key is our safe guard. So let's rule out 32-bit hash values.

If the future weakness revolves around a small hash value, let's thwart them by making all hash values >= 2^32.

If the future weakness results from some root-of-unity issue, lets rule out multiples of the PRP base 3. I'd remove multiples of two just for good measure. Removing hashes with more small primes is also possible. In total, this does not greatly reduce the search space for the brute force attacker.

I'm happy with 48-bit or 64-bit (or anything in-between!). When eliminating 0 mod 3 hashes, the scheme should not be a simple "add 2" as that would favor 2 mod 3 hashes.

Further comments? Time to come up with the concrete algorithm?

Last fiddled with by Prime95 on 2020-06-24 at 20:09
Prime95 is offline   Reply With Quote
Old 2020-06-24, 20:39   #191
wedgingt
 
"Will Edgington"
Nov 2010
Utah, USA

1816 Posts
Default Avoiding multiples or 2 or 3 in hash values

If you just want to eliminate values that are multiples of 2 or 3:
Code:
  int add[2*3] = { 1, 0, 3, 2, 1, 0 };
  value += add[value % 6];
The value will always be either 1 or 5 mod 6 after this but with a bias towards 5 % 6. Changing one value in the array appropriately would eliminate the bias.
To avoid possibly exceeding 2^64, the array value could be subtracted instead, sometimes leading to a final value < 2^32.
If you also want to eliminate multiples of 5, expand the array to 2*3*5 appropriately.
-- Will



Quote:
Originally Posted by Prime95 View Post
In choosing the hash function, we are really guarding against a researcher discovering a weakness in the system that is not presently known.

If the future weakness is a reduction in brute force effort, then a longer hash key is our safe guard. So let's rule out 32-bit hash values.

If the future weakness revolves around a small hash value, let's thwart them by making all hash values >= 2^32.

If the future weakness results from some root-of-unity issue, lets rule out multiples of the PRP base 3. I'd remove multiples of two just for good measure. Removing hashes with more small primes is also possible. In total, this does not greatly reduce the search space for the brute force attacker.

I'm happy with 48-bit or 64-bit (or anything in-between!). When eliminating 0 mod 3 hashes, the scheme should not be a simple "add 2" as that would favor 2 mod 3 hashes.

Further comments? Time to come up with the concrete algorithm?
wedgingt is offline   Reply With Quote
Old 2020-06-24, 21:25   #192
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

2·3·13·73 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Some data (now using the attached sliding window exponentiation routine)

Proof level 8:
Proof generator does 15489 or 20632 squarings (48-bit vs 64-bit hash)
Server does 1080 or 1414 squarings
Proof verifier does 390625 squarings (assuming 100,000,000 exponent)

Proof level 9:
Proof generator does 31485 or 41925 squarings (48-bit vs 64-bit hash)
Server does 1207 or 1577 squarings
Proof verifier does 195312 squarings (assuming 100,000,000 exponent)

From a total system point of view, we can see that proof level 10 is currently optimal. Compared to level 9, generator does 42K more squarings to save the verifier 97K squarings.

If 800 PRP tests a day are reported to the server, I think it can handle 1.2M squarings a day. My quad core Haswells can generate 10 million squarings a day.

For me, at proof level 9, the 10500 squarings saved for 48-bit vs. 64-bit hash represents 1/2 PRP test a year.
What are the current estimates of storage and bandwidth requirements of each of these levels?
henryzz is offline   Reply With Quote
Old 2020-06-24, 22:54   #193
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

48016 Posts
Default

Quote:
Originally Posted by Prime95 View Post
In choosing the hash function, we are really guarding against a researcher discovering a weakness in the system that is not presently known.

If the future weakness is a reduction in brute force effort, then a longer hash key is our safe guard. So let's rule out 32-bit hash values.

If the future weakness revolves around a small hash value, let's thwart them by making all hash values >= 2^32.

If the future weakness results from some root-of-unity issue, lets rule out multiples of the PRP base 3. I'd remove multiples of two just for good measure. Removing hashes with more small primes is also possible. In total, this does not greatly reduce the search space for the brute force attacker.

I'm happy with 48-bit or 64-bit (or anything in-between!). When eliminating 0 mod 3 hashes, the scheme should not be a simple "add 2" as that would favor 2 mod 3 hashes.

Further comments? Time to come up with the concrete algorithm?
A more complicated hash does not make a better hash (but it can make a weaker hash if not careful). I think it's Knuth who said something on the lines of "a random algorithm does not make a good random number generator". It's unlikely to obtain any security benefit by doing "hardening in the dark" without knowing why or what we're hardening against.

I propose we use simply SHA3-256 truncated to 64bits for the "h" exponents. The chaining of the hash OTOH is done using the full SHA3-256.

Maybe we should also present our "simple" hash scheme to the larger crypto community and ask them for an attack?
preda is offline   Reply With Quote
Old 2020-06-25, 14:14   #194
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3×23×61 Posts
Default

Quote:
Originally Posted by preda View Post
Maybe we should also present our "simple" hash scheme to the larger crypto community and ask them for an attack?
Get best available informed input, yes.
I think doing that repeatedly is one of the things that has made prime95 and gpuowl as good as they already are.
kriesel is offline   Reply With Quote
Old 2020-06-28, 05:48   #195
patnashev
 
"Pavel Atnashev"
Mar 2020

37 Posts
Default

We've started searching for GFN-15 Mega (b^32768+1, 1M digits). b is a hundred-bit number, but Pietrzak VDF works just fine with such numbers.
patnashev is online now   Reply With Quote
Old 2020-07-13, 15:27   #196
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3×23×61 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
In fact these methods works also for the standard LL test, so there is an incredible fast "proof" to convince ourselves in just only O(sqrt(p)) multiplication, if we limit the exponents in the proof say in 64 bits.

Just let
H(n)=(2+sqrt(3))^(2^n) mod Z[sqrt(3),mp].
LL says that mp is prime iff H(p-2)=0 (where here we omit the sqrt(3) stuff).

Ofcourse we had to use this ugly sqrt(3) part also to enable the various fast checks for the powers in H(), if we would keep the conjugate part then
we lose the power.

The error checks goes in the usual way, but in the above ring, not the friendly Z.
This is somewhat interesting, I mean having a fast "almost" true primality check. One drawback is the high storage of the ~sqrt(p) residues. (there is a tradeoff here, you can lower the storage by increasing the computation time).
Please elaborate. (In a way that could be clear to those of us that don't know much about rings.)

The LL test goes as before, but sqrt(p) residues are saved along the way?
What is Z? Notation of a ring?
What is the process by which those sqrt(p) saved residues are processed to produce a verification of correctness?
if it works, this seems to me to offer a more convincing proof of correctly finding a Mersenne prime, than matching zero residues in multiple runs. At the cost of more programming effort to adopt it.

Last fiddled with by kriesel on 2020-07-13 at 15:42
kriesel is offline   Reply With Quote
Old 2020-07-15, 08:34   #197
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

35 Posts
Default

Hi, I have activated the proof feature on my run of M215856353, are you interested in the data? If yes, I'd upload it. It was done using v6.11-325-g7c09e38 with -proof 10.
kruoli is online now   Reply With Quote
Old 2020-07-15, 12:14   #198
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

27·32 Posts
Default

Quote:
Originally Posted by kruoli View Post
Hi, I have activated the proof feature on my run of M215856353, are you interested in the data? If yes, I'd upload it. It was done using v6.11-325-g7c09e38 with -proof 10.
I think there may have been some changes to the proof file format since that version. If you still have around the temporary residues that are stored under 215856353/proof/ , you could use a recent version of gpuowl to re-generate the proof in the new format. To do this run:
./gpuowl -prp 215856353 -proof 10
which should re-start the exponent 215856353 from the last checkpoint which is very near 100%, run the few last iterations, and regenerate the proof in the new format.

The proof can't be uploaded yet, so you'd still need to keep it around for a bit.
preda is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
phi function rula Homework Help 3 2017-01-18 01:41
delay in crediting? ixfd64 PrimeNet 7 2008-10-20 20:45
Why delay between posts? JHagerson Forum Feedback 1 2006-05-13 21:30
Minimum delay between server connections vaughan ElevenSmooth 5 2005-09-08 17:17
Stats delay ltd Prime Sierpinski Project 10 2005-08-08 13:38

All times are UTC. The time now is 12:43.

Fri Aug 7 12:43:45 UTC 2020 up 21 days, 8:30, 1 user, load averages: 2.60, 2.52, 2.46

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.