{-
	Copyright (C) 2011 Dr. Alistair Ward

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]	Exports the /Multiplicative Order/ of an integer, in a specific /modular/ arithmetic.

-}

module Factory.Math.MultiplicativeOrder(
-- * Functions
	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

{- |
	* The smallest positive integral power to which the specified integral base must be raised,
	to be congruent with one, in the specified /modular/ arithmetic.

	* Based on <https://rosettacode.org/wiki/Multiplicative_order#Haskell>.

	* <https://en.wikipedia.org/wiki/Multiplicative_order>.

	* <https://mathworld.wolfram.com/MultiplicativeOrder.html>.
-}
multiplicativeOrder :: (Math.PrimeFactorisation.Algorithmic primeFactorisationAlgorithm, Control.DeepSeq.NFData i, Integral i, Show i)
	=> primeFactorisationAlgorithm
	-> i	-- ^ Base.
	-> i	-- ^ Modulus.
	-> i	-- ^ Result.
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	-- Combine the /multiplicative order/ of the constituent /prime-factors/.
	where
--		multiplicativeOrder' :: (Control.DeepSeq.NFData i, Integral i) => Data.Exponential.Exponential i -> i
		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