arithmoi-0.2.0.6: Efficient basic number-theoretic functions. Primes, powers, integer logarithms.

PortabilityNon-portable (GHC extensions)
StabilityProvisional
MaintainerDaniel Fischer <daniel.is.fischer@googlemail.com>
Safe HaskellSafe-Infered

Math.NumberTheory.Moduli

Contents

Description

Miscellaneous functions related to modular arithmetic.

Synopsis

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.

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

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

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

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

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

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

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