- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?
- snip -
I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take.
You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -
A finite set doesn't guarantee any particular pattern of solution.
Here's an extreme example:
Imagine a hash function that maps an infinite set of values to the finite set between 0 and 999. Imagine that results of the hash function are evenly distributed across the finite set so that any value in the finite set is equally likely to result from the function. Now imagine that he function results in the following particular results:
- hash('abc') results in a value of 100
- hash(100) results in a value of 200
- hash(200) results in a value of 300
- hash(300) results in a value of 400
- hash(400) results in a value of 200
The loop that the OP suggested would NEVER exit. It would run infinitely generating the sequence 200, 300, 400, 200, 300, 400, 200, 300, 400, etc. It would never reach a value where hash(y) = 100.
I stand by my statement, "
I'm not sure that it can even be said for certain that the loop would ever terminate. If it did, I don't think you can predict ahead of time just how many iterations it would take."
SHA-256 isn't predictable enough to know if a pattern of results would emerge.
Is the hash space for the SHA256 algorithm cyclic under sha256? I guess I don't know enough about the math involved, and a quick search doesn't turn up anything promising.
Intuition says that it should be, but that not every initial value is a generator. In fact, groups that have this property are very special, so I doubt it.