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;