Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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 [29] and the article of Flagolet and Odlyzko [17]) 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
Download PDF
14 pages

Loading next page...
 
/lp/springer-journals/a-classical-introduction-to-cryptography-exercise-book-algorithmic-PvwoHnIX9q
Publisher
Springer US
Copyright
© Springer Science+Business Media, Inc. 2006
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 [29] and the article of Flagolet and Odlyzko [17]) 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

There are no references for this article.