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 _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users