computation of powers using Fermat’s little theorem
A straightforward application of Fermat’s theorem consists of rewriting the power of an integer mod . Suppose we have with . Then, by Fermat’s theorem we have
for any integer . This means we can replace by any integer congruent to it mod . In particular we have
where denotes the remainder of upon division by .
This can be used to make the computation of large powers easier. It also allows one to find an easy to compute inverse to whenever . In fact, this is just where is an inverse to mod . This forms the base of the RSA cryptosystem where a message is encrypted by raising it to the th power, giving , and is decrypted by raising it to the th power, giving
which, by the above argument, is just
the original message!
|Title||computation of powers using Fermat’s little theorem|
|Date of creation||2013-03-22 13:17:42|
|Last modified on||2013-03-22 13:17:42|
|Last modified by||basseykay (877)|