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}\pmod{n}$ with $a\in\mathcal{U}(n)$. Then, by Fermat’s theorem we have

 $a^{\phi(n)}\equiv 1\pmod{n},$

so

 $x\equiv a^{b}(1)^{k}\equiv a^{b}(a^{\phi(n)})^{k}\equiv a^{b+k\phi(n)}\pmod{n}$

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

 $x\equiv a^{b\>\%\>\phi(n)}\pmod{n}$

where $b\>\%\>\phi(n)$ denotes the remainder of $b$ upon division by $\phi(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}\pmod{n}$ whenever $b\in\mathcal{U}(n)$. In fact, this is just $x^{b^{-1}}$ where $b^{-1}$ is an inverse to $b$ mod $\phi(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^{bb^{-1}},$

which, by the above argument, is just

 $x^{bb^{-1}\>\%\>\phi(n)}\equiv x,$

the original message!

Title computation of powers using Fermat’s little theorem ComputationOfPowersUsingFermatsLittleTheorem 2013-03-22 13:17:42 2013-03-22 13:17:42 basseykay (877) basseykay (877) 5 basseykay (877) Example msc 11-00