Portability | Non-portable (GHC extensions) |
---|---|
Stability | Provisional |
Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |
Miscellaneous functions related to modular arithmetic.
- jacobi :: (Integral a, Bits a) => a -> a -> Int
- invertMod :: Integer -> Integer -> Maybe Integer
- powerMod :: (Integral a, Bits a) => Integer -> a -> Integer -> Integer
- powerModInteger :: Integer -> Integer -> Integer -> Integer
- jacobi' :: (Integral a, Bits a) => a -> a -> Int
- powerMod' :: (Integral a, Bits a) => Integer -> a -> Integer -> Integer
- powerModInteger' :: Integer -> Integer -> Integer -> Integer
Functions with input check
jacobi :: (Integral a, Bits a) => a -> a -> IntSource
Jacobi symbol of two numbers. The "denominator" must be odd and positive, this condition is checked.
If both numbers have a common prime factor, the result
is 0
, otherwise it is ±1.
invertMod :: Integer -> Integer -> Maybe IntegerSource
Invert a number relative to a modulus.
If number
and modulus
are coprime, the result is
Just inverse
where
(number * inverse) `mod` (abs modulus) == 1 0 <= inverse < abs modulus
unless modulus == 0
and abs number == 1
, in which case the
result is Just number
.
If gcd number modulus > 1
, the result is Nothing
.
powerMod :: (Integral a, Bits a) => Integer -> a -> Integer -> IntegerSource
Modular power.
powerMod base exponent modulus
calculates (base ^ exponent) `mod` modulus
by repeated squaring and reduction.
If exponent < 0
and base
is invertible modulo modulus
, (inverse ^ |exponent|) `mod` modulus
is calculated. This function does some input checking and sanitation before calling the unsafe worker.
Unchecked functions
jacobi' :: (Integral a, Bits a) => a -> a -> IntSource
Jacobi symbol of two numbers without validity check of the "denominator".