Factoring

Lehman's method of factoring

(Sorry about the quality.)

Page from a book on Lehman's Method

Example of the Quadratic Sieve

  46 47 48 49 50 51 52 53 54 55 56
squares mod 2041 75 168 263 360 459 560 663 768 875 984 1095
factors                      
2   84   180   280   384   492  
3 25     60     221     164  
4   42       140       82  
5 5         28         219
7   6             125    
8   3               41  
9       20              
16                      
25 1                    

Log base 2 version

  46 47 48 49 50 51 52 53 54 55 56
squares mod 2041 75 168 263 360 459 560 663 768 875 984 1095
log2 6 7 8 8 9 9 9 10 10 10 10
2   6.0   7.0   8.0   9.0   9.0  
3 4.4     5.4     7.4     7.4  
4   5.0       7.0       6.4  
5 2.1         4.7         7.7
7   2.2             7.2    
8   1.2               5.4  
9       3.8              
16                      
25 -0.2                    

Estimated times to factor an RSA key

open projects
1999    512 bits  3.7 months
2004 1024 bits 5 days
1280 bits 18 months
2014 1280 bits <11 days maybe 100 times faster?
1536 bits <2 years maybe 100 times faster?
covert projects
1999   512 bits <1 year
2004 1024 bits 4 months
1280 bits 30 years
2014 1280 bits <4 months maybe 10 times faster?
1536 bits <20 years maybe 10 times faster?

These numbers are based on information in The future of integer factorization, by Andrew Odlyzko.