...another algorithm dominates it for single processor loop detection... at least in storage space. It works as follows: get a sequence of values v(i+1) = MD5(v(i)); simultaneously get another sequence w(i+1) = MD5(MD5(w(i))), and start them at the same place, v(0) = w(0). That is, you're running one of them twice as fast as the other.
I like to call this the "two race cars" algorithm--you start a fast car ahead of a slow car on a single-lane track, and if the fast one runs into the slow one it's a looped track. Funny, just two weeks ago a coworker put a 32-bit CRC function into the programming language I use, and I was playing with finding collisions. (I bet a dollar there would be a non-trivial collision between CRCs of the 76,000 files on our biggest disk and lost.) Has anyone mentioned using this sort of method to generate same-hash texts with, say, opposite meanings? David Wagner says--
Another thing -- I'm not sure this method is (directly) useful for generating lots of collisions, if that is what is desired. I believe Dr. Hellman wrote some paper about the cycling properties of random functions (out of interest in DES), and he concluded (if I remember correctly) that when you generate lots of random starting values and look at their cycling properties, most starting values will drain into a very few specific cycles.
Seems to me that even if lots of random starting points drain into the same cycle, you've still got lots of collisions. Either points where the sequences join the cycle, or points where different tributaries join each other before joining the cycle. --Steve - - - - - - - - - - They say the User exists *outside* of the net. No one knows for sure, but I intend to find out! --ReBoot (Saturday morning 3D animated cartoon)