Math.NumberTheory.Moduli.PrimitiveRoot

Primitive roots and cyclic groups.

Cyclic groups

data CyclicGroup a

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 a => Eq (CyclicGroup a)

Defined in Math.NumberTheory.Moduli.PrimitiveRoot

Methods

(==) :: CyclicGroup a -> CyclicGroup a -> Bool

(/=) :: CyclicGroup a -> CyclicGroup a -> Bool

Show a => Show (CyclicGroup a)

Defined in Math.NumberTheory.Moduli.PrimitiveRoot

Methods

showsPrec :: Int -> CyclicGroup a -> ShowS

show :: CyclicGroup a -> String

showList :: [CyclicGroup a] -> ShowS

Generic (CyclicGroup a)

Defined in Math.NumberTheory.Moduli.PrimitiveRoot

Associated Types

type Rep (CyclicGroup a) :: Type -> Type

Methods

from :: CyclicGroup a -> Rep (CyclicGroup a) x

to :: Rep (CyclicGroup a) x -> CyclicGroup a

NFData a => NFData (CyclicGroup a)

Defined in Math.NumberTheory.Moduli.PrimitiveRoot

Methods

rnf :: CyclicGroup a -> ()

type Rep (CyclicGroup a)

Defined in Math.NumberTheory.Moduli.PrimitiveRoot

type Rep (CyclicGroup a) = D1 (MetaData "CyclicGroup" "Math.NumberTheory.Moduli.PrimitiveRoot" "arithmoi-0.9.0.0-E3bSyM9N8uIFxgJyxrBJhq" False) ((C1 (MetaCons "CG2" PrefixI False) (U1 :: Type -> Type) :+: C1 (MetaCons "CG4" PrefixI False) (U1 :: Type -> Type)) :+: (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)

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 (Prime 13) 3)
>>> cyclicGroupFromModulo (4 * 13)
Nothing

cyclicGroupToModulo :: Euclidean a => CyclicGroup a -> Prefactored a

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

>>> cyclicGroupToModulo CG4
Prefactored {prefValue = 4, prefFactors = Coprimes {unCoprimes = [(2,2)]}}

>>> import Data.Maybe
>>> cyclicGroupToModulo (CGDoubleOddPrimePower (fromJust (isPrime 13)) 3)
Prefactored {prefValue = 4394, prefFactors = Coprimes {unCoprimes = [(13,3),(2,1)]}}

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

Calculate the size of a given cyclic group.

Primitive roots

data PrimitiveRoot m

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

Instances

Eq (PrimitiveRoot m)

Defined in Math.NumberTheory.Moduli.PrimitiveRoot

Methods

(==) :: PrimitiveRoot m -> PrimitiveRoot m -> Bool

(/=) :: PrimitiveRoot m -> PrimitiveRoot m -> Bool

KnownNat m => Show (PrimitiveRoot m)

Defined in Math.NumberTheory.Moduli.PrimitiveRoot

Methods

showsPrec :: Int -> PrimitiveRoot m -> ShowS

show :: PrimitiveRoot m -> String

showList :: [PrimitiveRoot m] -> ShowS

unPrimitiveRoot :: PrimitiveRoot m -> MultMod m

Extract primitive root value.

getGroup :: PrimitiveRoot m -> CyclicGroup Natural

Get cyclic group structure.

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

Check whether a given modular residue is a primitive root.

>>> :set -XDataKinds
>>> isPrimitiveRoot (1 :: Mod 13)
Nothing
>>> isPrimitiveRoot (2 :: Mod 13)
Just (PrimitiveRoot {unPrimitiveRoot = MultMod {multElement = (2 `modulo` 13)}, getGroup = CGOddPrimePower (Prime 13) 1})

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

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