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 x2 - y2 = 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 1012.
We start by choosing a simple irreducible polynomial function (such as f(x)=x2+1). We then generate a sequence of numbers starting at a given x0 such that
xi = f(xi-1) (mod n)
The trick in the algorithm is to discover pairs of numbers xi and xj such that the divisor d divides xi-xj. We can find this by calculating gcd(n, xi-xj) for a great number of pairs. Since we may have a huge number of pairs to try, we can speed up the process by multiplying many of the pairs together, before doing the gcd.
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 = 210000! (mod n)
for some small value of c, coprime to n. Consider the theorem which states that if p is an odd prime then
2p-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.