module Math.NumberTheory.Powers.Modular
{-# DEPRECATED "Use Data.Mod or Data.Mod.Word instead" #-}
( powMod
, powModWord
, powModInt
) where
import GHC.Natural (powModNatural)
import qualified GHC.Integer.GMP.Internals as GMP (powModInteger)
import Math.NumberTheory.Utils.FromIntegral
powMod :: (Integral a, Integral b) => a -> b -> a -> a
powMod :: forall a b. (Integral a, Integral b) => a -> b -> a -> a
powMod a
x b
y a
m
| a
m forall a. Ord a => a -> a -> Bool
<= a
0 = forall a. HasCallStack => [Char] -> a
error [Char]
"powModInt: non-positive modulo"
| b
y forall a. Ord a => a -> a -> Bool
< b
0 = forall a. HasCallStack => [Char] -> a
error [Char]
"powModInt: negative exponent"
| Bool
otherwise = forall {a}. Integral a => a -> a -> a -> a
f (a
x forall a. Integral a => a -> a -> a
`rem` a
m) b
y a
1 forall a. Integral a => a -> a -> a
`mod` a
m
where
f :: a -> a -> a -> a
f a
_ a
0 a
acc = a
acc
f a
b a
e a
acc = a -> a -> a -> a
f (a
b forall a. Num a => a -> a -> a
* a
b forall a. Integral a => a -> a -> a
`rem` a
m) (a
e forall a. Integral a => a -> a -> a
`quot` a
2)
(if forall a. Integral a => a -> Bool
odd a
e then a
b forall a. Num a => a -> a -> a
* a
acc forall a. Integral a => a -> a -> a
`rem` a
m else a
acc)
{-# INLINE [1] powMod #-}
{-# RULES
"powMod/Integer" powMod = powModInteger
#-}
powModInteger :: Integer -> Integer -> Integer -> Integer
powModInteger :: Integer -> Integer -> Integer -> Integer
powModInteger Integer
b Integer
e Integer
m = Integer -> Integer -> Integer -> Integer
GMP.powModInteger (Integer
b forall a. Integral a => a -> a -> a
`mod` Integer
m) Integer
e Integer
m
{-# RULES
"powMod/Natural" powMod = powModNatural
"powMod/Word" powMod = powModWord
"powMod/Int" powMod = powModInt
#-}
powModWord :: Word -> Word -> Word -> Word
powModWord :: Word -> Word -> Word -> Word
powModWord Word
b Word
e Word
m = forall a. Num a => Integer -> a
fromInteger forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Integer -> Integer
GMP.powModInteger (forall a. Integral a => a -> Integer
toInteger Word
b) (forall a. Integral a => a -> Integer
toInteger Word
e) (forall a. Integral a => a -> Integer
toInteger Word
m)
powModInt :: Int -> Int -> Int -> Int
powModInt :: Int -> Int -> Int -> Int
powModInt Int
x Int
y Int
m
| Int
m forall a. Ord a => a -> a -> Bool
<= Int
0 = forall a. HasCallStack => [Char] -> a
error [Char]
"powModInt: non-positive modulo"
| Int
y forall a. Ord a => a -> a -> Bool
< Int
0 = forall a. HasCallStack => [Char] -> a
error [Char]
"powModInt: negative exponent"
| Bool
otherwise = Word -> Int
wordToInt forall a b. (a -> b) -> a -> b
$ Word -> Word -> Word -> Word
powModWord (Int -> Word
intToWord (Int
x forall a. Integral a => a -> a -> a
`mod` Int
m)) (Int -> Word
intToWord Int
y) (Int -> Word
intToWord Int
m)