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.

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

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)]}}

Calculate the size of a given cyclic group.

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

Extract primitive root value.

Get cyclic group structure.

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' 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