# Modular Mathematics, Powers and Roots mod m

## Powers and Roots mod m

If e is coprime to φ(m),
consider the function x^{e}.
Note that e is invertible mod φ(m).
Let d be this inverse.
Also remember that x^{φ(m)} = 1 by Fermat's little theorem.
Now x^{ed} = x^{ed} = x^{1} = x.
If x and y are distinct, and coprime to m,
then x^{e} and y^{e} are also distinct.
If they were the same then raising them to the d power would produce the same value;
yet it reproduces x and y.
The map is one to one,
hence raising to the e power permutes all the values that are relatively prime to m.
Raising to the d power is the inverse map,
and is the same as taking the e^{th} root.
## An Efficient Algorithm

If e is large, an efficient algorithm computes b^{e} mod m.
Square b again and again, producing b^{2}, b^{4}, b^{8}, b^{16}, and so on.
Then multiply these factors together as necessary, according to the bits of e.
a = 1;
s = b;
while(e) {
if(e is odd) a = a×s mod m;
s = s×s mod m;
e = e/2;
}
return a;