4. Algorithmic number theory

4.1 Factoring

We present Pollard's p – 1 algorithm. We aim to give the idea implemented in this algorithm rather than the details.

Let n be the number to be factorized. Let p be a prime factor of n : n = p ^k m

where m is prime to p and assume that all prime factors of p – 1 are less than a small bound R. Let us denote by ${\mathcal{l}}_q$ , for each prime number q $\le$ R, the integer...