WyHash and xxh3 are not polynomial, in fact this is one of the issues we try to solve in the paper.
Many "practical" hashes use heuristics instead of real field multiplications to be faster. But it means they are vulnerable to adversarial inputs. That means, it's possible to design a set of keys that have much higher probability (under random hash seeds/keys) to collide than you'd expect under a correct hash function.
It is applicable to fast universal hashes like Poly1305 and Polymur (the latter of which I'm the author). However it's not clear to me whether this work improves over the state of the art for that purpose, see some questions here: https://www.reddit.com/r/programming/comments/1wbgcke/comput....
This purpose is however much easier/flexible than actual polynomial equivalence since the requirement here is only that the polynomial is injective, not identical.
WyHash and xxh3 do not have polynomial structures.
Universal hashes use the input text as the set of coefficients.
This method requires additional preprocessing of the coefficients, before starting to evaluate the polynomial. That preprocessing would slow the hashing algorithm more than what is gained during evaluation.
This method is useful only when with a given polynomial, i.e. set of polynomial coefficients, you want to evaluate that polynomial many times, so the cost of the preprocessing is amortized.
However, this application is very important because most functions are approximated either with polynomials or with rational functions, so this method can accelerate the evaluation of all such approximated functions.
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).
It's a very nice construction (based on Rabin & Winograd's polynomial multiplication method) for building universal hashes with n/2+O(logn) multiplications.
The annoying part is that it's a tree structure, which is not usually what you want in a fast hash that you're folding over a data stream. Some papers like https://eprint.iacr.org/2017/328.pdf try to fix this, but there are a lot of annoying trade-offs.
It takes advantage of FMA (fused multiply add), has good numeric stability and uses pipelining optimally.
A while ago I suggested using Estrin's method in Boost, for functions like std::exp. There's some interesting discussions here: https://github.com/boostorg/math/issues/924 if you are interested in all the practical details.
However, for finite fields (e.g. used for hashing and cryptography) multiplication is much more expensive than addition, which is the main use of this algorithm.
Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?
Many "practical" hashes use heuristics instead of real field multiplications to be faster. But it means they are vulnerable to adversarial inputs. That means, it's possible to design a set of keys that have much higher probability (under random hash seeds/keys) to collide than you'd expect under a correct hash function.
We actually analyze both WyHash and xxh3 in this setting in section "Adversarial inputs for heuristic hashes" - https://arxiv.org/pdf/2609.06022#page=165
This purpose is however much easier/flexible than actual polynomial equivalence since the requirement here is only that the polynomial is injective, not identical.
WyHash and xxh3 do not have polynomial structures.
Universal hashes use the input text as the set of coefficients.
This method requires additional preprocessing of the coefficients, before starting to evaluate the polynomial. That preprocessing would slow the hashing algorithm more than what is gained during evaluation.
This method is useful only when with a given polynomial, i.e. set of polynomial coefficients, you want to evaluate that polynomial many times, so the cost of the preprocessing is amortized.
However, this application is very important because most functions are approximated either with polynomials or with rational functions, so this method can accelerate the evaluation of all such approximated functions.
> 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).
It's a very nice construction (based on Rabin & Winograd's polynomial multiplication method) for building universal hashes with n/2+O(logn) multiplications.
The annoying part is that it's a tree structure, which is not usually what you want in a fast hash that you're folding over a data stream. Some papers like https://eprint.iacr.org/2017/328.pdf try to fix this, but there are a lot of annoying trade-offs.
A famous fast hash is NH, which is just:
where `a_i` are random keys. No modulus needed. The issue is that you need as many random keys as the length of the input.Our construction (section 5.9 Injective Polynomial Hashing) shows that you can do something a bit similar with polynomials:
this is a lot simpler than Bernstein's, and is still n/2 multiplications.It takes advantage of FMA (fused multiply add), has good numeric stability and uses pipelining optimally.
A while ago I suggested using Estrin's method in Boost, for functions like std::exp. There's some interesting discussions here: https://github.com/boostorg/math/issues/924 if you are interested in all the practical details.
However, for finite fields (e.g. used for hashing and cryptography) multiplication is much more expensive than addition, which is the main use of this algorithm.
https://stackoverflow.com/a/39135689