Factoring is a very active field of research among mathematicians and computer scientists; the best factoring algorithms are mentioned below with some references and their big-O asymptotic efficiency. O notation measures how fast an algorithm is; it gives an upper bound on the number of operations (to order of magnitude) in terms of n, the number to be factored, and p, a prime factor of n. For textbook treatment of factoring algorithms, see [Knu81] [Kob94] [LL90] [Bre89]; for a detailed explanation of big-O notation, see [CLR90].
Factoring algorithms come in two flavors, special purpose and general purpose; the efficiency of the former depends on the unknown factors, whereas the efficiency of the latter depends on the number to be factored. Special-purpose algorithms are best for factoring numbers with small factors, but the numbers used for the modulus in the RSA system do not have any small factors. Therefore, general-purpose factoring algorithms are the more important ones in the context of cryptographic systems and their security.
Special-purpose factoring algorithms include the Pollard rho method
[Pol75], with expected running time 
, and the Pollard p - 1 method
[Pol74], with running time O(p'), where p' is the
largest prime factor of p - 1. Both of these take an amount of time
that is exponential in the size of p, the prime factor that they
find; thus these algorithms are too slow for most factoring jobs. The elliptic
curve method (ECM) [Len87] is superior
to these; its asymptotic running
time is 
. The ECM is often used in practice to find factors
of randomly generated numbers; it is not strong enough to factor a large
RSA modulus.
The best general-purpose factoring algorithm today is the number
field sieve [BLP94]
[BLZ94], which runs in time approximately
0(exp(1.9223(ln n1/3 (ln ln n2/3)). Previously, the most widely used
general-purpose
algorithm was the multiple polynomial quadratic sieve (mpqs)
[Sil87],
which has running time 
. This was due to initial inefficiencies
that made the number field sieve less efficient than the quadratic sieve.
Recent improvements to the number field sieve make the number field sieve
more efficient in factoring numbers larger than about 115 digits
[DL95].
RSA-129 (see Question 51) was factored using a variation
of the quadratic sieve method. It is now estimated that if the number field
sieve had been used, it would have taken one quarter of the time.
Clearly, the number field sieve will overtake the mpqs as the most widely used factoring algorithm, as the size of the numbers being factored increases from about 130 digits, which is the current threshold of general numbers which can be factored, to 140 or 150 digits. A "general number" is one with no special form that might make it easier to factor; RSA moduli are created to be general numbers. Note that a 512-bit number has about 155 digits.
Numbers with up to 155 digits or more that have a special form can already be factored [LLM93]. The Cunningham Project [BLS88] keeps track of the factorizations of numbers with these special forms and maintains a "10 Most Wanted" list of desired factorizations. Also, a good way to survey current factoring capability is to look at recent results of the RSA Factoring Challenge (see Question 50).