[Cryptography] factoring small(ish) numbers

Hanno Böck hanno at hboeck.de
Tue Oct 14 03:35:05 EDT 2014


Am Mon, 13 Oct 2014 19:23:24 -0400
schrieb Jonathan Katz <jkatz at cs.umd.edu>:

> 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."
> 
> One can debate what "easily" means, but for my purposes I am thinking
> of something where (1) the factoring is done on a single, standard
> PC, (2) in less than a month, using (3) code that is either readily
> available or could be written by a talented undergraduate CS student.

The best algorithm for factoring is the general number field sieve.
There's some code available [1], however it's not "ready-to-use" and
requires some manual steps.

I think factoring 512 bit is what's "doable". People have been doing
this on their home PCs for quite a while [2].
768 bit is still challenging and probably not something you do at home.


[1] http://www.math.ttu.edu/~cmonico/software/ggnfs/
[2] https://en.wikipedia.org/wiki/TI-84_Plus_series
-- 
Hanno Böck
http://hboeck.de/

mail/jabber: hanno at hboeck.de
GPG: BBB51E42
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141014/a07c2001/attachment.sig>


More information about the cryptography mailing list