Is time complexity of Linux SHA1 linear? That means that 2GB file is hashed twice longer than 1GB file?
Asked
Active
Viewed 289 times
0
-
4What is "Linux SHA1"? Have you looked at the structure of SHA-1, and the Merkle–Damgård construction in general? What do you think the time complexity would be? What happens if you try it? Would there be other factors to take into account? – ilkkachu Feb 17 '21 at 20:15
1 Answers
3
Yes. There's no sensible way to implement SHA-1, SHA2, SHA3 or any other cryptographic hash function in anything other than linear time. It's impossible to have sub-linear time since the output depends on every bit of the input, and a linear time implementation is straightforward so there's no reason for an implementation to take more than linear time.
Common hash functions are not parallelizable, but even if they were, this wouldn't change the asymptotic complexity: parallelization multiplies the running time by a constant whose lower bound is 1/p where p is the number of processors, which doesn't change the "big oh" complexity class (O(1/p · f(n)) = O(f(n))).
In theory it's possible to design a hash function that can't (or isn't known to) be computable in linear time, but I'm not aware of any advantage such a design would have.
Gilles 'SO- stop being evil'
- 829,060