# 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

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,
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

```