4096 bit keys

Ingo Klöcker kloecker at kde.org
Wed Mar 23 22:39:05 CET 2011

```On Wednesday 23 March 2011, vedaal at nym.hush.com wrote:
> 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,
> 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.

Pretty much exactly 300 since 300! < 2^2048 < 301!.

So, out of 2^2048 candidates you eliminate 1+2+...+300 = 300*301/2 =
45150 candidates which lie in those intervals. Impressive!

Regards,
Ingo
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: </pipermail/attachments/20110323/9e417362/attachment-0001.pgp>
```