4096 bit keys
vedaal at nym.hush.com
vedaal at nym.hush.com
Wed Mar 23 20:57:06 CET 2011
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
More information about the Gnupg-users
mailing list