Is there such a thing as "Fast Hashing Algorithm"

Short version

Is it possible to accelerate hashing process by computing several hashing together in a "smart" way?

Long version

It's generally true that the algorithm complexity of several problems together is smaller than one problem alone.

A concrete example is Fast Fourier Transform. Given N points (assume N is power of 2), the time complexity of getting one single frequency in FT spectrum is O(N). However, we have O(N log(N)) time complexity when we need to compute all frequency.

Another classical example is Strassen algorithm on matrix multiplication.

Would it be theoretically possible to design a batch hashing algorithm on classical computer, such that the time complexity is reduced?

For reducing problem scope, let's just consider the SHA class hashing algorithm

Such "smart" algorithm would have a big impact on password cracking, and cryptocurrency mining.

• like tree hashing? Aug 26, 2017 at 3:55
• "It's generally true that the algorithm complexity of several problems together is smaller than one problem alone." The generality of this statement is simply wrong - otherwise it would be true for every single problem / algorithm. And of course someone would have to prove it. A correct statement would be "It is possible that ..."
– tylo
Aug 28, 2017 at 14:47
• SHA-class hashing algorithms should not be directly used for password hashing anyway. The baseline would be to use PBKDF2-HMAC-SHA-something, with salt.
– fgrieu
Aug 28, 2017 at 14:47