# A Classical Introduction to Cryptography Exercise BookAlgorithmic Number Theory

A Classical Introduction to Cryptography Exercise Book: Algorithmic Number Theory Chapter 7 Exercises Exercise 1 *Rho Method and Distinguished Points Let f be a function from a finite set E into itself and xo be a given element of E. The sequence defined by xi = f (xi-l) for i E N has the shape of the Greek character p, i.e., is composed of a first part XO, . . . , xq-1 (the "tail") and a second part xq, . . . , xq+e-l (the "loop") such that xq+e = xq for two integers ! and q. We assume that q and ! are the smallest integers such that xq+e = xq. The goal of this exercise is to design an algorithm for determining q, !, xq-1, and xq+e-l when q > 0. We assume that for a random pair (xo, f ), the average values of q and ! are equal to @ (for more details, see Section 2.1.6 of  and the article of Flagolet and Odlyzko ) and that it is possible to store some pairs (x, S) in memory, where x E E and S is any piece of information. Furthermore, we can perform two instructions, each costing one unit of time, Mem(x, S) http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

# A Classical Introduction to Cryptography Exercise BookAlgorithmic Number Theory

Springer Journals — Jan 1, 2006
14 pages      /lp/springer-journals/a-classical-introduction-to-cryptography-exercise-book-algorithmic-PvwoHnIX9q
Publisher
Springer US
ISBN
978-0-387-27934-3
Pages
159 –173
DOI
10.1007/0-387-28835-X_7
Publisher site
See Chapter on Publisher Site

### Abstract

Chapter 7 Exercises Exercise 1 *Rho Method and Distinguished Points Let f be a function from a finite set E into itself and xo be a given element of E. The sequence defined by xi = f (xi-l) for i E N has the shape of the Greek character p, i.e., is composed of a first part XO, . . . , xq-1 (the "tail") and a second part xq, . . . , xq+e-l (the "loop") such that xq+e = xq for two integers ! and q. We assume that q and ! are the smallest integers such that xq+e = xq. The goal of this exercise is to design an algorithm for determining q, !, xq-1, and xq+e-l when q > 0. We assume that for a random pair (xo, f ), the average values of q and ! are equal to @ (for more details, see Section 2.1.6 of  and the article of Flagolet and Odlyzko ) and that it is possible to store some pairs (x, S) in memory, where x E E and S is any piece of information. Furthermore, we can perform two instructions, each costing one unit of time, Mem(x, S)

Published: Jan 1, 2006