On Wednesday 23 March 2011, ved...@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
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
