    -- |
    -- 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 a -> a -> Bool
    forall a. Ord a => a -> a -> Bool
    <= a
    0    = [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "powModInt: non-positive modulo"
      | b
    y b -> b -> Bool
    forall a. Ord a => a -> a -> Bool
    <  b
    0    = [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "powModInt: negative exponent"
      | Bool
    otherwise = a -> b -> a -> a
    forall {a}. Integral a => a -> a -> a -> a
    f (a
    x a -> a -> a
    forall a. Integral a => a -> a -> a
    `rem` a
    m) b
    y a
    1 a -> a -> a
    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 a -> a -> a
    forall a. Num a => a -> a -> a
    * a
    b a -> a -> a
    forall a. Integral a => a -> a -> a
    `rem` a
    m) (a
    e a -> a -> a
    forall a. Integral a => a -> a -> a
    `quot` a
    2)
          (if a -> Bool
    forall a. Integral a => a -> Bool
    odd a
    e then a
    b a -> a -> a
    forall a. Num a => a -> a -> a
    * a
    acc a -> a -> a
    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 Integer -> Integer -> Integer
    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 = Integer -> Word
    forall a. Num a => Integer -> a
    fromInteger (Integer -> Word) -> Integer -> Word
    forall a b. (a -> b) -> a -> b
    $ Integer -> Integer -> Integer -> Integer
    GMP.powModInteger (Word -> Integer
    forall a. Integral a => a -> Integer
    toInteger Word
    b) (Word -> Integer
    forall a. Integral a => a -> Integer
    toInteger Word
    e) (Word -> Integer
    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 Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = [Char] -> Int
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "powModInt: non-positive modulo"
      | Int
    y Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <  Int
    0 = [Char] -> Int
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "powModInt: negative exponent"
      | Bool
    otherwise = Word -> Int
    wordToInt (Word -> Int) -> Word -> Int
    forall a b. (a -> b) -> a -> b
    $ Word -> Word -> Word -> Word
    powModWord (Int -> Word
    intToWord (Int
    x Int -> Int -> Int
    forall a. Integral a => a -> a -> a
    `mod` Int
    m)) (Int -> Word
    intToWord Int
    y) (Int -> Word
    intToWord Int
    m)