arithmoi-0.12.1.0: Efficient basic number-theoretic functions.

Copyright | (c) 2017 Andrew Lelechenko
License | MIT
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | Safe-Inferred
Language | Haskell2010

Math.NumberTheory.Powers.Modular

Description

Deprecated: Use Data.Mod or Data.Mod.Word instead

Modular powers (a. k. a. modular exponentiation).

Synopsis

- powMod :: (Integral a, Integral b) => a -> b -> a -> a
- powModWord :: Word -> Word -> Word -> Word
- powModInt :: Int -> Int -> Int -> Int

# Documentation

powMod :: (Integral a, Integral b) => a -> b -> a -> a Source #

`powMod` `b` `e` `m` computes (`b^e`) `mod` `m` in effective way. An exponent `e` must be non-negative, a modulo `m` must be positive. Otherwise the behaviour of `powMod` is undefined.

    >>> powMod 2 3 5
    3
    >>> powMod 3 12345678901234567890 1001
    1

See also `powMod` and `powSomeMod`.

For finite numeric types (`Int`, `Word`, etc.) modulo `m` should be such that `m^2` does not overflow, otherwise the behaviour is undefined. If you need both to fit into machine word and to handle large moduli, take a look at `powModInt` and `powModWord`.

    >>> powMod 3 101 (2^60-1 :: Integer) -- correct
    1018105167100379328
    >>> powMod 3 101 (2^60-1 :: Int) -- incorrect due to overflow
    1115647832265427613
    >>> powModInt 3 101 (2^60-1 :: Int) -- correct
    1018105167100379328

powModWord :: Word -> Word -> Word -> Word Source #

Specialised version of `powMod`, able to handle large moduli correctly.

    >>> powModWord 3 101 (2^60-1)
    1018105167100379328

powModInt :: Int -> Int -> Int -> Int Source #

Specialised version of `powMod`, able to handle large moduli correctly.

    >>> powModInt 3 101 (2^60-1)
    1018105167100379328