Fermat's Little TheoremThe crux to the RSA algorithm is another discovery by Fermat, called Fermat's little theorem. It is a statement about powers in modular arithmetic in the special case where the modular base is a prime number. The theorem is stated like this: a(p-1) = 1 (mod p) (unless a is a multiple of p) We proved this theorem in class, but just in case you'd like to check: try it out here, for a few values of p, and several values of a each time. Try also what happens if p is not prime ... (HINT: try setting a value for p and changing values for a) Fermat's Calculator
|