```-- |
-- 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
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
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
Ord, Int -> JacobiSymbol -> ShowS
[JacobiSymbol] -> ShowS
JacobiSymbol -> String
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     -> forall a b. a -> b -> a
const JacobiSymbol
Zero
JacobiSymbol
One      -> 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 :: forall a. Num a => 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 :: forall a. (Integral a, Bits a) => a -> a -> JacobiSymbol
jacobi a
_ a
1 = JacobiSymbol
One
jacobi a
a a
b
| a
b forall a. Ord a => a -> a -> Bool
< a
0     = forall a. HasCallStack => String -> a
error String
"Math.NumberTheory.Moduli.jacobi: negative denominator"
| forall a. Bits a => a -> Bool
evenI a
b   = forall a. HasCallStack => String -> a
error String
"Math.NumberTheory.Moduli.jacobi: even denominator"
| Bool
otherwise = 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' :: 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 forall a. Ord a => a -> a -> Bool
< a
0     = let n :: JacobiSymbol
n = if forall a. Bits a => a -> Bool
rem4is3 a
b then JacobiSymbol
MinusOne else JacobiSymbol
One
(Word
z, a
o) = forall a. Integral a => a -> (Word, a)
shiftToOddCount (forall a. Num a => a -> a
negate a
a)
s :: JacobiSymbol
s = if forall a. Bits a => a -> Bool
evenI Word
z Bool -> Bool -> Bool
|| forall a. Bits a => a -> Bool
rem8is1or7 a
b then JacobiSymbol
n else JacobiSymbol -> JacobiSymbol
negJS JacobiSymbol
n
in JacobiSymbol
s forall a. Semigroup a => a -> a -> a
<> forall a. (Integral a, Bits a) => a -> a -> JacobiSymbol
jacobi' a
o a
b
| a
a forall a. Ord a => a -> a -> Bool
>= a
b    = case a
a forall a. Integral a => a -> a -> a
`rem` a
b of
a
0 -> JacobiSymbol
Zero
a
r -> forall a.
(Integral a, Bits a) =>
JacobiSymbol -> a -> a -> JacobiSymbol
jacPS JacobiSymbol
One a
r a
b
| forall a. Bits a => a -> Bool
evenI a
a   = case forall a. Integral a => a -> (Word, a)
shiftToOddCount a
a of
(Word
z, a
o) -> let r :: JacobiSymbol
r = if forall a. Bits a => a -> Bool
rem4is3 a
o Bool -> Bool -> Bool
&& forall a. Bits a => a -> Bool
rem4is3 a
b then JacobiSymbol
MinusOne else JacobiSymbol
One
s :: JacobiSymbol
s = if forall a. Bits a => a -> Bool
evenI Word
z Bool -> Bool -> Bool
|| forall a. Bits a => a -> Bool
rem8is1or7 a
b then JacobiSymbol
r else JacobiSymbol -> JacobiSymbol
negJS JacobiSymbol
r
in forall a.
(Integral a, Bits a) =>
JacobiSymbol -> a -> a -> JacobiSymbol
jacOL JacobiSymbol
s a
b a
o
| Bool
otherwise = forall a.
(Integral a, Bits a) =>
JacobiSymbol -> a -> a -> JacobiSymbol
jacOL (if forall a. Bits a => a -> Bool
rem4is3 a
a Bool -> Bool -> 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
| forall a. Bits a => a -> Bool
evenI a
a = case forall a. Integral a => a -> (Word, a)
shiftToOddCount a
a of
(Word
z, a
o)
| forall a. Bits a => a -> Bool
evenI Word
z Bool -> Bool -> Bool
|| forall a. Bits a => a -> Bool
rem8is1or7 a
b -> forall a.
(Integral a, Bits a) =>
JacobiSymbol -> a -> a -> JacobiSymbol
jacOL (if forall a. Bits a => a -> Bool
rem4is3 a
o Bool -> Bool -> 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               -> forall a.
(Integral a, Bits a) =>
JacobiSymbol -> a -> a -> JacobiSymbol
jacOL (if forall a. Bits a => a -> Bool
rem4is3 a
o Bool -> Bool -> 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 = forall a.
(Integral a, Bits a) =>
JacobiSymbol -> a -> a -> JacobiSymbol
jacOL (if forall a. Bits a => a -> Bool
rem4is3 a
a Bool -> Bool -> 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 forall a. Integral a => a -> a -> a
`rem` a
b of
a
0 -> JacobiSymbol
Zero
a
r -> 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 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 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 forall a. Bits a => a -> Int -> Bool
`testBit` Int
1 forall a. Eq a => a -> a -> Bool
== a
n forall a. Bits a => a -> Int -> Bool
`testBit` Int
2
```