Math.NumberTheory.Powers.Modular

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

Documentation

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

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.

>>> powMod 2 3 5
3
>>> powMod 3 12345678901234567890 1001
1

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.

>>> powMod 3 101 (2^60-1 :: Integer)
1018105167100379328 -- correct
>>> powMod 3 101 (2^60-1 :: Int)
1115647832265427613 -- incorrect due to overflow
>>> powModInt 3 101 (2^60-1 :: Int)
1018105167100379328 -- correct

powModWord :: Word -> Word -> Word -> Word

Specialised version of powMod, able to handle large moduli correctly.

>>> powModWord 3 101 (2^60-1)
1018105167100379328

powModInt :: Int -> Int -> Int -> Int

Specialised version of powMod, able to handle large moduli correctly.

> powModInt 3 101 (2^60-1)

1018105167100379328