Modular Mathematics, Powers and Roots mod m
Powers and Roots mod m
If e is coprime to φ(m),
consider the function xe.
Note that e is invertible mod φ(m).
Let d be this inverse.
Also remember that xφ(m) = 1 by Fermat's little theorem.
Now xed = xed = x1 = x.
If x and y are distinct, and coprime to m,
then xe and ye 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 eth root.
An Efficient Algorithm
If e is large, an efficient algorithm computes be mod m.
Square b again and again, producing b2, b4, b8, b16, 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;