Copyright | (c) 2017 Andrew Lelechenko |
---|---|
License | MIT |
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
Safe Haskell | None |
Language | Haskell2010 |
Multiplicative groups of integers modulo m.
Synopsis
- data MultMod m
- multElement :: MultMod m -> Mod m
- isMultElement :: KnownNat m => Mod m -> Maybe (MultMod m)
- invertGroup :: KnownNat m => MultMod m -> MultMod m
- data PrimitiveRoot m
- unPrimitiveRoot :: PrimitiveRoot m -> MultMod m
- isPrimitiveRoot :: (Integral a, UniqueFactorisation a) => CyclicGroup a m -> Mod m -> Maybe (PrimitiveRoot m)
- discreteLogarithm :: CyclicGroup Integer m -> PrimitiveRoot m -> MultMod m -> Natural
Multiplicative group
This type represents elements of the multiplicative group mod m, i.e.
those elements which are coprime to m. Use toMultElement
to construct.
multElement :: MultMod m -> Mod m Source #
Unwrap a residue.
isMultElement :: KnownNat m => Mod m -> Maybe (MultMod m) Source #
Attempt to construct a multiplicative group element.
invertGroup :: KnownNat m => MultMod m -> MultMod m Source #
For elements of the multiplicative group, we can safely perform the inverse without needing to worry about failure.
Primitive roots
data PrimitiveRoot m Source #
PrimitiveRoot
m is a type which is only inhabited
by primitive roots of m.
Instances
Eq (PrimitiveRoot m) Source # | |
Defined in Math.NumberTheory.Moduli.Multiplicative (==) :: PrimitiveRoot m -> PrimitiveRoot m -> Bool # (/=) :: PrimitiveRoot m -> PrimitiveRoot m -> Bool # | |
KnownNat m => Show (PrimitiveRoot m) Source # | |
Defined in Math.NumberTheory.Moduli.Multiplicative showsPrec :: Int -> PrimitiveRoot m -> ShowS # show :: PrimitiveRoot m -> String # showList :: [PrimitiveRoot m] -> ShowS # |
unPrimitiveRoot :: PrimitiveRoot m -> MultMod m Source #
Extract primitive root value.
isPrimitiveRoot :: (Integral a, UniqueFactorisation a) => CyclicGroup a m -> Mod m -> Maybe (PrimitiveRoot m) Source #
Check whether a given modular residue is a primitive root.
>>>
:set -XDataKinds
>>>
import Data.Maybe
>>>
isPrimitiveRoot (fromJust cyclicGroup) (1 :: Mod 13)
Nothing>>>
isPrimitiveRoot (fromJust cyclicGroup) (2 :: Mod 13)
Just (PrimitiveRoot {unPrimitiveRoot = MultMod {multElement = (2 `modulo` 13)}})
discreteLogarithm :: CyclicGroup Integer m -> PrimitiveRoot m -> MultMod m -> Natural Source #
Computes the discrete logarithm. Currently uses a combination of the baby-step giant-step method and Pollard's rho algorithm, with Bach reduction.
>>>
:set -XDataKinds
>>>
import Data.Maybe
>>>
let cg = fromJust cyclicGroup :: CyclicGroup Integer 13
>>>
let rt = fromJust (isPrimitiveRoot cg 2)
>>>
let x = fromJust (isMultElement 11)
>>>
discreteLogarithm cg rt x
7