- 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:
- snip -
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.
- hash(100) results in a value of 200
- hash(400) results in a value of 200
This would mean there is a collision i.e hash(100) = hash(400)
Obviously. Given an infinite source, collisions will have to occur eventually in the solution. It can't be avoided.
I think either the loop would terminate for some value of C less than 2^256 or it would not terminate, meaning there was a collison in the sha256
Agreed, either:
- sha256(y) would collide with an earlier iteration of sha256(y) creating a loop that would never terminate
- sha256(y) would collide with sha256("abc") creating a loop that would terminate before C = 2256+1
I suppose it is possible that you could encounter every possible value between 0 and 2
256-1. If that were to happen, then at C = 2
256+1 you would either have to collide with an earlier value (since there are no values left that haven't been generated), or with sha256("abc"). I doubt the result set is that perfectly distributed, but I've not seen anything that says it can't be.