hello,
I'm doing a research for an exam that I'll have on 25, I need to know (please give me som link if you know them, I wasn't able) what's the complexity in term of O(...) of SHA-1 and MD5, and even of TIGER.
If there're also some comparative with MD5 and SHA-1, that would be great. It's my last exam before graduation! please help me, thanks

lordsoth

i can't answer it exactly, but i GUESS that it is just O(n). seems the most logical one to me.

This is a strange question, because these functions always take a fixed size input for each iteration, and hence, their complexity is obviously always O(n), where n is the size of the total input (i.e. the number of iterations).

Please note the clear distinction between computational complexity (described by O-expressions as above) and running time / algorithmic complexity. SHA-1 e.g. has a little more "complex" algorithm than MD5 (in the meaning bigger, longer, larger number of instructions per iteration, but still not having anything to do with computational time complexity) and hence, with non-optimized implementation methods it will practically always have a little longer execution time than MD5, but this has nothing to do with computational complexity.

(Edit: Lifewire's reply wasn't there when I first viewed the original post and pressed the reply button, but as it seems, we have the same opinion anyway )

so I can't determine it exacly in any way?!?!?
I hoped to see some O(n)......O(n*logn).... sob sob :P
thanks anyway!
lordsoth

Again, the computational complexity (which is the kind of complexity that can be described with O-expressions) is "exactly" O(n). The algorithmic complexity can never be described with an absolute measurement like that, and absolutely not with any O-expressions. At most, you can describe it with a relative measurement for a certain machine code implementation on certain specified hardware platform.

Please try to understand this, since I have quite a strong feeling that this will help you a lot more on that exam than any execution time measurements for those hash algos...

If you mean, "what is the hash output size?": MD4, MD5, RIPE-MD and the various Snefru hash functions all have 128 bits of output; SHA-1 is a 160-bit hash; TIGER is 192 bits, but you can truncate it to 160 or 128 bits.

I remember Knuth's first volume - Fundamental Algorithms - having a lot of stuff regarding algorithmic complexity estimates. Try visiting your favourite library.

Be warned: Knuth is Knuth. Nuff said.

Peres