Copyright | (c) 2017 Andrew Lelechenko |
---|---|

License | MIT |

Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |

Safe Haskell | None |

Language | Haskell2010 |

Modular powers (a. k. a. modular exponentiation).

# Documentation

powMod :: (Integral a, Integral b) => a -> b -> a -> a Source #

`powMod`

`b`

`e`

`m`

computes (`b^e`

) `mod` `m`

in effective way.
An exponent `e`

must be non-negative, a modulo `m`

must be positive.
Otherwise the behaviour of `powMod`

is undefined.

`>>>`

3`powMod 2 3 5`

`>>>`

1`powMod 3 12345678901234567890 1001`

See also `powMod`

and `powSomeMod`

.

For finite numeric types (`Int`

, `Word`

, etc.)
modulo `m`

should be such that `m^2`

does not overflow,
otherwise the behaviour is undefined. If you
need both to fit into machine word and to handle large moduli,
take a look at `powModInt`

and `powModWord`

.

`>>>`

1018105167100379328 -- correct`powMod 3 101 (2^60-1 :: Integer)`

`>>>`

1115647832265427613 -- incorrect due to overflow`powMod 3 101 (2^60-1 :: Int)`

`>>>`

1018105167100379328 -- correct`powModInt 3 101 (2^60-1 :: Int)`