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