> The reason that this answe ris somewhat of a lie is that the > prime numbers > used in cryptography are usually NOT the "largest prime > numbers in the > world" at the time, nor too close to it. (It'd be easy to > crack such keys > if they were limited to the 1000 largest primes -- then > you're down to a > trial and error set of about a million combinations).
Actually, it's about a thousand times easier than that if all you want to do is break a particular key. Use trial division by each of a thousand primes and see which gives no remainder. You get the other prime for free. Actually, it's even easier than that! The thousand largest primes are of disparate lengths. A table containing the lengths of the million possible combinations would be both small and easy to search. Look up the length of the key and you will usually know which two primes produced it and no division is required. Where two or more combinations give the same length of key, one single-precision multiplication of the leading few bits of the primes concerned will usually distinguish between them and no multiprecision arithmetic is required. Paul _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
