Can someone please point me to a book or paper that describes the Tortoise and Hare algorithm by Floyd?
I know there are ample websites out there, but for reference purposes, I need a book or paper to point to.
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth.3 However, the algorithm does not appear in Floyd's published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a directed graph in a 1967 paper, but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a folk theorem, not attributable to a single individual.
Now looking up reference , yields the Handbook of Applied Cryptography, which indeed contains a description as Note 3.8 (PDF version). However the Handbook also attributes the algorithm to Knuth as Wikipedia does, so
Knuth, Donald E. (1969), The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, p. 7, exercise 6
is the reference you are looking for with the Handbook citing it as (PDF, reference 692)
D.E.Knuth , The Art of Computer Programming – Seminumerical Algorithms, volume 2, Addison-Wesley, Reading, Massachusetts, 2nd edition, 1981