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

Portability Non-portable (GHC extensions) Provisional Daniel Fischer Safe-Infered

Math.NumberTheory.Moduli

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.

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.

Specialised version of `powerMod` for `Integer` exponents. Reduces the number of shifts of the exponent since shifting large `Integer`s 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.

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