On 3/22/11 5:50 PM, Jerome Baum wrote: > Actually none of this is that important. If you can do the division in > half a second instead of one, that only halves the time you need. All I > have to do is add one bit to my key size and you're back to square > one.
You have to add one bit to your *effective* key size. Remember, the primes are not evenly distributed: the larger you go, the more they are spread out. This is why for very small keys each additional bit gives you quite a lot of security, but as keys grow very large more and more bits have to be added to get that additional boost. As an example, there are 25 primes under 100: of all the possible values, you have to check 25% of them. But there are only 78,498 primes under one million: you only have to check 7.9% of those numbers. > The problem is the number of divisions you have to perform O(2^n) > for RSA-n. Actually it's a lot less, O(2^(n/2)) for the simple fact that > you have to divide only up to the square root, as one factor must be > smaller than that. But the kind of magnitude is still the same and it > grows pretty fast with key size. You might want to look into the General Number Field Sieve (GNFS), which is a much more efficient way of breaking RSA keys than by simple trial division. _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users