| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Math.PowMod
Description
\(\mathit{base}^n \bmod x\) in a constant time using Fermet's little theorem.
TODO: Test all the functions.
Synopsis
- addMod :: Int -> Int -> Int -> Int
- subMod :: Int -> Int -> Int -> Int
- mulMod :: Int -> Int -> Int -> Int
- factMod :: Int -> Int -> Int
- powModConst :: Int -> Int -> Int -> Int
- invModConst :: Int -> Int -> Int
- divModConst :: Int -> Int -> Int -> Int
- factModsN :: Int -> Int -> Vector Int
- bcMod :: Int -> Int -> Int -> Int
Documentation
powModConst :: Int -> Int -> Int -> Int #
\(O(W)\) \(\mathit{base} ^ \mathit{power} \bmod \mathit{modulo}\) using binary lifting.
invModConst :: Int -> Int -> Int #
\(O(W)\) \(x / d \bmod p\) using Fermat's little theorem and binary lifting.