The optimal choice of factoring algorithm depends on the size of the number you want to factor. For numbers larger than a googol (10100) the GNFS (general number field sieve) algorithm is the fastest known factoring algorithm, making GNFS the algorithm of choice for trying to factor public keys for RSA encryption
The expected time required to factor a number n using the GNFS is proportional to
exp( f(n) g(n) )
where f(n) is relatively constant and g(n) varies more strongly with n. More specifically
f(n) = (64/9)1/3 + o(1)
and
g(n) = (log n)1/3 (log log n)2/3.
The notation o(1) means a term that goes to zero as n increases. Very often in practice you can ignore o(1) terms when your value of n is large. In cryptographic applications n is certainly large, at least 21024, and yet the o(1) term is still significant for values of n seen in practice. I’ve seen one source say that for keys used in practice the o(1) term is around 0.27.
Security levels
It is widely stated that factoring a 1024-bit private key is comparable in difficulty to breaking an 80-bit symmetric encryption key, i.e. that 1024-bit keys provide 80-bit security.
... continue reading