module Factory.Math.MultiplicativeOrder(
multiplicativeOrder
) where
import qualified Control.DeepSeq
import qualified Factory.Data.Exponential as Data.Exponential
import qualified Factory.Math.Power as Math.Power
import qualified Factory.Math.Primality as Math.Primality
import qualified Factory.Math.PrimeFactorisation as Math.PrimeFactorisation
multiplicativeOrder :: (Math.PrimeFactorisation.Algorithmic primeFactorisationAlgorithm, Control.DeepSeq.NFData i, Integral i, Show i)
=> primeFactorisationAlgorithm
-> i
-> i
-> i
multiplicativeOrder :: primeFactorisationAlgorithm -> i -> i -> i
multiplicativeOrder primeFactorisationAlgorithm
primeFactorisationAlgorithm i
base i
modulus
| i
modulus i -> i -> Bool
forall a. Ord a => a -> a -> Bool
< i
2 = [Char] -> i
forall a. HasCallStack => [Char] -> a
error ([Char] -> i) -> [Char] -> i
forall a b. (a -> b) -> a -> b
$ [Char]
"Factory.Math.MultiplicativeOrder.multiplicativeOrder:\tinvalid modulus; " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ i -> [Char]
forall a. Show a => a -> [Char]
show i
modulus
| Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ i -> i -> Bool
forall i. Integral i => i -> i -> Bool
Math.Primality.areCoprime i
base i
modulus = [Char] -> i
forall a. HasCallStack => [Char] -> a
error ([Char] -> i) -> [Char] -> i
forall a b. (a -> b) -> a -> b
$ [Char]
"Factory.Math.MultiplicativeOrder.multiplicativeOrder:\targuments aren't coprime; " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ (i, i) -> [Char]
forall a. Show a => a -> [Char]
show (i
base, i
modulus)
| Bool
otherwise = ((i, Int) -> i -> i) -> i -> [(i, Int)] -> i
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (i -> i -> i
forall a. Integral a => a -> a -> a
lcm (i -> i -> i) -> ((i, Int) -> i) -> (i, Int) -> i -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i, Int) -> i
forall exponent. Integral exponent => (i, exponent) -> i
multiplicativeOrder') i
1 ([(i, Int)] -> i) -> [(i, Int)] -> i
forall a b. (a -> b) -> a -> b
$ primeFactorisationAlgorithm -> i -> [(i, Int)]
forall algorithm base.
(Algorithmic algorithm, NFData base, Integral base) =>
algorithm -> base -> Factors base Int
Math.PrimeFactorisation.primeFactors primeFactorisationAlgorithm
primeFactorisationAlgorithm i
modulus
where
multiplicativeOrder' :: (i, exponent) -> i
multiplicativeOrder' (i, exponent)
e = [i] -> i
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product ([i] -> i) -> ([(i, Int)] -> [i]) -> [(i, Int)] -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((i, Int) -> i) -> [(i, Int)] -> [i]
forall a b. (a -> b) -> [a] -> [b]
map (
\(i, Int)
e' -> let
d :: Int
d :: Int
d = [i] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([i] -> Int) -> (i -> [i]) -> i -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i -> Bool) -> [i] -> [i]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (i -> i -> Bool
forall a. Eq a => a -> a -> Bool
/= i
1) ([i] -> [i]) -> (i -> [i]) -> i -> [i]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i -> i) -> i -> [i]
forall a. (a -> a) -> a -> [a]
iterate (
\i
y -> i -> i -> i -> i
forall i power.
(Integral i, Integral power, Show power) =>
i -> power -> i -> i
Math.Power.raiseModulo i
y ((i, Int) -> i
forall base exponent. Exponential base exponent -> base
Data.Exponential.getBase (i, Int)
e') i
pk
) (i -> Int) -> i -> Int
forall a b. (a -> b) -> a -> b
$ i -> i -> i -> i
forall i power.
(Integral i, Integral power, Show power) =>
i -> power -> i -> i
Math.Power.raiseModulo i
base (i
totient i -> i -> i
forall a. Integral a => a -> a -> a
`div` (i, Int) -> i
forall base exponent.
(Num base, Integral exponent) =>
Exponential base exponent -> base
Data.Exponential.evaluate (i, Int)
e') i
pk
in (i, Int) -> i
forall base exponent. Exponential base exponent -> base
Data.Exponential.getBase (i, Int)
e' i -> Int -> i
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
d
) ([(i, Int)] -> i) -> [(i, Int)] -> i
forall a b. (a -> b) -> a -> b
$ primeFactorisationAlgorithm -> i -> [(i, Int)]
forall algorithm base.
(Algorithmic algorithm, NFData base, Integral base) =>
algorithm -> base -> Factors base Int
Math.PrimeFactorisation.primeFactors primeFactorisationAlgorithm
primeFactorisationAlgorithm i
totient where
pk :: i
pk = (i, exponent) -> i
forall base exponent.
(Num base, Integral exponent) =>
Exponential base exponent -> base
Data.Exponential.evaluate (i, exponent)
e
totient :: i
totient = (i, exponent) -> i
forall base exponent.
(Integral base, Integral exponent) =>
Exponential base exponent -> base
Math.PrimeFactorisation.primePowerTotient (i, exponent)
e