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

Exercise 1
To get your fingers warmed up, take the Python Challenge, which is available online at
www.pythonchallenge.com . This is a set of puzzles, some quite difficult, that require writing programs of vari-
ous kinds to complete.
Although it is called the “Python” Challenge, there is no reason that any other language could not be used.
It just happens that they guarantee that there are usually the appropriate packages available for Python (such as
the Python Imaging Library for some of the image manipulation puzzles), along with Python's built-in support
for string manipulation, large integer mathematics, and so forth.
Again, I am not trying to condemn or recommend any particular language for any particular purposes. This
just happens to be, in my opinion, a good set of programming exercises.

Exercise 2
Implement the standard brute-force factoring algorithm as efficiently as possible in a programming language of
your choice. Try only odd numbers (and 2) up to (where a is the number you wish to factor).

Exercise 3
Make improvements to your brute-force algorithm. For example, skipping multiples of 3, 5, 7, .... Discuss the
speed improvements in doing so.

Exercise 4
Implement Fermat's difference of squares method in the programming language of your choice. Discuss its per-
formance (running times) with inputs of integers varying in size from small numbers (< 100) up through num-
bers in the billions and further.

Exercise 5
Implement Pollard's p - 1 factorization algorithm.

Exercise 6
Building on the elliptic curve point addition used in the previous chapter, implement elliptic curve factorization
(ECF).
Next, provide a chart to compare the performance of Pollard's p - 1 and ECF for the same inputs (with the
same, or similar, parameters).

Exercise 7
Implement Pollard's ρ algorithm for both factoring and discrete logarithms.