-- |
-- 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 CPP          #-}
{-# LANGUAGE LambdaCase   #-}

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

import Data.Bits
#if __GLASGOW_HASKELL__ < 803
import Data.Semigroup
#endif
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
/= :: JacobiSymbol -> JacobiSymbol -> Bool
$c/= :: JacobiSymbol -> JacobiSymbol -> Bool
== :: JacobiSymbol -> JacobiSymbol -> Bool
$c== :: 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
min :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol
$cmin :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol
max :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol
$cmax :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol
>= :: JacobiSymbol -> JacobiSymbol -> Bool
$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
compare :: JacobiSymbol -> JacobiSymbol -> Ordering
$ccompare :: JacobiSymbol -> JacobiSymbol -> Ordering
$cp1Ord :: Eq 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
showList :: [JacobiSymbol] -> ShowS
$cshowList :: [JacobiSymbol] -> ShowS
show :: JacobiSymbol -> String
$cshow :: JacobiSymbol -> String
showsPrec :: Int -> JacobiSymbol -> ShowS
$cshowsPrec :: Int -> 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

{-# SPECIALISE symbolToNum :: JacobiSymbol -> Integer,
                              JacobiSymbol -> Int,
                              JacobiSymbol -> Word,
                              JacobiSymbol -> Natural
  #-}
-- | Convenience function to convert out of a Jacobi symbol
symbolToNum :: Num a => JacobiSymbol -> a
symbolToNum :: JacobiSymbol -> a
symbolToNum = \case
  JacobiSymbol
Zero -> a
0
  JacobiSymbol
One -> a
1
  JacobiSymbol
MinusOne -> -a
1

-- | <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
{-# SPECIALISE jacobi :: Integer -> Integer -> JacobiSymbol,
                         Natural -> Natural -> JacobiSymbol,
                         Int -> Int -> JacobiSymbol,
                         Word -> Word -> JacobiSymbol
  #-}
jacobi :: (Integral a, Bits a) => a -> a -> JacobiSymbol
jacobi :: 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

jacobi' :: (Integral a, Bits a) => a -> a -> JacobiSymbol
jacobi' :: 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 :: 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 :: 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 :: 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 :: 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 :: 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