computation of powers using Fermat’s little theorem

A straightforward application of Fermat’s theorem consists of rewriting the power of an integer mod n. Suppose we have xab(modn) with a𝒰(n). Then, by Fermat’s theorem we have




for any integer k. This means we can replace b by any integer congruentMathworldPlanetmath to it mod ϕ(n). In particular we have


where b%ϕ(n) denotes the remainder of b upon division by ϕ(n).

This can be used to make the computation of large powers easier. It also allows one to find an easy to compute inverse to xb(modn) whenever b𝒰(n). In fact, this is just xb-1 where b-1 is an inverse to b mod ϕ(n). This forms the base of the RSA cryptosystem where a message x is encrypted by raising it to the bth power, giving xb, and is decrypted by raising it to the b-1th power, giving


which, by the above argument, is just


the original message!

Title computation of powers using Fermat’s little theorem
Canonical name ComputationOfPowersUsingFermatsLittleTheorem
Date of creation 2013-03-22 13:17:42
Last modified on 2013-03-22 13:17:42
Owner basseykay (877)
Last modified by basseykay (877)
Numerical id 5
Author basseykay (877)
Entry type Example
Classification msc 11-00