{-
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 .
-}
{- |
[@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 .
* .
* .
-}
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