It depends on the size of the numbers, and their form. Numbers
in special forms, such as a^n - b for `small’ b, are more readily
factored through specialized techniques and not necessarily related
to the difficulty of factoring in general. Hence a specific factoring
`breakthrough’ for a special number form may have no practical value
or relevance to particular instances (and those generated for use
in cryptographic systems are specifically `filtered’ to resist such
approaches.) The most important observation about factoring is that
all known algorithms require an exponential amount of time in the
_size_ of the number (measured in bits, log2(n) where `n’ is the
number). Cryptgraphic algorithms built on the difficulty of factoring
generally depend on this exponential-time property. (The distinction
of `exponential’ vs. `polynomial time’ algorithms, or NP vs. P, is a
major area of active computational research, with insights very
closely intertwined with cryptographic security.)
In October 1992 Arjen Lenstra and Dan Bernstein factored 2^523 - 1
into primes, using about three weeks of MasPar time. (The MasPar is
a 16384-processor SIMD machine; each processor can add about 200000
integers per second.) The algorithm there is called the “number field
sieve”; it is quite a bit faster for special numbers like 2^523 - 1
than for general numbers n, but it takes time only
exp(O(log^{1/3} n log^{2/3} log n)) in any case.
An older and more popular method for smaller numbers is the “multiple
polynomial quadratic sieve”, which takes time exp(O(log^{1/2} n
log^{1/2} log n))—faster than the number field sieve for small n,
but slower for large n. The breakeven point is somewhere between 100
and 150 digits, depending on the implementations.
Factorization is a fast-moving field—the state of the art just a few
years ago was nowhere near as good as it is now. If no new methods are
developed, then 2048-bit RSA keys will always be safe from
factorization, but one can’t predict the future. (Before the number
field sieve was found, many people conjectured that the quadratic
sieve was asymptotically as fast as any factoring method could be.)
