ABSTRACT

In Chapter 6, we introduced several algorithmic techniques, that allow us to apply the birthday paradox to arbitrary lists of randomly distributed objects. These techniques do not take into account the specific details of how these objects are generated. In this chapter, we are going to focus on a more specific problem and look for collisions among objects which are generated by iterating some fixed function. In this specific case, many improvements are possible. This is quite important for cryptanalysis, because there are many applications where this improved setting can be exploited. In particular, there are some very important number theoretic algorithms due to Pollard that use these techniques to factor integers or compute discrete logarithms.