4096 bit keys

[Ingo Klöcker]

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

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>