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.
>>>
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