-- |
-- Module:      Math.NumberTheory.Powers.Modular
-- Copyright:   (c) 2017 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Modular powers (a. k. a. modular exponentiation).
--

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@ @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 'Math.NumberTheory.Moduli.Class.powMod' and 'Math.NumberTheory.Moduli.Class.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) -- correct
-- 1018105167100379328
-- >>> powMod 3 101 (2^60-1 :: Int) -- incorrect due to overflow
-- 1115647832265427613
-- >>> powModInt 3 101 (2^60-1 :: Int) -- correct
-- 1018105167100379328
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
  #-}

-- Work around https://ghc.haskell.org/trac/ghc/ticket/14085
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
  #-}

-- | Specialised version of 'powMod', able to handle large moduli correctly.
--
-- >>> powModWord 3 101 (2^60-1)
-- 1018105167100379328
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)

-- | Specialised version of 'powMod', able to handle large moduli correctly.
--
-- >>> powModInt 3 101 (2^60-1)
-- 1018105167100379328
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)