arithmoi-0.13.0.0: Efficient basic number-theoretic functions.

Copyright | (c) 2017 Andrew Lelechenko
License | MIT
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | Safe-Inferred
Language | Haskell2010

Math.NumberTheory.Moduli.Multiplicative

Contents

- Multiplicative group
- Primitive roots

Description

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

data MultMod m Source #

This type represents elements of the multiplicative group mod m, i.e. those elements which are coprime to m. Use `isMultElement` to construct.

#### Instances

Instances details

KnownNat m => Monoid (MultMod m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Multiplicative Methods mempty :: MultMod m Source # mappend :: MultMod m -> MultMod m -> MultMod m Source # mconcat :: [MultMod m] -> MultMod m Source #
KnownNat m => Semigroup (MultMod m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Multiplicative Methods (<>) :: MultMod m -> MultMod m -> MultMod m Source # sconcat :: NonEmpty (MultMod m) -> MultMod m Source # stimes :: Integral b => b -> MultMod m -> MultMod m Source #
KnownNat m => Bounded (MultMod m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Multiplicative Methods minBound :: MultMod m Source # maxBound :: MultMod m Source #
Show (MultMod m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Multiplicative Methods showsPrec :: Int -> MultMod m -> ShowS Source # show :: MultMod m -> String Source # showList :: [MultMod m] -> ShowS Source #
Eq (MultMod m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Multiplicative Methods (==) :: MultMod m -> MultMod m -> Bool Source # (/=) :: MultMod m -> MultMod m -> Bool Source #
Ord (MultMod m) Source # |

Instance details

Defined in Math.NumberTheory.Moduli.Multiplicative

Methods

compare :: MultMod m -> MultMod m -> Ordering Source #

(<) :: MultMod m -> MultMod m -> Bool Source #

(<=) :: MultMod m -> MultMod m -> Bool Source #

(>) :: MultMod m -> MultMod m -> Bool Source #

(>=) :: MultMod m -> MultMod m -> Bool Source #

max :: MultMod m -> MultMod m -> MultMod m Source #

min :: MultMod m -> MultMod m -> MultMod m Source #

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

Instances details

Show (PrimitiveRoot m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Multiplicative Methods showsPrec :: Int -> PrimitiveRoot m -> ShowS Source # show :: PrimitiveRoot m -> String Source # showList :: [PrimitiveRoot m] -> ShowS Source #
Eq (PrimitiveRoot m) Source # |
Instance details Defined in Math.NumberTheory.Moduli.Multiplicative Methods (==) :: PrimitiveRoot m -> PrimitiveRoot m -> Bool Source # (/=) :: PrimitiveRoot m -> PrimitiveRoot m -> Bool Source #

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