- Trial Division
- Fermat's Algorithm
- Pollard Rho Algorithm
- Pollard p-1 Algorithm
- The Quadratic Sieve
- CFRAC
- Elliptic Curve Algorithm

The basic idea is to look for factors by attempting to divide the given number by prime numbers less than the square root of the number. A static table of primes could be used to save effort generating them. Another alternative is to simply test all numbers less than the square root - although it takes a bit longer, it saves on storage.

*Note that the reason for only going as high as the square root of the
number we want to factorize is that all factors come in pairs, one lower
and one higher than the square root, which when multiplied together give the
number (except of course the square root itself).
For example the pairs of factors for 12 are (1,12), (2,6), (3,4). The square
root of 12 lies between 3 and 4.
*

The Trial division algorithm is reasonably good for *very* small
numbers. Before running one of the stronger algorithms, one might use trial
division to test the small possible factors up to 1,000,000. After that it
becomes very slow, and cannot compete with the stronger algorithms.

Fermat's algorithm works from the square root of the number, n, and works
outwards. It tries to find two numbers, x and y, so that x^{2} -
y^{2} = n. This
is the difference of two squares and can be written n = (x - y) (x + y),
and thus n is respresented as the product of two integers.

Although the algorithm can be sped up by keeping track of certain variables, this particular algorithm is not suitable for factoring large numbers. The problem with both trial division and Fermat's algorithm is that they do not only find factors, but if left running long enough, they prove primality. They are deterministic and will check every possible factor before returning. This is a particularly bad way of proving primality, especially since we have the pseudoprime test. The rest of the algorithms described will not be deterministic but probabalistic.

Together, the Pollard Rho and p-1 algorithms are intermediate tests between
the trial division and Fermat's algorithm and the big guns such as the
Quadratic sieve. They work quite well up to numbers where the prime factors
are no bigger than 10^{12}.

We start by choosing a simple irreducible polynomial function (such as
f(x)=x^{2}+1). We then generate a sequence of numbers starting at a given
x_{0} such that

x_{i} = f(x_{i-1}) (mod n)

The trick in the algorithm is to discover pairs of numbers *x _{i}
* and

A fuller explanation of the Pollard Rho can be found in Bressoud's book.

The *p-1* test works when the divisors of n (let's call them
*p, q*) have the property that the divisors *p-1* or *q-1
* have small factors, let's say less than 10,000. We could say that all
the factors must be less than 10,000 and therefore *p-1* divides
10000!. Using the fast exponentiation algorithm, we can quickly determine

m = 2^{10000!} (mod n)

for some small value of c, coprime to n. Consider the theorem which states that if p is an odd prime then

2^{p-1} = 1 (mod p) {note the equals stands for
"is congruent to" here}

Using this we can see that since p-1 divides 10000!,

m = 1 (mod p)

which is like saying that

m - 1 = p*k, for some k in Z

Therefore *p* divides *k-1*. There is a reasonable chance
that n does not divide *m-1* so we can find the a non-tirvial factor by
calculating

g = gcd(m-1,n)

This explanation of the Pollard p-1 is taken from Bressoud's book.

Ronan Killeen

Back to home.