Math.NumberTheory.Moduli.PrimitiveRoot

Primitive roots and cyclic groups.

Documentation

isPrimitiveRoot :: KnownNat n => Mod n -> Bool

Check whether a given modular residue is a primitive root.

> isPrimitiveRoot (1 :: Mod 13)
False
> isPrimitiveRoot (2 :: Mod 13)
True

Here is how to list all primitive roots:

> filter 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.

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

Show (Prime a) => Show (CyclicGroup a)

Methods

showsPrec :: Int -> CyclicGroup a -> ShowS

show :: CyclicGroup a -> String

showList :: [CyclicGroup a] -> ShowS

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

cyclicGroupToModulo :: (Integral a, UniqueFactorisation a) => CyclicGroup a -> Prefactored a

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

> cyclicGroupToModulo CG4
Prefactored {prefValue = 4, prefFactors = [(2, 2)]}
> cyclicGroupToModulo (CGDoubleOddPrimePower (PrimeNat 13) 3)
Prefactored {prefValue = 4394, prefFactors = [(2, 1), (13, 3)]}

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