TABLE OF CONTENTS As we saw in Section 7.1, it is easy to recognize prime numbers, and therefore, composite numbers as well. Given a composite number n, it is easy to get a "proof of compositeness" (for instance by exhibiting a number b such that 0 < b < n and b n -1 mod n ? 1). Here "easy" means within a time polynomial in the size of n (namely log n). It is however quite hard to get a nontrivial factor of n in general: no polynomial algorithms (in terms of log n) are known for that.
The first algorithm we think of is based on the trial division algorithm depicted in Fig. 7.1: we try to divide n by all integers i from 2 to 
until a factor is found. This algorithm will pull a factor out of n within a complexity of O( p) arithmetic operations where p is the smallest prime factor of n. [3]
In this section we list a few exponential algorithms which have a better complexity.
Pollard Rho algorithm (named after the Greek ? character) lowers the complexity of trial division from O( p) down to 
where p is the smallest prime factor of n (see Ref. [149]). The basic idea is the following.
We take a "random" function f which can be "factorized" by a mod p function for any factor p of n
