Show HN: Compute polynomials twice as fast

There are many hashes that use more thorough mixing functions than can be achieved with one or a few arithmetic operations (like in universal hashes), thus for them the collision probability reaches the limit imposed by the length of the hash value. Modern CPUs have various instructions that can be exploited in mixing functions that have about the same speed as simpler arithmetic operations, but which achieve a better mixing.

An example is the Alred construction (Joan Daemen & Vincent Rijmen, in 2005-02), which was inspired by the old CBC-MAC algorithm, but it is much more efficient (in this construction, the hash mixing function is derived from the internal mixing function used in some block cipher function, for example the AES block cipher function, so it can be implemented with the AES round function instructions of x86-64 and Aarch64, which are very fast in modern processors; this hash function uses the AES instructions but it is several times faster than the AES encryption/decryption algorithms, which are already very fast).

Another example is any hash function that has the structure used in the Jutla authentication method (Charanjit Singh Jutla @ IBM, patent filed on 2000-04-14; many other patents were filed on variants of this, but now they are expired or invalid; in this method, the input text is partitioned in blocks with the length equal to the hash length, then a parallel mixing function transforms each input text block into a scrambled text, in a different space of values, then in the transformed space a simple additive function, even the simplest, which is bitwise addition modulo 2, can be used to reduce the transformed message to a single intermediate hash value, and finally the inverse of the mixing function is applied to the intermediate hash value to produce the final hash value by going back to the original space of values; this makes the computation of the hash parallelizable, thus very fast; an LFSR, i.e. linear-feedback shift register, is used to generate a non-repeating sequence that is added to each block, both before and after applying the mixing transformation, to make the hash depend on the order of the input blocks, i.e. this is equivalent with using a different mixing function for each block; there are universal hashes based on scalar products which have the same structure like this, but the difference is that they use a simple multiplication instead of a complex mixing function).

Another example is the HighwayHash, developed at Google in 2016, and optimized for SIMD instructions of AVX2 or SSE4.1 or IBM POWER VSX or Arm Aarch64.

Such hash functions were developed first in cryptographic contexts, i.e. as keyed hash functions, a.k.a. message-authentication codes.

Nonetheless, because modern CPUs now include a lot of instructions for the acceleration of cryptographic algorithms, such hash functions can be used now for any other hashing applications, because on modern CPUs they can be as fast or even faster than traditional hash functions with simple arithmetic operations.