arithmoi-0.8.0.0: Efficient basic number-theoretic functions.

Copyright (c) 2017 Andrew Lelechenko MIT Andrew Lelechenko Provisional Non-portable (GHC extensions) None Haskell2010

Math.NumberTheory.Powers.Modular

Description

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

Synopsis

# 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 :: Int64)
1115647832265427613 -- incorrect due to overflow
>>> powModInt 3 101 (2^60-1 :: Int)
1018105167100379328 -- correct


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

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


powModInt :: Int -> Int -> Int -> Int Source #

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

> powModInt 3 101 (2^60-1)

1018105167100379328