| Copyright | (c) 2017 Andrew Lelechenko |
|---|---|
| License | MIT |
| Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
| Safe Haskell | None |
| Language | Haskell2010 |
Math.NumberTheory.Moduli.Class
Description
Safe modular arithmetic with modulo on type level.
Synopsis
- data Mod (m :: Nat)
- getVal :: Mod m -> Integer
- getNatVal :: Mod m -> Natural
- getMod :: KnownNat m => Mod m -> Integer
- getNatMod :: KnownNat m => Mod m -> Natural
- invertMod :: KnownNat m => Mod m -> Maybe (Mod m)
- powMod :: (KnownNat m, Integral a) => Mod m -> a -> Mod m
- (^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m
- data MultMod m
- multElement :: MultMod m -> Mod m
- isMultElement :: KnownNat m => Mod m -> Maybe (MultMod m)
- invertGroup :: KnownNat m => MultMod m -> MultMod m
- data SomeMod where
- modulo :: Integer -> Natural -> SomeMod
- invertSomeMod :: SomeMod -> Maybe SomeMod
- powSomeMod :: Integral a => SomeMod -> a -> SomeMod
- class KnownNat (n :: Nat)
Known modulo
This data type represents integers modulo m, equipped with useful instances.
For example, 3 :: Mod 10 stands for the class of integers
congruent to 3 modulo 10: …−17, −7, 3, 13, 23…
>>>:set -XDataKinds>>>3 + 8 :: Mod 10(1 `modulo` 10) -- because 3 + 8 = 11 ≡ 1 (mod 10)
Warning: division by residue, which is not
coprime
with the modulo, throws DivideByZero.
Consider using invertMod for non-prime moduli.
Instances
| KnownNat m => Bounded (Mod m) | |
| KnownNat m => Enum (Mod m) | |
| Eq (Mod m) | |
| KnownNat m => Fractional (Mod m) | See the warning about division above. |
| KnownNat m => Num (Mod m) | |
| Ord (Mod m) | |
| KnownNat m => Show (Mod m) | |
| Generic (Mod m) | |
| NFData (Mod m) | |
| KnownNat m => GcdDomain (Mod m) | See the warning about division above. |
| KnownNat m => Euclidean (Mod m) | See the warning about division above. |
| KnownNat m => Field (Mod m) | See the warning about division above. |
Defined in Data.Mod | |
| KnownNat m => Semiring (Mod m) | |
| KnownNat m => Ring (Mod m) | |
| type Rep (Mod m) | |
getVal :: Mod m -> Integer Source #
The canonical representative of the residue class, always between 0 and m-1 inclusively.
getNatVal :: Mod m -> Natural Source #
The canonical representative of the residue class, always between 0 and m-1 inclusively.
getMod :: KnownNat m => Mod m -> Integer Source #
Linking type and value levels: extract modulo m as a value.
getNatMod :: KnownNat m => Mod m -> Natural Source #
Linking type and value levels: extract modulo m as a value.
(^%) :: (KnownNat m, Integral a) => Mod m -> a -> Mod m infixr 8 #
Drop-in replacement for ^ with much better performance.
Negative powers are allowed, but may throw DivideByZero, if an argument
is not coprime with the modulo.
Building with -O triggers a rewrite rule ^ = ^%.
>>>:set -XDataKinds>>>3 ^% 4 :: Mod 10(1 `modulo` 10) -- because 3 ^ 4 = 81 ≡ 1 (mod 10)>>>3 ^% (-1) :: Mod 10(7 `modulo` 10) -- because 3 * 7 = 21 ≡ 1 (mod 10)>>>4 ^% (-1) :: Mod 10(*** Exception: divide by zero -- because 4 and 10 are not coprime
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.
Instances
| KnownNat m => Bounded (MultMod m) Source # | |
| Eq (MultMod m) Source # | |
| Ord (MultMod m) Source # | |
Defined in Math.NumberTheory.Moduli.Multiplicative | |
| KnownNat m => Show (MultMod m) Source # | |
| KnownNat m => Semigroup (MultMod m) Source # | |
| KnownNat m => Monoid (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.
Unknown modulo
This type represents residues with unknown modulo and rational numbers. One can freely combine them in arithmetic expressions, but each operation will spend time on modulo's recalculation:
>>>2 `modulo` 10 + 4 `modulo` 15(1 `modulo` 5)>>>(2 `modulo` 10) * (4 `modulo` 15)(3 `modulo` 5)>>>2 `modulo` 10 + fromRational (3 % 7)(1 `modulo` 10)>>>2 `modulo` 10 * fromRational (3 % 7)(8 `modulo` 10)
If performance is crucial, it is recommended to extract Mod m for further processing
by pattern matching. E. g.,
case modulo n m of
SomeMod k -> process k -- Here k has type Mod m
InfMod{} -> error "impossible"Instances
| Eq SomeMod Source # | |
| Fractional SomeMod Source # | Beware that division by residue, which is not coprime with the modulo,
will result in runtime error. Consider using |
| Num SomeMod Source # | |
| Ord SomeMod Source # | |
Defined in Math.NumberTheory.Moduli.SomeMod | |
| Show SomeMod Source # | |
| GcdDomain SomeMod Source # | See the warning about division above. |
| Euclidean SomeMod Source # | See the warning about division above. |
| Field SomeMod Source # | See the warning about division above. |
Defined in Math.NumberTheory.Moduli.SomeMod | |
| Semiring SomeMod Source # | |
| Ring SomeMod Source # | |
Defined in Math.NumberTheory.Moduli.SomeMod | |
modulo :: Integer -> Natural -> SomeMod infixl 7 Source #
Create modular value by representative of residue class and modulo.
One can use the result either directly (via functions from Num and Fractional),
or deconstruct it by pattern matching. Note that modulo never returns InfMod.
invertSomeMod :: SomeMod -> Maybe SomeMod Source #
Computes the inverse value, if it exists.
>>>invertSomeMod (3 `modulo` 10)Just (7 `modulo` 10) -- because 3 * 7 = 1 :: Mod 10>>>invertSomeMod (4 `modulo` 10)Nothing>>>invertSomeMod (fromRational (2 % 5))Just 5 % 2
powSomeMod :: Integral a => SomeMod -> a -> SomeMod Source #
Drop-in replacement for ^, with much better performance.
When -O is enabled, there is a rewrite rule, which specialises ^ to powSomeMod.
>>>powSomeMod (3 `modulo` 10) 4(1 `modulo` 10)