Safe Haskell | None |
---|---|

Language | Haskell2010 |

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.

- data Integer
- = S# Int#
- | J# Int# ByteArray#

- gcdInt :: Int# -> Int# -> Int#
- gcdInteger :: Integer -> Integer -> Integer
- gcdExtInteger :: Integer -> Integer -> (#Integer, Integer#)
- lcmInteger :: Integer -> Integer -> Integer
- nextPrimeInteger :: Integer -> Integer
- testPrimeInteger :: Integer -> Int# -> Int#
- powInteger :: Integer -> Word# -> Integer
- powModInteger :: Integer -> Integer -> Integer -> Integer
- powModSecInteger :: Integer -> Integer -> Integer -> Integer
- recipModInteger :: Integer -> Integer -> Integer
- sizeInBaseInteger :: Integer -> Int# -> Word#
- importIntegerFromByteArray :: ByteArray# -> Word# -> Word# -> Int# -> Integer
- importIntegerFromAddr :: Addr# -> Word# -> Int# -> State# s -> (#State# s, Integer#)
- exportIntegerToMutableByteArray :: Integer -> MutableByteArray# s -> Word# -> Int# -> State# s -> (#State# s, Word##)
- exportIntegerToAddr :: Integer -> Addr# -> Int# -> State# s -> (#State# s, Word##)

# The `Integer`

type

Arbitrary-precision integers.

S# Int# | "small" integers fitting into an |

J# Int# ByteArray# | "big" integers represented as GMP's The This representation tries to avoid using the GMP number
representation for small integers that fit into a native
Note: It does |

# Number theoretic functions

gcdInteger :: Integer -> Integer -> Integer Source

Compute greatest common divisor.

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

Extended euclidean algorithm.

For

and *a*

, compute their greatest common divisor *b*

and the coefficient *g*

satisfying *s*

.*a**s* + *b**t* = *g*

*Since: 0.5.1.0*

lcmInteger :: Integer -> Integer -> Integer Source

Compute least common multiple.

nextPrimeInteger :: Integer -> Integer Source

Compute next prime greater than

probalistically.*n*

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.

"

" determines whether `testPrimeInteger`

*n* *k*

is prime
and returns one of the following results:*n*

`2#`

is returned if

is definitely prime,*n*`1#`

if

is a*n**probable prime*, or`0#`

if

is definitely not a prime.*n*

The

argument controls how many test rounds are performed for
determining a *k**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

"

" computes base `powInteger`

*b* *e*

raised to exponent *b*

.*e*

*Since: 0.5.1.0*

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

"

" computes base `powModInteger`

*b* *e* *m*

raised to
exponent *b*

modulo *e*

.*m*

Negative exponents are supported if an inverse modulo

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 *m*`recipModInteger`

.

*Since: 0.5.1.0*

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

"

" computes base `powModSecInteger`

*b* *e* *m*

raised to
exponent *b*

modulo *e*

. It is required that *m*

and
*e* > 0

is odd.*m*

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

, and a warning will be emitted when used.`powModInteger`

*Since: 0.5.1.0*

recipModInteger :: Integer -> Integer -> Integer Source

"

" computes the inverse of `recipModInteger`

*x* *m*

modulo *x*

. If
the inverse exists, the return value *m*

will satisfy *y*`0 < `

, otherwise the result is *y* <
abs(*m*)`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:

- "

" (see also comment in`sizeInBaseInteger`

0*base*= 1`exportIntegerToMutableByteArray`

). - This function is only defined if

and*base*>= 2#

(Note: the documentation claims that only*base*<= 256#

is supported, however the actual implementation supports up to base 256).*base*<= 62# - If

is a power of 2, the result will be exact. In other cases (e.g. for*base*

), the result*base*= 10#*may*be 1 digit too large sometimes. - "

" can be used to determine the most significant bit of`sizeInBaseInteger`

*i*2#

.*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`

baoffsetsizeorder

reads

bytes from the*size*`ByteArray#`

starting at*ba**offset*- with most significant byte first if

is*order*`1#`

or least significant byte first if

is*order*`-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

in
base-256 representation.*addr*

`importIntegerFromAddr`

addrsizeorder

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`

imbaoffsetorder

writes

- the
`Integer`

*i* - into the
`MutableByteArray#`

starting at*mba**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 "

" to compute the exact number of
bytes written in advance for `sizeInBaseInteger`

*i* 256#

. In case of *i* /= 0

,
*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

in base-256 representation.*addr*

`exportIntegerToAddr`

addroe

See description of `exportIntegerToMutableByteArray`

for more details.

*Since: 0.5.1.0*