    -- |
    -- Module:      Math.NumberTheory.Moduli.JacobiSymbol
    -- Copyright:   (c) 2011 Daniel Fischer, 2017-2018 Andrew Lelechenko
    -- Licence:     MIT
    -- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
    -- Description: Deprecated
    --
    -- <https://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol>
    -- is a generalization of the Legendre symbol, useful for primality
    -- testing and integer factorization.
    --

    {-# LANGUAGE BangPatterns #-}
    {-# LANGUAGE LambdaCase   #-}

    module Math.NumberTheory.Moduli.JacobiSymbol
      ( JacobiSymbol(..)
      , jacobi
      , symbolToNum
      ) where

    import Data.Bits
    import Numeric.Natural

    import Math.NumberTheory.Utils

    -- | Represents three possible values of
    -- <https://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol>.
    data JacobiSymbol = MinusOne | Zero | One
      deriving (JacobiSymbol -> JacobiSymbol -> Bool
    (JacobiSymbol -> JacobiSymbol -> Bool)
    -> (JacobiSymbol -> JacobiSymbol -> Bool) -> Eq JacobiSymbol
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: JacobiSymbol -> JacobiSymbol -> Bool
    == :: JacobiSymbol -> JacobiSymbol -> Bool
    $c/= :: JacobiSymbol -> JacobiSymbol -> Bool
    /= :: JacobiSymbol -> JacobiSymbol -> Bool
    Eq, Eq JacobiSymbol
    Eq JacobiSymbol =>
    (JacobiSymbol -> JacobiSymbol -> Ordering)
    -> (JacobiSymbol -> JacobiSymbol -> Bool)
    -> (JacobiSymbol -> JacobiSymbol -> Bool)
    -> (JacobiSymbol -> JacobiSymbol -> Bool)
    -> (JacobiSymbol -> JacobiSymbol -> Bool)
    -> (JacobiSymbol -> JacobiSymbol -> JacobiSymbol)
    -> (JacobiSymbol -> JacobiSymbol -> JacobiSymbol)
    -> Ord JacobiSymbol
    JacobiSymbol -> JacobiSymbol -> Bool
    JacobiSymbol -> JacobiSymbol -> Ordering
    JacobiSymbol -> JacobiSymbol -> JacobiSymbol
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    $ccompare :: JacobiSymbol -> JacobiSymbol -> Ordering
    compare :: JacobiSymbol -> JacobiSymbol -> Ordering
    $c< :: JacobiSymbol -> JacobiSymbol -> Bool
    < :: JacobiSymbol -> JacobiSymbol -> Bool
    $c<= :: JacobiSymbol -> JacobiSymbol -> Bool
    <= :: JacobiSymbol -> JacobiSymbol -> Bool
    $c> :: JacobiSymbol -> JacobiSymbol -> Bool
    > :: JacobiSymbol -> JacobiSymbol -> Bool
    $c>= :: JacobiSymbol -> JacobiSymbol -> Bool
    >= :: JacobiSymbol -> JacobiSymbol -> Bool
    $cmax :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol
    max :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol
    $cmin :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol
    min :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol
    Ord, Int -> JacobiSymbol -> ShowS
    [JacobiSymbol] -> ShowS
    JacobiSymbol -> String
    (Int -> JacobiSymbol -> ShowS)
    -> (JacobiSymbol -> String)
    -> ([JacobiSymbol] -> ShowS)
    -> Show JacobiSymbol
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> JacobiSymbol -> ShowS
    showsPrec :: Int -> JacobiSymbol -> ShowS
    $cshow :: JacobiSymbol -> String
    show :: JacobiSymbol -> String
    $cshowList :: [JacobiSymbol] -> ShowS
    showList :: [JacobiSymbol] -> ShowS
    Show)

    instance Semigroup JacobiSymbol where
      <> :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol
    (<>) = \case
        JacobiSymbol
    MinusOne -> JacobiSymbol -> JacobiSymbol
    negJS
        JacobiSymbol
    Zero     -> JacobiSymbol -> JacobiSymbol -> JacobiSymbol
    forall a b. a -> b -> a
    const JacobiSymbol
    Zero
        JacobiSymbol
    One      -> JacobiSymbol -> JacobiSymbol
    forall a. a -> a
    id

    negJS :: JacobiSymbol -> JacobiSymbol
    negJS :: JacobiSymbol -> JacobiSymbol
    negJS = \case
      JacobiSymbol
    MinusOne -> JacobiSymbol
    One
      JacobiSymbol
    Zero     -> JacobiSymbol
    Zero
      JacobiSymbol
    One      -> JacobiSymbol
    MinusOne

    -- | Convenience function to convert out of a Jacobi symbol
    symbolToNum :: Num a => JacobiSymbol -> a
    symbolToNum :: forall a. Num a => JacobiSymbol -> a
    symbolToNum = \case
      JacobiSymbol
    Zero -> a
    0
      JacobiSymbol
    One -> a
    1
      JacobiSymbol
    MinusOne -> -a
    1

    {-# SPECIALISE symbolToNum :: JacobiSymbol -> Integer #-}
    {-# SPECIALISE symbolToNum :: JacobiSymbol -> Int #-}
    {-# SPECIALISE symbolToNum :: JacobiSymbol -> Word #-}
    {-# SPECIALISE symbolToNum :: JacobiSymbol -> Natural #-}

    -- | <https://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol> of two arguments.
    -- The lower argument (\"denominator\") must be odd and positive,
    -- this condition is checked.
    --
    -- If arguments have a common factor, the result
    -- is 'Zero', otherwise it is 'MinusOne' or 'One'.
    --
    -- >>> jacobi 1001 9911 -- arguments have a common factor 11
    -- Zero
    -- >>> jacobi 1001 9907
    -- MinusOne
    jacobi :: (Integral a, Bits a) => a -> a -> JacobiSymbol
    jacobi :: forall a. (Integral a, Bits a) => a -> a -> JacobiSymbol
    jacobi a
    _ a
    1 = JacobiSymbol
    One
    jacobi a
    a a
    b
      | a
    b a -> a -> Bool
    forall a. Ord a => a -> a -> Bool
    < a
    0     = String -> JacobiSymbol
    forall a. HasCallStack => String -> a
    error String
    "Math.NumberTheory.Moduli.jacobi: negative denominator"
      | a -> Bool
    forall a. Bits a => a -> Bool
    evenI a
    b   = String -> JacobiSymbol
    forall a. HasCallStack => String -> a
    error String
    "Math.NumberTheory.Moduli.jacobi: even denominator"
      | Bool
    otherwise = a -> a -> JacobiSymbol
    forall a. (Integral a, Bits a) => a -> a -> JacobiSymbol
    jacobi' a
    a a
    b   -- b odd, > 1

    {-# SPECIALISE jacobi :: Integer -> Integer -> JacobiSymbol #-}
    {-# SPECIALISE jacobi :: Natural -> Natural -> JacobiSymbol #-}
    {-# SPECIALISE jacobi :: Int -> Int -> JacobiSymbol #-}
    {-# SPECIALISE jacobi :: Word -> Word -> JacobiSymbol #-}

    jacobi' :: (Integral a, Bits a) => a -> a -> JacobiSymbol
    jacobi' :: forall a. (Integral a, Bits a) => a -> a -> JacobiSymbol
    jacobi' a
    0 a
    _ = JacobiSymbol
    Zero
    jacobi' a
    1 a
    _ = JacobiSymbol
    One
    jacobi' a
    a a
    b
      | a
    a a -> a -> Bool
    forall a. Ord a => a -> a -> Bool
    < a
    0     = let n :: JacobiSymbol
    n = if a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    b then JacobiSymbol
    MinusOne else JacobiSymbol
    One
                        (Word
    z, a
    o) = a -> (Word, a)
    forall a. Integral a => a -> (Word, a)
    shiftToOddCount (a -> a
    forall a. Num a => a -> a
    negate a
    a)
                        s :: JacobiSymbol
    s = if Word -> Bool
    forall a. Bits a => a -> Bool
    evenI Word
    z Bool -> Bool -> Bool
    || a -> Bool
    forall a. Bits a => a -> Bool
    rem8is1or7 a
    b then JacobiSymbol
    n else JacobiSymbol -> JacobiSymbol
    negJS JacobiSymbol
    n
                    in JacobiSymbol
    s JacobiSymbol -> JacobiSymbol -> JacobiSymbol
    forall a. Semigroup a => a -> a -> a
    <> a -> a -> JacobiSymbol
    forall a. (Integral a, Bits a) => a -> a -> JacobiSymbol
    jacobi' a
    o a
    b
      | a
    a a -> a -> Bool
    forall a. Ord a => a -> a -> Bool
    >= a
    b    = case a
    a a -> a -> a
    forall a. Integral a => a -> a -> a
    `rem` a
    b of
                      a
    0 -> JacobiSymbol
    Zero
                      a
    r -> JacobiSymbol -> a -> a -> JacobiSymbol
    forall a.
    (Integral a, Bits a) =>
    JacobiSymbol -> a -> a -> JacobiSymbol
    jacPS JacobiSymbol
    One a
    r a
    b
      | a -> Bool
    forall a. Bits a => a -> Bool
    evenI a
    a   = case a -> (Word, a)
    forall a. Integral a => a -> (Word, a)
    shiftToOddCount a
    a of
                      (Word
    z, a
    o) -> let r :: JacobiSymbol
    r = if a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    o Bool -> Bool -> Bool
    && a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    b then JacobiSymbol
    MinusOne else JacobiSymbol
    One
                                    s :: JacobiSymbol
    s = if Word -> Bool
    forall a. Bits a => a -> Bool
    evenI Word
    z Bool -> Bool -> Bool
    || a -> Bool
    forall a. Bits a => a -> Bool
    rem8is1or7 a
    b then JacobiSymbol
    r else JacobiSymbol -> JacobiSymbol
    negJS JacobiSymbol
    r
                                in JacobiSymbol -> a -> a -> JacobiSymbol
    forall a.
    (Integral a, Bits a) =>
    JacobiSymbol -> a -> a -> JacobiSymbol
    jacOL JacobiSymbol
    s a
    b a
    o
      | Bool
    otherwise = JacobiSymbol -> a -> a -> JacobiSymbol
    forall a.
    (Integral a, Bits a) =>
    JacobiSymbol -> a -> a -> JacobiSymbol
    jacOL (if a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    a Bool -> Bool -> Bool
    && a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    b then JacobiSymbol
    MinusOne else JacobiSymbol
    One) a
    b a
    a

    -- numerator positive and smaller than denominator
    jacPS :: (Integral a, Bits a) => JacobiSymbol -> a -> a -> JacobiSymbol
    jacPS :: forall a.
    (Integral a, Bits a) =>
    JacobiSymbol -> a -> a -> JacobiSymbol
    jacPS !JacobiSymbol
    acc a
    a a
    b
      | a -> Bool
    forall a. Bits a => a -> Bool
    evenI a
    a = case a -> (Word, a)
    forall a. Integral a => a -> (Word, a)
    shiftToOddCount a
    a of
        (Word
    z, a
    o)
          | Word -> Bool
    forall a. Bits a => a -> Bool
    evenI Word
    z Bool -> Bool -> Bool
    || a -> Bool
    forall a. Bits a => a -> Bool
    rem8is1or7 a
    b -> JacobiSymbol -> a -> a -> JacobiSymbol
    forall a.
    (Integral a, Bits a) =>
    JacobiSymbol -> a -> a -> JacobiSymbol
    jacOL (if a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    o Bool -> Bool -> Bool
    && a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    b then JacobiSymbol -> JacobiSymbol
    negJS JacobiSymbol
    acc else JacobiSymbol
    acc) a
    b a
    o
          | Bool
    otherwise               -> JacobiSymbol -> a -> a -> JacobiSymbol
    forall a.
    (Integral a, Bits a) =>
    JacobiSymbol -> a -> a -> JacobiSymbol
    jacOL (if a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    o Bool -> Bool -> Bool
    && a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    b then JacobiSymbol
    acc else JacobiSymbol -> JacobiSymbol
    negJS JacobiSymbol
    acc) a
    b a
    o
      | Bool
    otherwise = JacobiSymbol -> a -> a -> JacobiSymbol
    forall a.
    (Integral a, Bits a) =>
    JacobiSymbol -> a -> a -> JacobiSymbol
    jacOL (if a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    a Bool -> Bool -> Bool
    && a -> Bool
    forall a. Bits a => a -> Bool
    rem4is3 a
    b then JacobiSymbol -> JacobiSymbol
    negJS JacobiSymbol
    acc else JacobiSymbol
    acc) a
    b a
    a

    -- numerator odd, positive and larger than denominator
    jacOL :: (Integral a, Bits a) => JacobiSymbol -> a -> a -> JacobiSymbol
    jacOL :: forall a.
    (Integral a, Bits a) =>
    JacobiSymbol -> a -> a -> JacobiSymbol
    jacOL !JacobiSymbol
    acc a
    _ a
    1 = JacobiSymbol
    acc
    jacOL !JacobiSymbol
    acc a
    a a
    b = case a
    a a -> a -> a
    forall a. Integral a => a -> a -> a
    `rem` a
    b of
      a
    0 -> JacobiSymbol
    Zero
      a
    r -> JacobiSymbol -> a -> a -> JacobiSymbol
    forall a.
    (Integral a, Bits a) =>
    JacobiSymbol -> a -> a -> JacobiSymbol
    jacPS JacobiSymbol
    acc a
    r a
    b

    -- Utilities

    -- Sadly, GHC do not optimise `Prelude.even` to a bit test automatically.
    evenI :: Bits a => a -> Bool
    evenI :: forall a. Bits a => a -> Bool
    evenI a
    n = Bool -> Bool
    not (a
    n a -> Int -> Bool
    forall a. Bits a => a -> Int -> Bool
    `testBit` Int
    0)

    -- For an odd input @n@ test whether n `rem` 4 == 1
    rem4is3 :: Bits a => a -> Bool
    rem4is3 :: forall a. Bits a => a -> Bool
    rem4is3 a
    n = a
    n a -> Int -> Bool
    forall a. Bits a => a -> Int -> Bool
    `testBit` Int
    1

    -- For an odd input @n@ test whether (n `rem` 8) `elem` [1, 7]
    rem8is1or7 :: Bits a => a -> Bool
    rem8is1or7 :: forall a. Bits a => a -> Bool
    rem8is1or7 a
    n = a
    n a -> Int -> Bool
    forall a. Bits a => a -> Int -> Bool
    `testBit` Int
    1 Bool -> Bool -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    n a -> Int -> Bool
    forall a. Bits a => a -> Int -> Bool
    `testBit` Int
    2