|
In many applications, such as Public key cryptography, large prime numbers are needed. The usual algorithm to generate prime numbers is to just generate a random odd number and test it for primality. However, primality tests are slow. If the user does not require the test to be completely accurate (say, he might tolerate a 0.000000000000000001% chance a "prime" number might be composite), there are very fast algorithms, such as Fermat's Little Theorom. Fermat's Little Theorom is so-called to differentiate it from [Fermats Last Theorom]?. Basically, the test states that, if p is a prime number, then for any positive number a less than p, a^p mod p = a (that is, if you take some number a, multiply it by itself p times, then divide the result by p and take the remainder, you should get back a). Note that the opposite is not always true: if the result is a, p is not necesarily prime. However, the Contrapositive? is always true, so if the result is not a, p is not prime. So, to be reasonably sure that a number is prime, test it against several a's. (It can be shown that for each a, the chance of catching a false prime is at least 3 in 4.) In practice, exponentiation takes log-base-2 of p steps, so Fermat's test is quite fast. Proving the Little Theorom is pretty easy: we can use Mathematical induction. Basically, I will demonstrate that the algorithm works when a = 1, then that if it works for a = some number, it works for a = some number + 1, concluding that it works for all a's less than p. Before I start, I need to prove (sorta a sideshow) that (a + b)^n mod p = a^n + b^n mod p when p is prime. (Does anyone know how to get superscript on this system?) The [Binomial theorom]? tells us that (a + b)^n is a^n + b^n + a bunch of nCr's times a^something times b^something. nCr is in this case pCr (since we're working with p) which equals p(p-1)(p-2)(p-3) ... (r terms) all divided by r! Since r is less than p, and we're supposing p is prime, p cannot divide n!, so the whole term (nCr' times a^something times b^something) is a multiple of p, which means the whole term equals 0 mod p. So, (a + b)^n mod p indeed equals a^n + b^n mod p when p is prime. Back to the proof: |
|
This page was moved to Fermats little theorem. |
![[Home]](wikipedia.png)