Introduction to Cryptography with Open-Source Software

Appendix B

Advance d computational number

theory

This app e ndix provides an introductio n to some more advanced number the-

oretical algorithms. In particular:

• The quadratic sieve method for factorization.

• The AKS method of primality testing.

• The Pollard rho and the Pohlig–Hellman methods for discrete loga-

rithms.

B.1 The quadratic sieve

The quadratic sieve is a relatively recent algorithm, which can be used

to factor numbers up to about 100 digits. After that a more sophisticated

algorithm—the “number field sieve”—which is be yond the scope of this text,

needs to be used. The idea is to find congruences of the form

x

2

= y

2

(mod n) (B.1)

and then testing ...