content: -- |
  -- Module:      Math.NumberTheory.Moduli.JacobiTests
  -- Copyright:   (c) 2016 Andrew Lelechenko
  -- Licence:     MIT
  -- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
  --
  -- Tests for Math.NumberTheory.Moduli.Jacobi
  --
  
  {-# OPTIONS_GHC -fno-warn-type-defaults #-}
  
  module Math.NumberTheory.Moduli.JacobiTests
    ( testSuite
    ) where
  
  import Test.Tasty
  
  import Data.Bits
  
  import Math.NumberTheory.Moduli.Sqrt
  import Math.NumberTheory.TestUtils
  
  -- https://en.wikipedia.org/wiki/Jacobi_symbol#Properties, item 2
  jacobiProperty2 :: (Integral a, Bits a) => AnySign a -> (MyCompose Positive Odd) a -> Bool
  jacobiProperty2 (AnySign a) (MyCompose (Positive (Odd n)))
    =  a + n < a -- check overflow
    || jacobi a n == jacobi (a + n) n
  
  -- https://en.wikipedia.org/wiki/Jacobi_symbol#Properties, item 3
  jacobiProperty3 :: (Integral a, Bits a) => AnySign a -> (MyCompose Positive Odd) a -> Bool
  jacobiProperty3 (AnySign a) (MyCompose (Positive (Odd n))) = case jacobi a n of
    MinusOne -> a `gcd` n == 1
    Zero     -> a `gcd` n /= 1
    One      -> a `gcd` n == 1
  
  doesProductOverflow :: Integral a => a -> a -> Bool
  doesProductOverflow x y = abs (toInteger (x * y)) < abs (toInteger x * toInteger y)
  
  -- https://en.wikipedia.org/wiki/Jacobi_symbol#Properties, item 4
  jacobiProperty4 :: (Integral a, Bits a) => AnySign a -> AnySign a -> (MyCompose Positive Odd) a -> Bool
  jacobiProperty4 (AnySign a) (AnySign b) (MyCompose (Positive (Odd n))) =
    doesProductOverflow a b ||
    jacobi (a * b) n == jacobi a n <> jacobi b n
  
  -- https://en.wikipedia.org/wiki/Jacobi_symbol#Properties, item 5
  jacobiProperty5 :: (Integral a, Bits a) => AnySign a -> (MyCompose Positive Odd) a -> (MyCompose Positive Odd) a -> Bool
  jacobiProperty5 (AnySign a) (MyCompose (Positive (Odd m))) (MyCompose (Positive (Odd n))) =
    doesProductOverflow m n ||
    jacobi a (m * n) == jacobi a m <> jacobi a n
  
  -- https://en.wikipedia.org/wiki/Jacobi_symbol#Properties, item 6
  jacobiProperty6 :: (Integral a, Bits a) => (MyCompose Positive Odd) a -> (MyCompose Positive Odd) a -> Bool
  jacobiProperty6 (MyCompose (Positive (Odd m))) (MyCompose (Positive (Odd n))) = gcd m n /= 1 || jacobi m n <> jacobi n m == (if m `mod` 4 == 1 || n `mod` 4 == 1 then One else MinusOne)
  
  -- https://en.wikipedia.org/wiki/Jacobi_symbol#Properties, item 7
  jacobiProperty7 :: (Integral a, Bits a) => (MyCompose Positive Odd) a -> Bool
  jacobiProperty7 (MyCompose (Positive (Odd n))) =
    jacobi (-1) n == if n `mod` 4 == 1 then One else MinusOne
  
  jacobiProperty7_Int :: (MyCompose Positive Odd) Int -> Bool
  jacobiProperty7_Int = jacobiProperty7
  
  jacobiProperty7_Integer :: (MyCompose Positive Odd) Integer -> Bool
  jacobiProperty7_Integer = jacobiProperty7
  
  -- https://en.wikipedia.org/wiki/Jacobi_symbol#Properties, item 8
  jacobiProperty8 :: (Integral a, Bits a) => (MyCompose Positive Odd) a -> Bool
  jacobiProperty8 (MyCompose (Positive (Odd n))) =
    even n ||
    jacobi 2 n == if n `mod` 8 == 1 || n `mod` 8 == 7 then One else MinusOne
  
  jacobiProperty9 :: (Integral a, Bits a, Bounded a) => (MyCompose Positive Odd) a -> Bool
  jacobiProperty9 (MyCompose (Positive (Odd n))) =
    jacobi m n == jacobi (toInteger m) (toInteger n)
    where
      m = minBound
  
  jacobiProperty9_Int :: (MyCompose Positive Odd) Int -> Bool
  jacobiProperty9_Int = jacobiProperty9
  
  testSuite :: TestTree
  testSuite = testGroup "Jacobi"
    [ testSameIntegralProperty  "same modulo n"                jacobiProperty2
    , testSameIntegralProperty  "consistent with gcd"          jacobiProperty3
    , testSameIntegralProperty3 "multiplicative 1"             jacobiProperty4
    , testSameIntegralProperty3 "multiplicative 2"             jacobiProperty5
    , testSameIntegralProperty  "law of quadratic reciprocity" jacobiProperty6
    , testSmallAndQuick         "-1 Int"                       jacobiProperty7_Int
    , testSmallAndQuick         "-1 Integer"                   jacobiProperty7_Integer
    , testIntegralProperty      "2"                            jacobiProperty8
    , testSmallAndQuick         "minBound Int"                 jacobiProperty9_Int
    ]
  