arithmoi-0.8.0.0: Efficient basic number-theoretic functions.

Copyright (c) 2017 Andrew Lelechenko MIT Andrew Lelechenko Provisional Non-portable (GHC extensions) None Haskell2010

Math.NumberTheory.Moduli.PrimitiveRoot

Contents

Description

Primitive roots and cyclic groups.

Synopsis

Cyclic groups

data CyclicGroup a Source #

A multiplicative group of residues is called cyclic, if there is a primitive root g, whose powers generates all elements. Any cyclic multiplicative group of residues falls into one of the following cases.

Constructors

 CG2 Residues modulo 2. CG4 Residues modulo 4. CGOddPrimePower (Prime a) Word Residues modulo p^k for odd prime p. CGDoubleOddPrimePower (Prime a) Word Residues modulo 2p^k for odd prime p.
Instances
 Eq (Prime a) => Eq (CyclicGroup a) Source # Instance detailsDefined in Math.NumberTheory.Moduli.PrimitiveRoot Methods(==) :: CyclicGroup a -> CyclicGroup a -> Bool #(/=) :: CyclicGroup a -> CyclicGroup a -> Bool # Show (Prime a) => Show (CyclicGroup a) Source # Instance detailsDefined in Math.NumberTheory.Moduli.PrimitiveRoot MethodsshowsPrec :: Int -> CyclicGroup a -> ShowS #show :: CyclicGroup a -> String #showList :: [CyclicGroup a] -> ShowS # Source # Instance detailsDefined in Math.NumberTheory.Moduli.PrimitiveRoot Associated Typestype Rep (CyclicGroup a) :: * -> * # Methodsfrom :: CyclicGroup a -> Rep (CyclicGroup a) x #to :: Rep (CyclicGroup a) x -> CyclicGroup a # NFData (Prime a) => NFData (CyclicGroup a) Source # Instance detailsDefined in Math.NumberTheory.Moduli.PrimitiveRoot Methodsrnf :: CyclicGroup a -> () # type Rep (CyclicGroup a) Source # Instance detailsDefined in Math.NumberTheory.Moduli.PrimitiveRoot type Rep (CyclicGroup a) = D1 (MetaData "CyclicGroup" "Math.NumberTheory.Moduli.PrimitiveRoot" "arithmoi-0.8.0.0-6Rtnbx2jJER74A6C7rjrHd" False) ((C1 (MetaCons "CG2" PrefixI False) (U1 :: * -> *) :+: C1 (MetaCons "CG4" PrefixI False) (U1 :: * -> *)) :+: (C1 (MetaCons "CGOddPrimePower" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Prime a)) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word)) :+: C1 (MetaCons "CGDoubleOddPrimePower" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Prime a)) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word))))

cyclicGroupFromModulo :: (Ord a, Integral a, UniqueFactorisation a) => a -> Maybe (CyclicGroup a) Source #

Check whether a multiplicative group of residues, characterized by its modulo, is cyclic and, if yes, return its form.

>>> cyclicGroupFromModulo 4
Just CG4
>>> cyclicGroupFromModulo (2 * 13 ^ 3)
Just (CGDoubleOddPrimePower (PrimeNat 13) 3)
>>> cyclicGroupFromModulo (4 * 13)
Nothing

Extract modulo and its factorisation from a cyclic multiplicative group of residues.

>>> cyclicGroupToModulo CG4
Prefactored {prefValue = 4, prefFactors = Coprimes {unCoprimes = fromList [(2,2)]}}
>>> :set -XTypeFamilies
>>> cyclicGroupToModulo (CGDoubleOddPrimePower (PrimeNat 13) 3)
Prefactored {prefValue = 4394, prefFactors = Coprimes {unCoprimes = fromList [(2,1),(13,3)]}}

groupSize :: (Euclidean a, Ord a, UniqueFactorisation a) => CyclicGroup a -> Prefactored a Source #

Calculate the size of a given cyclic group.

Primitive roots

data PrimitiveRoot m Source #

'PrimitiveRoot m' is a type which is only inhabited by primitive roots of n.

Instances
 Source # Instance detailsDefined in Math.NumberTheory.Moduli.PrimitiveRoot Methods(==) :: PrimitiveRoot m -> PrimitiveRoot m -> Bool #(/=) :: PrimitiveRoot m -> PrimitiveRoot m -> Bool # KnownNat m => Show (PrimitiveRoot m) Source # Instance detailsDefined in Math.NumberTheory.Moduli.PrimitiveRoot MethodsshowsPrec :: Int -> PrimitiveRoot m -> ShowS #show :: PrimitiveRoot m -> String #showList :: [PrimitiveRoot m] -> ShowS #

Extract primitive root value.

Get cyclic group structure.

isPrimitiveRoot :: KnownNat n => Mod n -> Maybe (PrimitiveRoot n) Source #

Check whether a given modular residue is a primitive root.

>>> :set -XDataKinds
>>> isPrimitiveRoot (1 :: Mod 13)
False
>>> isPrimitiveRoot (2 :: Mod 13)
True

Here is how to list all primitive roots:

>>> mapMaybe isPrimitiveRoot [minBound .. maxBound] :: [Mod 13]
[(2 modulo 13), (6 modulo 13), (7 modulo 13), (11 modulo 13)]

This function is a convenient wrapper around isPrimitiveRoot'. The latter provides better control and performance, if you need them.

isPrimitiveRoot' :: (Integral a, UniqueFactorisation a) => CyclicGroup a -> a -> Bool Source #

isPrimitiveRoot' cg a checks whether a is a primitive root of a given cyclic multiplicative group of residues cg.

>>> let Just cg = cyclicGroupFromModulo 13
>>> isPrimitiveRoot' cg 1
False
>>> isPrimitiveRoot' cg 2
True