[Cryptography] factoring small(ish) numbers

[Viktor Dukhovni]

On Mon, Oct 13, 2014 at 07:23:24PM -0400, Jonathan Katz wrote:

> I'm curious if anyone can point me to references that would indicate values
> of n for which n-bit numbers can be factored "easily."

Are you looking at factoring RSA moduli (product of two primes with
~n/2 bits) or general $n-bit$ numbers?  Many numbers have small
factors, which are easily found by ECM with run-time dependent only
on the size of the factors not the number itself.  The remaining
large factors can be subjected to primality tests, and either found
composite or if desired proved prime.

It is only at that point that any large composites with no small
factors found by ECM should be subjected to GNFS.  Of course with
properly generated RSA moduli you'll start with GNFS immediately.

-- 
	Viktor.