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 $x\equiv a^b(modn)$ with $a\in 𝒰(n)$. Then, by Fermat’s theorem we have

$$a^{\varphi (n)}\equiv 1(modn),$$

so

$$x\equiv a^b{(1)}^k\equiv a^b{(a^{\varphi (n)})}^k\equiv a^{b+k\varphi (n)}(modn)$$

for any integer $k$. This means we can replace $b$ by any integer congruent to it mod $\varphi (n)$. In particular we have

$$x\equiv a^{b\%\varphi (n)}(modn)$$

where $b\%\varphi (n)$ denotes the remainder of $b$ upon division by $\varphi (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 $x^b(modn)$ whenever $b\in 𝒰(n)$. In fact, this is just $x^{b^{-1}}$ where $b^{-1}$ is an inverse to $b$ mod $\varphi (n)$. This forms the base of the RSA cryptosystem where a message $x$ is encrypted by raising it to the $b$th power, giving $x^b$, and is decrypted by raising it to the $b^{-1}$th power, giving

$${(x^b)}^{b^{-1}}\equiv x^{b{b}^{-1}},$$

which, by the above argument, is just

$$x^{b{b}^{-1}\%\varphi (n)}\equiv x,$$

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