28 points thomasahle 18 hours ago 8 comments
A few years ago my coauthor and I was wondering if we could reduce the number of multiplications used for hashing algorithms. We had a construction and a 100 page proof, but we were not 100% sure it was correct. Now we have a full Lean proof, so we decided to publish it.
I made this website to make it easy for anyone how has polynomials to evaluate to see how it would be done using our method, as well as a number of previous approaches by Knuth and others.
aetherspawn 1 hour ago | parent
I guess it’s not faster than using a table for CRC8?
vlovich123 1 hour ago | parent
Would this be applicable to fast hashes like WyHash and xxh3 or are those not using polynomials? Is this mainly for faster cryptographic hashes?
voxelghost 1 hour ago | parent
It keeps flipping back to 'monic' from e.g. 'ln(1+x)' when switching between algorithms, and then seems to lock to 'monic'? (Am I missing something?)
Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?
gowld 50 minutes ago | parent
"monic" is a separate switch from the example functions radio-selector. Enabling "monic" removes the leading coefficient.
gowld 59 minutes ago | parent
What is the tradeoff between multiplication and addition?
gowld 54 minutes ago | parent
From the abstract, a name that many on HN would recognize:
> We also give an injective polynomial construction for universal hashing that uses N multiplications to hash 2N values with a single random key. This improves the best previous construction by Daniel J. Bernstein (this http URL).