This section describes methods of factoring integers. It starts off with some extremely naive methods, and builds
up to some more advanced methods. Very little knowledge is assumed, however some knowledge of mathematics would
be a big help. I will give some information regarding the time it takes to factor certain integers also, since
algorithm complexity is a huge part of integer factorisation methods.
I will start with the question: what does it mean to factorise an integer? All integers are either prime numbers
or composite numbers. Prime numbers cannot be factored, since no two (or more) numbers can be multiplied together
to get a prime number (except itself and 1). Several prime numbers include 5,7,29 and 3967. There are an infinite number of primes. Composite
numbers are those numbers that are made up by multiplying 2 or more numbers together, e.g. 6 = 2x3, 2968 = 2x2x2x7x53.
The numbers that we list as being the factors of a composite are prime. The task described on this page is, given a
number 'n', how to get the list of prime numbers, that, when multiplied together, give 'n'.
The RSA algorithm uses composite numbers with 2 very large prime factors. For this reason the algorithms on this page
will only be concerned with finding the first factor in the list of factors. This first factor can then be used
to get the other factor.
Method 1. Trial Division
This method is the simplest method and the first that comes to mind. Given a number N, simply divide it by all the numbers
less than it, if any divide evenly (no remainder) then we have our factor.
If we think about it, we do not need to divide by all the numbers less than N, we can actually stop at sqrt(N), since at least
one of the factors has to be less than this (the other will be greater). This is actually a pretty big speed up, imagine we
are trying to factor the number 101. Instead of trying all the numbers up to 100, we actually only need to test up to 10.
To further speed this up, we need only test odd numbers less than sqrt(N), since if a number is not divisible by 2, then it
can never by divisible by 4 as well (4=2x2). This idea can be extended to all other products, which means we really only need
to test prime numbers less than sqrt(N). However, building this list of primes would take longer than just trial division of N, so it
is probably better to just skip the even numbers.
Psuedocode for trial division of integer N
-------------------------------------------
if remainder of N/2 is zero, return 2 as factor
loop i = 3 to sqrt(N),
if remainder of N/i is zero
return i as factor
endif
i = i + 2
endloop
If we haven't returned yet, N must be prime
One of the biggest drawbacks of this method, though, is that it is really slow for large numbers (N > 10^8). More
efficient solutions are shown below.
A javascript implementation of this method:
Note that the javascript method here returns all the prime factors of a number, not just the first (as the psuedocode does). Also note that
javascript is really slow compared to something like c, so if you want a slightly quicker version implement it in something other than
javascript.
Method 2: The Pollard-Rho Method
John Pollard published his Rho Method of Factorization in 1974. This discussion assumes you know some modulo arithmetic and how
to find the greatest common divisors of 2 numbers.
First of all, we should know that this number is composite (there are a few tests that can be done).
We start with a number n. Since n is composite, we know it has at least one factor d. We know that d is smaller than n, and that there is
at least one d which is less than sqrt(n).
We will chose 2 random numbers a and b, both of which are 0 <= a,b < n. The only combination of a and b such that a = b (mod n) is when a and b
are the same (because a and b are less than n). But, since d < n, we may be able to find a,b such that a = b (mod d) where a != b.
If we find an a,b such that a = b (mod d), it means that d divides (a-b) [or d | (a-b) ]. Since d divides n, the greatest common divisor of (a-b)
and n is a multiple of d [or d | gcd((a-b),n) ]. So, now, we can divide n by whatever this greatest common divisor turned out to be.
This means we have found a factor. If we were dealing with a product of 2 primes we could stop here, otherwise we would continue with d or n/d.
The central idea of the pollard rho method is using a polynomial f(x) to generate a and b. Usually this polynomial is of the form x^2 + 1.
... more coming soon ...
pseudocode for the pollard rho method
input: n
returns d, a factor of n
-------------------------------------
x=2, y=2, d=1
while d is 1
x = f(x)
y = f(f(y))
d = GCD(|x - y|, n)
if d = n, pollard rho method has failed.
endwhile
d is our factor
If the pollard method fails, it is because of 1 of the following: the number n is prime, or the polynomial f(x) is a
poor choice. Try x^2 + 2 or x^3 + 1 etc.
A javascript implementation of this method, numbers up to around 10^12 should not be a problem.
Note that the javascript method here returns just the first prime factor it finds. Also note that
javascript is really slow compared to something like c, so if you want a slightly quicker version implement it in something other than
javascript. The biggest number javascript can handle is slightly bigger than 9,000,000,000,000,000 (16 digits max).
Method 3: Pollard p-1 method
A javascript implementation of this method, numbers up to around 10^12 should not be a problem.
Note that the javascript method here returns just the first prime factor it finds. Also note that
javascript is really slow compared to something like c, so if you want a slightly quicker version implement it in something other than
javascript. The biggest number javascript can handle is slightly bigger than 9,000,000,000,000,000 (16 digits max).
Method 4: Congruences of Squares
This method is quite inefficeint in itself, however other faster algorithms build on it.
Method : The Multiple Polynomial Quadratic Sieve
A good introduction to this method is given in mpqs.ps.gz, this
document gives a good overview of other methods as well.