{-
	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 base modulus
        | modulus < 2                                   = error $ "Factory.Math.MultiplicativeOrder.multiplicativeOrder:\tinvalid modulus; " ++ show modulus
        | not $ Math.Primality.areCoprime base modulus  = error $ "Factory.Math.MultiplicativeOrder.multiplicativeOrder:\targuments aren't coprime; " ++ show (base, modulus)
        | otherwise                                     = foldr (lcm . multiplicativeOrder') 1 $ Math.PrimeFactorisation.primeFactors primeFactorisationAlgorithm modulus       -- Combine the /multiplicative order/ of the constituent /prime-factors/.
        where
--		multiplicativeOrder' :: (Control.DeepSeq.NFData i, Integral i) => Data.Exponential.Exponential i -> i
                multiplicativeOrder' e  = product . map (
                        \e'     -> let
                                d :: Int
                                d       = length . takeWhile (/= 1) . iterate (
                                        \y      -> Math.Power.raiseModulo y (Data.Exponential.getBase e') pk
                                 ) $ Math.Power.raiseModulo base (totient `div` Data.Exponential.evaluate e') pk
                        in Data.Exponential.getBase e' ^ d
                 ) $ Math.PrimeFactorisation.primeFactors primeFactorisationAlgorithm totient   where
                        pk      = Data.Exponential.evaluate e
                        totient = Math.PrimeFactorisation.primePowerTotient e