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 positive modulus. If number and modulus are coprime, the result is Just inverse where

   (number * inverse) `mod` modulus == 1
   0 <= inverse < modulus

If number mod modulus == 0 or 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. Modulus must be positive. 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. Modulus must be positive.

chineseRemainder :: [(Integer, Integer)] -> Maybe Integer

Given a list [(r_1,m_1), ..., (r_n,m_n)] of (residue,modulus) pairs, chineseRemainder calculates the solution to the simultaneous congruences

r ≡ r_k (mod m_k)

if all moduli are positive and pairwise coprime. Otherwise the result is Nothing regardless of whether a solution exists.

Partially checked input

sqrtModP :: Integer -> Integer -> Maybe Integer

sqrtModP n prime calculates a modular square root of n modulo prime if that exists. The second argument must be a (positive) prime, otherwise the computation may not terminate and if it does, may yield a wrong result. The precondition is not checked.

If prime is a prime and n a quadratic residue modulo prime, the result is Just r where r^2 ≡ n (mod prime), if n is a quadratic nonresidue, the result is Nothing.

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'.

sqrtModPList :: Integer -> Integer -> [Integer]

sqrtModPList n prime computes the list of all square roots of n modulo prime. prime must be a (positive) prime. The precondition is not checked.

sqrtModP' :: Integer -> Integer -> Integer

sqrtModP' square prime finds a square root of square modulo prime. prime must be a (positive) prime, and square must be a positive quadratic residue modulo prime, i.e. 'jacobi square prime == 1. The precondition is not checked.

tonelliShanks :: Integer -> Integer -> Integer

tonelliShanks square prime calculates a square root of square modulo prime, where prime is a prime of the form 4*k + 1 and square is a positive quadratic residue modulo prime, using the Tonelli-Shanks algorithm. No checks on the input are performed.

sqrtModPP :: Integer -> (Integer, Int) -> Maybe Integer

sqrtModPP n (prime,expo) calculates a square root of n modulo prime^expo if one exists. prime must be a (positive) prime. expo must be positive, n must be coprime to prime

sqrtModPPList :: Integer -> (Integer, Int) -> [Integer]

sqrtModPPList n (prime,expo) calculates the list of all square roots of n modulo prime^expo. The same restriction as in sqrtModPP applies to the arguments.

sqrtModF :: Integer -> [(Integer, Int)] -> Maybe Integer

sqrtModF n primePowers calculates a square root of n modulo product [p^k | (p,k) <- primePowers] if one exists and all primes are distinct. The list must be non-empty, n must be coprime with all primes.

sqrtModFList :: Integer -> [(Integer, Int)] -> [Integer]

sqrtModFList n primePowers calculates all square roots of n modulo product [p^k | (p,k) <- primePowers] if all primes are distinct. The list must be non-empty, n must be coprime with all primes.

chineseRemainder2 :: (Integer, Integer) -> (Integer, Integer) -> Integer

chineseRemainder2 (r_1,m_1) (r_2,m_2) calculates the solution of

r ≡ r_k (mod m_k)

if m_1 and m_2 are coprime.