ClassTests.hs

-- |
-- Module:      Math.NumberTheory.Moduli.ClassTests
-- Copyright:   (c) 2016 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Tests for Math.NumberTheory.Moduli.Class
--

{-# LANGUAGE DataKinds       #-}

{-# OPTIONS_GHC -fno-warn-type-defaults #-}

module Math.NumberTheory.Moduli.ClassTests
  ( testSuite
  ) where

import Test.Tasty
import qualified Test.Tasty.QuickCheck as QC

import Data.Maybe
import Numeric.Natural

import Math.NumberTheory.Moduli hiding (invertMod)
import Math.NumberTheory.TestUtils

invertMod :: Integer -> Integer -> Maybe SomeMod
invertMod x m = invertSomeMod (x `modulo` fromInteger m)

powerMod :: Integral a => Integer -> a -> Integer -> SomeMod
powerMod b e m = (b `modulo` fromInteger m) ^ e

-- | Check that 'invertMod' inverts numbers modulo.
invertModProperty :: AnySign Integer -> Positive Integer -> Bool
invertModProperty (AnySign k) (Positive m) = case invertMod k m of
  Nothing            -> k `rem` m == 0 || gcd k m > 1
  Just InfMod{}      -> False
  Just (SomeMod inv) -> gcd k m == 1 && k * getVal inv `mod` m == 1 `mod` m

-- | Check that 'powerMod' is multiplicative by first argument.
powerModProperty2 :: (Integral a) => NonNegative a -> AnySign Integer -> AnySign Integer -> Positive Integer -> Bool
powerModProperty2 (NonNegative e) (AnySign b1) (AnySign b2) (Positive m)
  =  e < 0 && (isNothing (invertMod b1 m) || isNothing (invertMod b2 m))
  || pm1 * pm2 == pm12
  where
    pm1  = powerMod b1  e m
    pm2  = powerMod b2  e m
    pm12 = powerMod (b1 * b2) e m

-- | Check that 'powerMod' is additive by second argument.
powerModProperty3 :: (Integral a) => NonNegative a -> NonNegative a -> AnySign Integer -> Positive Integer -> Bool
powerModProperty3 (NonNegative e1) (NonNegative e2) (AnySign b) (Positive m)
  =  (e1 < 0 || e2 < 0) && isNothing (invertMod b m)
  || e2 >= 0 && e1 + e2 < e1 -- check overflow
  || e1 >= 0 && e1 + e2 < e2 -- check overflow
  || e2 <= 0 && e1 + e2 > e1 -- check overflow
  || e1 <= 0 && e1 + e2 > e2 -- check overflow
  || pm1 * pm2 == pm12
  where
    pm1  = powerMod b e1 m
    pm2  = powerMod b e2 m
    pm12 = powerMod b (e1 + e2) m

-- | Specialized to trigger 'powerModInteger'.
powerModProperty2_Integer :: NonNegative Integer -> AnySign Integer -> AnySign Integer -> Positive Integer -> Bool
powerModProperty2_Integer = powerModProperty2

-- | Specialized to trigger 'powerModInteger'.
powerModProperty3_Integer :: NonNegative Integer -> NonNegative Integer -> AnySign Integer -> Positive Integer -> Bool
powerModProperty3_Integer = powerModProperty3

someModAddProperty :: Integer -> Positive Natural -> Integer -> Positive Natural -> Bool
someModAddProperty x1 (Positive m1) x2 (Positive m2) = case x1 `modulo` m1 + x2 `modulo` m2 of
  SomeMod z -> getMod z == m3 && getVal z == x3
  InfMod{}  -> False
  where
    m3 = toInteger $ m1 `gcd` m2
    x3 = (x1 + x2) `mod` m3

someModSubProperty :: Integer -> Positive Natural -> Integer -> Positive Natural -> Bool
someModSubProperty x1 (Positive m1) x2 (Positive m2) = case x1 `modulo` m1 - x2 `modulo` m2 of
  SomeMod z -> getMod z == m3 && getVal z == x3
  InfMod{}  -> False
  where
    m3 = toInteger $ m1 `gcd` m2
    x3 = (x1 - x2) `mod` m3

someModMulProperty :: Integer -> Positive Natural -> Integer -> Positive Natural -> Bool
someModMulProperty x1 (Positive m1) x2 (Positive m2) = case (x1 `modulo` m1) * (x2 `modulo` m2) of
  SomeMod z -> getMod z == m3 && getVal z == x3
  InfMod{}  -> False
  where
    m3 = toInteger $ m1 `gcd` m2
    x3 = (x1 * x2) `mod` m3

sameSomeModMulProperty :: Integer -> Integer -> Positive Natural -> Bool
sameSomeModMulProperty x1 x2 (Positive m) = case (x1 `modulo` m) * (x2 `modulo` m) of
  SomeMod z -> getMod z == toInteger m && getVal z == x3
  InfMod{}  -> False
  where
    x3 = (x1 * x2) `mod` toInteger m

sameSomeModMulHugeProperty :: Integer -> Integer -> Positive (Huge Natural) -> Bool
sameSomeModMulHugeProperty x1 x2 (Positive (Huge m)) = case (x1 `modulo` m) * (x2 `modulo` m) of
  SomeMod z -> getMod z == toInteger m && getVal z == x3
  InfMod{}  -> False
  where
    x3 = (x1 * x2) `mod` toInteger m

sameSomeModMulHugeAllProperty :: Huge Integer -> Huge Integer -> Positive (Huge Natural) -> Bool
sameSomeModMulHugeAllProperty (Huge x1) (Huge x2) (Positive (Huge m)) = case (x1 `modulo` m) * (x2 `modulo` m) of
  SomeMod z -> getMod z == toInteger m && getVal z == x3
  InfMod{}  -> False
  where
    x3 = (x1 * x2) `mod` toInteger m

someModNegProperty :: Integer -> Positive Natural -> Bool
someModNegProperty x1 (Positive m1) = case negate (x1 `modulo` m1) of
  SomeMod z -> getMod z == m3 && getVal z == x3
  InfMod{}  -> False
  where
    m3 = toInteger m1
    x3 = negate x1 `mod` m3

someModAbsSignumProperty :: Integer -> Positive Natural -> Bool
someModAbsSignumProperty x (Positive m) = z == abs z * signum z
  where
    z = x `modulo` m

infModAddProperty :: Integer -> Positive Natural -> Integer -> Bool
infModAddProperty x1 (Positive m1) x2 = case x1 `modulo` m1 + fromInteger x2 of
  SomeMod z -> getMod z == m3 && getVal z == x3
  InfMod{}  -> False
  where
    m3 = toInteger m1
    x3 = (x1 + x2) `mod` m3

infModSubProperty :: Integer -> Positive Natural -> Integer -> Bool
infModSubProperty x1 (Positive m1) x2 = case x1 `modulo` m1 - fromInteger x2 of
  SomeMod z -> getMod z == m3 && getVal z == x3
  InfMod{}  -> False
  where
    m3 = toInteger m1
    x3 = (x1 - x2) `mod` m3

infModMulProperty :: Integer -> Positive Natural -> Integer -> Bool
infModMulProperty x1 (Positive m1) x2 = case x1 `modulo` m1 * fromInteger x2 of
  SomeMod z -> getMod z == m3 && getVal z == x3
  InfMod{}  -> False
  where
    m3 = toInteger m1
    x3 = (x1 * x2) `mod` m3

getValModProperty :: Integer -> Positive Natural -> Bool
getValModProperty x (Positive m) = case z of
  SomeMod t -> z == getVal t `modulo` getNatMod t && z == toInteger (getNatVal t) `modulo` fromInteger (getMod t)
  InfMod{} -> False
  where
    z = x `modulo` m

testSuite :: TestTree
testSuite = testGroup "Class"
  [ testSmallAndQuick "invertMod" invertModProperty
  , testGroup "powerMod"
    [ testGroup "generic"
      [ testIntegralProperty "multiplicative by base"   powerModProperty2
      , testSameIntegralProperty "additive by exponent" powerModProperty3
      ]
    , testGroup "Integer"
      [ testSmallAndQuick "multiplicative by base"  powerModProperty2_Integer
      , testSmallAndQuick "additive by exponent"    powerModProperty3_Integer
      ]
    ]
  , testGroup "Same SomeMod"
    [ testSmallAndQuick "mul" sameSomeModMulProperty
    , QC.testProperty "mul huge" sameSomeModMulHugeProperty
    , QC.testProperty "mul huge all" sameSomeModMulHugeAllProperty
    ]
  , testGroup "SomeMod"
    [ testSmallAndQuick "add" someModAddProperty
    , testSmallAndQuick "sub" someModSubProperty
    , testSmallAndQuick "mul" someModMulProperty
    , testSmallAndQuick "neg" someModNegProperty
    , testSmallAndQuick "abs" someModAbsSignumProperty
    ]
  , testGroup "InfMod"
    [ testSmallAndQuick "add" infModAddProperty
    , testSmallAndQuick "sub" infModSubProperty
    , testSmallAndQuick "mul" infModMulProperty
    ]
  , testSmallAndQuick "getVal/getMod" getValModProperty
  ]