Re: A89: Linux Port for 89/92

[Prev][Next][Index][Thread]

Re: A89: Linux Port for 89/92


 > Aren't there already programs to find if obscenly large numbers are prime or
 > not (I know I've run across a couple)?  Don't these programs accomplish this
 > task by attempting to find the factors?  Would that be a viable method for
 > finding the factors to the 512 bit excryption key?

No. They don't try to factor the number. They operate using
probabilistic methods to test if a number is a prime or not with a
certain probability. You can recursively apply them to decrease the
probability of false result to be smaller than any chosen threshold.

Here's one (from the book I mentioned), called the Lehman test. It is
a simple test to decide if 'p' is a prime number or not:

1) choose a random number 'a' less than 'p'.
2) calculate x = a^((p-1)/2) mod p
3) if x is not 1 or -1 mod p, then p is not a prime
4) is x is 1 or -1 mod p then the likelihood of p not being prime is
   less than 50%.
   
So, if 4) was the case, 'a' is a so-called witness for p being a
possible prime. Repeat the test t times. If you have t independent
witnesses, each with a 50% 'trustworthiness' it gives you a 2^-t chance
of falsely declaring p a prime (i.e. the probability that all tests
falsely declared p a possible prime).
So, you just run say 1000 tests, all saying that p is a prime, then
you can say that you are 99.999 ... (300 9-s) % percent sure that p is 
indeed a large prime.

This is not the method used in practice, the Rabin - Miller method is
just as easy as that one but the probability of a failed test is only
25%, that is the method converges much faster. The best methods can
give you a less than 1/2^51 probability of error in only 6 tests for
256-bit numbers. On a Sparc-II (not a very quick machine) finding a
256-bit prime took 2.8 sec, a 1024 bit one about 5 minutes using the
Rabin-Miller test.

That's why you can test (and, of course, generate - choose a random
number, test it if it's prime, choose an other one if it isn't) large
primes very quickly indeed but you can't factor them if they fail the 
test. This is what makes the whole RSA method feasible - it's very
easy to come up with the two primes to compose n but it is very hard 
to factor n back to the two primes.

Also note, that while exponentiation of very large numbers (a^n) may
seem to be troublesome, it is in fact not that complex: you can get
it done with only log n multiplications and additions.

Regards,

Zoltan
Follow-Ups: References: