Maybe if Mike is around he could answer this, or some of you other Crypto experts:

Say you have a algo like RSA public key. Now, I know if the key size is large bruteforcing would take forever and a day no matter what you do, but my question is - even if you wrote a bruteforcer, why would you actually start at the beginning and scan. I would tend to think the chances of the required value would very rarely be on the ends of the spectrum. Also very rare would be in the exact middle. I would think the best places to scan would be the lower and upper 2/3 of the number distribution.

Am I on any kind of right track of thinking here? This is how I've always thought about any type of algorithm that ppl use to lock away code, in the case of writing a bruteforcer. Wouldn't the distro be similar to the normal "chaotic" bell curve?

-niko

I am hardly an expert in the field, but I here is my answer:

The overhead of writing a key generator with chaotic functions, and keeping track of the already tested keys for not repeating too many of them would quickly neutralize any time saving advantage you might get by generating "random looking" keys.

The best way to factor large numbers (above a few hundred bits) is the Number Field Sieve. It works by finding a lot of relationships between numbers mod n and algebraic complex numbers. Algebraic numbers are those that you can get by using + - * / ^.

For example, when n=2501 then you can say 50 = i since

50^2 = 2500 = -1 mod n and i^2 = -1 in complex numbers.

You'd try to factor every number a+bi in a certain "small" range, then factor a+b*50. You put a 1 in the matrix if the exponent on a prime factor is odd, and a zero if even.

Finally, you try to find a set of rows that add to zero mod 2. With good probability, this will give you one factor.

So the brute-force part is trying every a,b in a range, but it's not testing them as potential factors of n.