4096 bit keys

[vedaal at nym.hush.com]

Jerome Baum jerome at jeromebaum.com wrote on
Tue Mar 22 23:28:31 CET 2011 :

>They  go  up with  O(log(n))  where n  is  the number,  or
something like it, right? 


The Prime Number Theorem:

Pi(x) ~ x/ln(x)
(Pi(x) refers to the number of primes up to and including the 
integer x
 
~ means approximately.


Formally, the proof is for Lim x-->infinity  Pi(x)/[x/ln(x)] = 1

There is an interesting related Prime Number theorem that might 
help you eliminate which intervals of numbers need to be factored:

For any positive integer n, there exists an integer a, such that 
the n consecutive integers:
[ a, a+1, a+2, ..., a+(n-1)] 
are all composite.

a = (n+1)! + 2

(For anyone interested, the proof is in a free and easily readable, 
downloadable text on Elementary Number Theory by W. Edwin Clark
http://shell.cas.usf.edu/~wclark/  )

Now, while there is no simple formula that can generate all primes, 
it is very simple to generate factorials for all n up to the point 
where n! is less than the square root of 2^4096.

So, in your spare time, ;-)  you can eliminate a large amount of 
intervals where factoring is unnessary.

(But even after all that, you may find that a 4096 bit key is still 
pretty much unfactorable for the not-too-near future. ;-)  )


vedaal