Math.NumberTheory.Moduli

Miscellaneous functions related to modular arithmetic.

Functions with input check

jacobi :: (Integral a, Bits a) => a -> a -> Int

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 Integer

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

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.

powerModInteger :: Integer -> Integer -> Integer -> Integer

Specialised version of powerMod for Integer exponents. Reduces the number of shifts of the exponent since shifting large Integers is expensive. Call this function directly if you don't want or can't rely on rewrite rules.

Unchecked functions

jacobi' :: (Integral a, Bits a) => a -> a -> Int

Jacobi symbol of two numbers without validity check of the "denominator".

powerMod' :: (Integral a, Bits a) => Integer -> a -> Integer -> Integer

Modular power worker without input checking. Assumes all arguments strictly positive and modulus greater than 1.

powerModInteger' :: Integer -> Integer -> Integer -> Integer

Specialised worker without input checks. Makes the same assumptions as the general version powerMod'.