Factoring and Discrete Logarithms - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 68

3.5.4.1 Analysis of Pollard's λ
To make this work, we need to set the s i values so that they are about 0.5 on average, and we will have
T set its trap after approximately 0.7 hops, giving us that W will hop about 2.7 times before
stopping. This method also has on the order of ln( b - a ) space requirements, and on the order of 2.7
time requirements.
3.5.5 Index Calculus Method
The index calculus method provides a method analagous to quadratic and number field sieves of factoring,
shown above. This method is particularly well suited to solving the discrete logarithm on multiplicative groups
modulo prime numbers. It was first described as the first subexponential discrete logarithm function by Adle-
man and Demarrais [1].
In general, this can be a very fast method over multiplicative groups, with on the order of
setup time and about running time.
For more information on the index calculus method, please refer to Reference [1].
3.6 Summary
Public key cryptographic systems and key exchange systems often rely on algebraic and number theoretic prop-
erties for their security. Two cornerstones of their security are the difficulty of finding factors of large numbers
and solving discrete logarithms.
In this chapter, I discussed techniques for attempting to crack these two problems. While factoring and dis-
crete logarithms for large problems are not easy, they represent the best way to perform cryptanalysis on most
number theoretic and algebraic cryptosystems.
Exercises
For any of the programming exercises in this chapter, I recommend using a language that supports large number
arithmetic. Languages that support such features are C/C++(through gmp ), Java, and Python, although most
languages will have at least some support for large number arithmetic.
Other languages and environments would also be useful for many of these problems, such as Mathematica
and MATLAB. However, I find it difficult to recommend these packages for every reader, since they can be
very expensive. If you have the ability to experiment with these and other advanced mathematical tools, feel
free to use them.