integer-gmp-0.5.1.0: Integer library based on GMP

Safe HaskellNone
LanguageHaskell2010

GHC.Integer.GMP.Internals

Contents

Description

This modules provides access to the Integer constructors and exposes some highly optimized GMP-operations.

Note that since integer-gmp does not depend on base, error reporting via exceptions, error, or undefined is not available. Instead, the low-level functions will crash the runtime if called with invalid arguments.

See also GHC Commentary: Libraries/Integer.

Synopsis

The Integer type

data Integer Source

Arbitrary-precision integers.

Constructors

S# Int#

"small" integers fitting into an Int#

J# Int# ByteArray#

"big" integers represented as GMP's mpz_t structure.

The Int# field corresponds to mpz_t's _mp_size field, which encodes the sign and the number of limbs stored in the ByteArray# field (i.e. mpz_t's _mp_d field). Note: The ByteArray# may have been over-allocated, and thus larger than the size denoted by the Int# field.

This representation tries to avoid using the GMP number representation for small integers that fit into a native Int#. This allows to reduce (or at least defer) calling into GMP for operations whose results remain in the Int#-domain.

Note: It does not constitute a violation of invariants to represent an integer which would fit into an Int# with the J#-constructor. For instance, the value 0 has (only) two valid representations, either S# 0# or J# 0 _.

Instances

Eq Integer 
Ord Integer 

Number theoretic functions

gcdInt :: Int# -> Int# -> Int# Source

Compute greatest common divisor.

gcdInteger :: Integer -> Integer -> Integer Source

Compute greatest common divisor.

gcdExtInteger :: Integer -> Integer -> (#Integer, Integer#) Source

Extended euclidean algorithm.

For a and b, compute their greatest common divisor g and the coefficient s satisfying as + bt = g.

Since: 0.5.1.0

lcmInteger :: Integer -> Integer -> Integer Source

Compute least common multiple.

nextPrimeInteger :: Integer -> Integer Source

Compute next prime greater than n probalistically.

According to the GMP documentation, the underlying function mpz_nextprime() "uses a probabilistic algorithm to identify primes. For practical purposes it's adequate, the chance of a composite passing will be extremely small."

Since: 0.5.1.0

testPrimeInteger :: Integer -> Int# -> Int# Source

Probalistic Miller-Rabin primality test.

"testPrimeInteger n k" determines whether n is prime and returns one of the following results:

  • 2# is returned if n is definitely prime,
  • 1# if n is a probable prime, or
  • 0# if n is definitely not a prime.

The k argument controls how many test rounds are performed for determining a probable prime. For more details, see GMP documentation for `mpz_probab_prime_p()`.

Since: 0.5.1.0

Exponentiation functions

powInteger :: Integer -> Word# -> Integer Source

"powInteger b e" computes base b raised to exponent e.

Since: 0.5.1.0

powModInteger :: Integer -> Integer -> Integer -> Integer Source

"powModInteger b e m" computes base b raised to exponent e modulo m.

Negative exponents are supported if an inverse modulo m exists. It's advised to avoid calling this primitive with negative exponents unless it is guaranteed the inverse exists, as failure to do so will likely cause program abortion due to a divide-by-zero fault. See also recipModInteger.

Since: 0.5.1.0

powModSecInteger :: Integer -> Integer -> Integer -> Integer Source

"powModSecInteger b e m" computes base b raised to exponent e modulo m. It is required that e > 0 and m is odd.

This is a "secure" variant of powModInteger using the mpz_powm_sec() function which is designed to be resilient to side channel attacks and is therefore intended for cryptographic applications.

This primitive is only available when the underlying GMP library supports it (GMP >= 5). Otherwise, it internally falls back to powModInteger, and a warning will be emitted when used.

Since: 0.5.1.0

recipModInteger :: Integer -> Integer -> Integer Source

"recipModInteger x m" computes the inverse of x modulo m. If the inverse exists, the return value y will satisfy 0 < y < abs(m), otherwise the result is 0.

Note: The implementation exploits the undocumented property of mpz_invert() to not mangle the result operand (which is initialized to 0) in case of non-existence of the inverse.

Since: 0.5.1.0

Import/export functions

sizeInBaseInteger :: Integer -> Int# -> Word# Source

Compute number of digits (without sign) in given base.

It's recommended to avoid calling sizeInBaseInteger for small integers as this function would currently convert those to big integers in order to call mpz_sizeinbase().

This function wraps mpz_sizeinbase() which has some implementation pecularities to take into account:

  • "sizeInBaseInteger 0 base = 1" (see also comment in exportIntegerToMutableByteArray).
  • This function is only defined if base >= 2# and base <= 256# (Note: the documentation claims that only base <= 62# is supported, however the actual implementation supports up to base 256).
  • If base is a power of 2, the result will be exact. In other cases (e.g. for base = 10#), the result may be 1 digit too large sometimes.
  • "sizeInBaseInteger i 2#" can be used to determine the most significant bit of i.

Since: 0.5.1.0

importIntegerFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> Integer Source

Read Integer (without sign) from byte-array in base-256 representation.

The call

importIntegerFromByteArray ba offset size order

reads

  • size bytes from the ByteArray# ba starting at offset
  • with most significant byte first if order is 1# or least significant byte first if order is -1#, and
  • returns a new Integer

Since: 0.5.1.0

importIntegerFromAddr :: Addr# -> Word# -> Int# -> State# s -> (#State# s, Integer#) Source

Read Integer (without sign) from memory location at addr in base-256 representation.

importIntegerFromAddr addr size order

See description of importIntegerFromByteArray for more details.

Since: 0.5.1.0

exportIntegerToMutableByteArray :: Integer -> MutableByteArray# s -> Word# -> Int# -> State# s -> (#State# s, Word##) Source

Dump Integer (without sign) to mutable byte-array in base-256 representation.

The call

exportIntegerToMutableByteArray i mba offset order

writes

  • the Integer i
  • into the MutableByteArray# mba starting at offset
  • with most significant byte first if order is 1# or least significant byte first if order is -1#, and
  • returns number of bytes written.

Use "sizeInBaseInteger i 256#" to compute the exact number of bytes written in advance for i /= 0. In case of i == 0, exportIntegerToMutableByteArray will write and report zero bytes written, whereas sizeInBaseInteger report one byte.

It's recommended to avoid calling exportIntegerToMutableByteArray for small integers as this function would currently convert those to big integers in order to call mpz_export().

Since: 0.5.1.0

exportIntegerToAddr :: Integer -> Addr# -> Int# -> State# s -> (#State# s, Word##) Source

Dump Integer (without sign) to addr in base-256 representation.

exportIntegerToAddr addr o e

See description of exportIntegerToMutableByteArray for more details.

Since: 0.5.1.0