Re: A89: Linux Port for 89/92
[Prev][Next][Index][Thread]
Re: A89: Linux Port for 89/92
Where did all of this talk about the boot loader originate? Was it
suggested as a way to send the file to the calc and run the code or am I
missing something?
- Matt
Zoltan Kocsi wrote:
>
> > 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
References: