Even if RSA decided to cancel the Factoring Challenge, it seems that some teams keep working on it. According to Wikipedia, RSA-768 has been factored in late 2009.
What are the current large integer factorization algorithms and what the mathematical principles behind them? What are the ways for improvement (faster algorithms, better implementations...)?
The three main general-purpose algorithms for factorization are the quadratic sieve (QS), the elliptic curve method (ECM) and the number field sieve (NFS).
On Complexity
The running time of these algorithms is expressed with the L-notation: $L_n[a,c]$ means that the asymptotic complexity of factoring a number $n$ is $O(e^{(c+o(1))(\log n)^a(\log \log n)})^{1-a}$. We recognize "$\log n$" as "the size of the number $n$" so the main parameter to look at is the "$a$", but, for a given "$a$", "$c$" must not be neglected. Also, this is an asymptotic complexity, valid when $n$ is "big enough" and there is no telling whether the everyday "$n$" values (e.g. RSA keys) are "big enough" for the expression to be a precise estimate of the actual factorization effort. Last but not least, running time is only about CPU consumption, it does not cover memory usage, and memory is the bottleneck for 1024-bit integers.
Quadratic Sieve
A description of QS can be found in chapter 3 of the Handbook of Applied Cryptography. It is more thoroughly detailed in "A Course in Number Theory and Cryptography", a highly recommendable book for whoever is interested in such subjects (contrary to the Handbook, this one is not free, but it is well worth its price).
The main idea of QS is to try to find two integers which are square roots of the same value modulo $n$. If we consider $n = pq$ (with $p$ and $q$ big primes), then most integers which have a square root modulo $n$ actually have four square roots; this can be seen with the Chinese Remainder Theorem (CRT), which roughly states that when you compute modulo $n$, you are actually computing modulo $p$ and modulo $q$ at the same time. If $z$ is a quadratic residue modulo $n$ (it is the square of some integer modulo $n$), then $z$ is also a quadratic residue modulo $p$ and modulo $q$. Modulo $p$, $z$ has two square roots (if $u$ is a square root of $z$, then so is $-u$), and $z$ also has two square roots modulo $q$, yielding four possible combinations through the CRT. The four square roots of $z$ are $u$, $-u$, $v$ and $-v$ for two values $u$ and $v$.
So if we find $x$ and $y$ such that $x^2 = y^2 \mod n$, then $x$ and $y$ are two square roots of the same value modulo $n$. The bad case is then $x = ±y \mod n$, because this yields no information: this is when $x$ and $y$ are $u$ and $-u$, or $v$ and $-v$. However, there is a 1/2 probability that $x$ and $y$ are $±u$ and $±v$, respectively. At that point, a simple GCD between $n$ and $x+y$ will yield $p$ or $q$.
In QS, we set two bounds $A$ and $B$, and we look for $B$-numbers in a set $S$ of integers. A $B$-number is a number which is $B$-smooth, i.e. such that all its prime divisors are smaller than $B$. The set $S$ consists in the integers $t^2-n$, for values of $t$ which are between $\sqrt{n}$ and $\sqrt{n}+A$. So the values in $S$ are "small" integers which are each equal to the square modulo $n$ of a "bigger" integer.
Suppose that we found two $B$-smooth integers $s_1$ and $s_2$, such that $s_1 = gh^5$ for some small primes $g$ and $h$ (smaller than $B$), and $s_2 = g^3h^3$. Neither is an "obvious square" (i.e. a square in the plain integers, not computing modulo $n$); but $s_1s_2 = g^4h^8$, which is the square of $g^2h^4$ (square in the plain integers, but this then also holds true modulo $n$). However, $s_1$ and $s_2$ are also squares modulo $n$ of some $t_1$ and $t_2$, respectively, so $s_1s_2$ is a square of $t_1t_2$ modulo $n$. This yields two values $x = t_1t_2$ and $y = g^2h^4$ such that $x^2 = y^2 \mod n$, exactly what we were looking for.
The gist of QS is the generalization of this process. We accumulate many $B$-smooth values from $S$, in the hope that we will find a product of such $B$-smooth values where each prime divisor will have an even exponent, because this then yields an "obvious square" which we can equate to a "non-obvious square" obtained from the way the set $S$ was defined.
Finding $B$-smooth integers in the set $S$ involves "sieving", which in this case can be thought of as an offspring of Eratosthenes' Sieve. We "lay out" a sequence of values from $S$, then we "mark" all multiples of $r$ for every prime $r$ smaller than $B$; if one of the values has accumulated enough marks, then it is a product of "many" small primes, and thus a good candidate for being $B$-smooth.
The two parts of the algorithm are thus sieving, which can be distributed over many machines, each looking for $B$-smooth integers in a relatively small range (for big integers, we are still talking about using a few gigabytes of RAM in each machine). Then, all $B$-smooth integers are accumulated in a big matrix: one row per $B$-smooth value $s$, one column per prime $r$ smaller than $B$. The slot at row $s$ and column $r$ is a 1 if the factorization of $s$ includes $r$ with an odd exponent; otherwise, this is a 0. The matrix reduction step tries to find sums of rows (in $\mathbb{Z}_2$) which yield an all-zero row (summing two rows is equivalent to multiplying the corresponding $s$ values, and an all-zero row means that the product will have even exponents for all small primes, hence an obvious square).
The sieving will work in a reasonable time if $B$ is sufficiently big (it is easier to find $B$-numbers if you allow bigger "small primes"). On the other hand, the matrix reduction step will have good probability of finding full relations (products of $s$ values which are obvious squares) only if we have found more than $B$ such $B$-numbers; and the final matrix will have size $B^2$, which can become unbearably huge. So there is a trade-off. It has been proven (given some "reasonable" assumptions) that the optimal choice leads to a running complexity of $L_n[1/2,1]$.
A variant is known as the Multiple Polynomial Quadratic Sieve, in which $S$ may accept other kinds of integer, beyond the "$t^2-n$" format. See the main paper from Silverman.
Factoring with Elliptic Curves
The ECM factorization algorithm relies on the following idea: we compute points on an elliptic curve, using values modulo $n$ as if $n$ was prime (which it is not), fervently hoping that things will go sour at some point: we want to hit a value which is not invertible modulo $n$, because then a simple GCD will yield a non-trivial factor of $n$.
An Elliptic Curve is the set of points $(X,Y)$, where $X$ and $Y$ are from a field, such that a given cubic equation holds, usually $Y^2 = X^3 + aX + b$ for some constants $a$ and $b$. On such a set of points, we can define a group law; this requires a "neutral point", an extra conventional point called "point at infinity" which does not have $X$ and $Y$ coordinates in the field. The EC group law is easily computable, with formulas which imply a division (pay attention, this is the interesting point for ECM): to add point $(X_1,Y_1)$ to point $(X_2,Y_2)$, we must divide some value with $X_2 - X_1$. When we add two points with the same $X$ coordinate but not the same $Y$, we get the point at infinity (which somehow explains its name: we are "dividing by zero").
Since we can add points together, we can define the multiplication of a point by an integer: to multiply $P$ by $f$, we repeatedly add $P$ to itself ($f-1$ times). This can be done efficiently with a double-and-add algorithm. If we work with a finite field, then the curve is a finite group, and this implies that when adding $P$ to itself we necessarily end up with the point at infinity. Actually, any point $P$ has an order, which is an integer $d$ such that $fP$ is the point at infinity whenever $f$ is a multiple of $d$.
Integers modulo $n$ are not a field. However, if $n = pq$, then, when we compute with curve points with coordinates modulo $n$, we are actually computing points over two curves simultaneously: the curve in the field of integers modulo $p$, and the curve in the field of integers modulo $q$. This is what the Chinese Remainder Theorem is all about. So the ECM works like this:
The ECM relies on the hope that the point on the curve modulo $p$ (but not modulo $q$) will have a $B$-smooth order; thus, multiplying by all the $r^x$ will reach modulo $p$ (but not modulo $q$) the point at infinity, i.e. a "division by zero". Since we work modulo $n$, we will notice that division by zero as a case of "inversion modulo $n$ does not work".
The boundary $B$ is configured so that we do not spend too much time on a given curve. If we exhaust all small primes lower than $B$, then we try again with another curve (other random $a$ and $b$ constants).
There are variants which can give a boost to the performance of ECM; see this report for details.
The running complexity on a "balanced" integer (a RSA modulus $n = pq$ where $p$ and $q$ have the same size) is similar to that of the quadratic sieve. However, the complexity of ECM primarily depends on the size of the smallest factor of $n$, not the size of $n$, so this is the algorithm of choice for attacking big "unbalanced" integers (e.g. integers which have not been specially generated as RSA modulus).
Number Field Sieve
The Number Field Sieve is a very complex algorithm which I will not attempt to detail here, if only because I am quite sure that I would not get it right. As an extreme over-simplification, NFS is like QS with polynomials instead of integers everywhere. It relies on quite of lot of number theory. However, it still has the two basic steps:
An extra initialization step is needed to choose the parameters; it is often known as "polynomial selection" and requires quite a lot of thinking and non-negligible CPU work.
The running time of NFS on random integers (known as the General Number Field Sieve) is $L_n[1/3,c]$ for a constant $c = (64/9)^{1/3}$. It is faster than QS and ECM for integers larger than about 350 bits; all factorization records beginning with RSA-130 (430 bits) up to and including the current RSA-768 (768 bits) used GNFS. There is a variant called SNFS (Special Number Field Sieve) which is applicable only to integers which have a special format (and thus not applicable to RSA key cracking), but which has a better complexity ($L_n[1/3,c]$ with $c = (32/9)^{1/3}$, which means that SNFS can potentially factor integers twice bigger than GNFS). SNFS was used to factor a 1024-bit integer which was a divisor of $2^{1039}-1$.
For big integers, the bottleneck in factorization is the matrix reduction step, which requires terabytes of very fast RAM and cannot be easily distributed. Rumor has it that the polynomial selection for a 1024-bit "general" integer factorization has begun, but if the sieving step appears doable (though it will take several years), nobody knows yet how the matrix reduction step will be performed (even accounting for what five or ten years of technological advances will bring us).
Quantum Computers
Shor's algorithm easily factorizes very big integers. Its only drawback is that it works only on a quantum computer, which does not exist (yet).
On Scientific Progress
We may note that QS, ECM and NFS are all algorithms from the 1980s. No new, efficient algorithm has been discovered in the last 20 years. However, many optimizations have been discovered in the meantime, leading to algorithm variants (e.g. MPQS, ECM with "stage 2"...) which are widely faster than their original description, so there has been substantial progress -- but description of this progress requires going into the technical details of each algorithm.
For numbers over about 115 (decimal) digits, the best algorithm currently known in the General Number Field Sieve (GNFS – sometimes just called the Number Field Sieve, though there's also a Special Number Field Sieve for factoring numbers of a special form).
The GNFS, unfortunately, is an exceedingly complex algorithm, and I don't know of any online tutorial that gives enough detail to even begin to implement it (most give about a rather vague summary of a sentence or two). While it doesn't have (even close to) enough to implement the algorithm yourself, the Wikipedia entry for the GNFS has links to a few working implementations.
Be aware, however, that factoring a 115+ digit number with the GNFS requires a lot of RAM – more than most people have available, and it accesses the data randomly enough that virtual memory is pretty useless for it.
For somewhat smaller numbers, the next choice is the multiple polynomial quadratic sieve (MPQS). This isn't exactly a trivial algorithm either, but the Wikipedia entry (for one example) looks like it's probably sufficient to implement it (and it also has links to some implementations).
You may already be aware of this but have a look at the following article relating to different integer factorization algorithms. It is a bit outdated, however, it should give you an idea of the different algorithms available, and the theory behind them.
Integer Factorization Algorithms by C. Barnes, 2004
Note that if you do a Google search, you should be able to find the PDF of this article.
You may also want to have a look at the following link. I think it more directly answers your question about the fastest integer factorization algorithm, as well as providing references to other integer factorization algorithms.
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
