In [2]: pow?
Signature: pow(x, y, z=None, /)
Docstring:
Equivalent to x**y (with two arguments) or x**y % z (with three arguments)

Some types, such as ints, are able to use a more efficient algorithm when
invoked using the three argument form.
Type:      builtin_function_or_method

In [3]: pow(2, 100, 3)
Out[3]: 1


${x}^{2}={x}\cdot{x}$ ${x}^{3}={x}\cdot{x}^{2}$ ${x}^{4}={x}\cdot{x}^{3}$

pow' :: Integral a => a -> a -> a
pow' x 0 = 1
pow' x n = x * pow' x (n-1)


${x}^{4}={x}^2\cdot{x}^{2}$

1) n 为偶数
${x}^{n}=({x}^{n/2})^{2}$ 2) n 为奇数
${x}^{n}={x}*{x}^{n-1}$

square :: Integral a => a -> a
square x = x * x
pow' :: Integral a => a -> a -> a
pow' _ 0 = 1
pow' x n
| even n = square \$ pow' x (n div 2)
| otherwise = x * pow' x (n-1)


${a}\cdot{b}\bmod{b}=({a}\cdot({b}\bmod{m)})%{m}$

${x}^{2}\bmod{m}=({x}\cdot({x}\bmod{m}))\bmod{m}$

${x}^{3}\bmod{m}=({x}\cdot({x}^2\bmod{m}))\bmod{m}$

${x}^{4}\bmod{m}=({x}\cdot({x}^3\bmod{m}))\bmod{m}$

(我实在不想写 LaTex 了 QAQ)

powMod :: Integral a => a -> a -> a -> a
powMod _ 0 _ = 1
powMod x 1 m = x mod m
powMod x n m
| even n = powMod modSquare (ndiv2) m
| otherwise = (x * powMod modSquare ((n-1)div2) m) mod m
where modSquare = x * (x mod m)