Invariant:Jn# andJp# are used iff value doesn't fit inS#

Useful properties resulting from the invariants:

• abs (S# _) <= abs (Jp# _)

• abs (S# _) <  abs (Jn# _)

Constructors

Test whether all internal invariants are satisfied byInteger value

Returns1# if valid,0# otherwise.

This operation is mostly useful for test-suites and/or code which constructsInteger values directly.

Integer for which onlyn-th bit is set. Undefined behaviour for negativen values.

Count number of set bits. For negative arguments returns negative population count of negated argument.

Compute greatest common divisor.

Extended euclidean algorithm.

Fora andb, compute their greatest common divisorg and the coefficients satisfyingas +bt =g.

Since: integer-gmp-0.5.1.0

Compute least common multiple.

SquareInteger

"powModIntegerbem" computes baseb raised to exponente moduloabs(m).

Negative exponents are supported if an inverse modulom exists.

Warning: 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 alsorecipModInteger.

Future versions ofinteger_gmp may not support negativee values anymore.

Since: integer-gmp-0.5.1.0

"powModSecIntegerbem" computes baseb raised to exponente modulom. It is required thate >= 0 andm is odd.

This is a "secure" variant ofpowModInteger using thempz_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 topowModInteger, and a warning will be emitted when used.

Since: integer-gmp-1.0.2.0

"recipModIntegerxm" computes the inverse ofx modulom. If the inverse exists, the return valuey will satisfy0 <y < abs(m), otherwise the result is0.

Since: integer-gmp-0.5.1.0

Type representingraw arbitrary-precision Naturals

This is common type used byNatural andInteger. As this type consists of a single constructor wrapping aByteArray# it can be unpacked.

Essential invariants:

• ByteArray# size is an exact multiple ofWord# size
• limbs are stored in least-significant-limb-first order,
• the most-significant limb must be non-zero, except for
• 0 which is represented as a 1-limb.

Constructors

Type representing a GMP Limb

Count ofGmpLimbs, must be positive (unless specified otherwise).

Test whether all internal invariants are satisfied byBigNat value

Returns1# if valid,0# otherwise.

This operation is mostly useful for test-suites and/or code which constructsInteger values directly.

Return number of limbs contained inBigNat.

CAF representing the value0 :: BigNat

CAF representing the value1 :: BigNat

Special 0-sized bigNat returned in case of arithmetic underflow

This is currently only returned by the following operations:

• minusBigNat
• minusBigNatWord

Other operations such asquotBigNat may returnnullBigNat as well as a dummy/place-holder value instead ofundefined since we can't throw exceptions. But that behaviour should not be relied upon.

NB:isValidBigNat# nullBigNat is false

ConstructBigNat from existingByteArray# containingnGmpLimbs in least-significant-first order.

If possibleByteArray#, will be used directly (i.e. sharedwithout cloning theByteArray# into a newly allocated one)

Note: size parameter (timessizeof(GmpLimb)) must be less or equal to itssizeofByteArray#.

Construct 1-limbBigNat fromWord#

Construct BigNat from 2 limbs. The first argument is the most-significant limb.

Equivalent toword2Int# .bigNatToWord

Same asindexBigNat# bn 0#

Extractn-th (0-based) limb inBigNat.n must be less than size as reported bysizeofBigNat#.

ReturnsnullBigNat (seeisNullBigNat#) in case of underflow

ReturnsnullBigNat (seeisNullBigNat#) in case of underflow

SquareBigNat

If divisor is zero,(#nullBigNat,nullBigNat #) is returned

Note: Result of div/0 undefined

div/0 not checked

Version ofpowModInteger operating onBigNats

Since: integer-gmp-1.0.0.0

Version ofpowModInteger forWord#-sized moduli

Since: integer-gmp-1.0.0.0

Version ofrecipModInteger operating onBigNats

Since: integer-gmp-1.0.0.0

Specialised version of

bitBigNat = shiftLBigNat (wordToBigNat 1##)

avoiding a few redundant allocations

Test ifBigNat value is equal to zero.

Test for special 0-sizedBigNat representing underflows.

Compute greatest common divisor.

Warning: result may become negative if (at least) one argument isminBound

Compute greatest common divisor.

Since: integer-gmp-1.0.0.0

Version ofpowModInteger operating onWord#s

Since: integer-gmp-1.0.0.0

Version ofrecipModInteger operating onWord#s

Since: integer-gmp-1.0.0.0

Probalistic Miller-Rabin primality test.

"testPrimeIntegernk" determines whethern is prime and returns one of the following results:

• 2# is returned ifn is definitely prime,
• 1# ifn is aprobable prime, or
• 0# ifn is definitely not a prime.

Thek argument controls how many test rounds are performed for determining aprobable prime. For more details, seeGMP documentation for `mpz_probab_prime_p()`.

Since: integer-gmp-0.5.1.0

Version oftestPrimeInteger operating onBigNats

Since: integer-gmp-1.0.0.0

Version oftestPrimeInteger operating onWord#s

Since: integer-gmp-1.0.0.0

Compute next prime greater thann probalistically.

According to the GMP documentation, the underlying functionmpz_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: integer-gmp-0.5.1.0

Version ofnextPrimeInteger operating onBigNats

Since: integer-gmp-1.0.0.0

Version ofnextPrimeInteger operating onWord#s

Since: integer-gmp-1.0.0.0

Version ofsizeInBaseInteger operating onBigNat

Since: integer-gmp-1.0.0.0

Compute number of digits (without sign) in givenbase.

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

• "sizeInBaseInteger 0base = 1" (see also comment inexportIntegerToMutableByteArray).
• This function is only defined ifbase >= 2# andbase <= 256# (Note: the documentation claims that onlybase <= 62# is supported, however the actual implementation supports up to base 256).
• Ifbase is a power of 2, the result will be exact. In other cases (e.g. forbase = 10#), the resultmay be 1 digit too large sometimes.
• "sizeInBaseIntegeri 2#" can be used to determine the most significant bit ofi.

Since: integer-gmp-0.5.1.0

Version ofsizeInBaseInteger operating onWord#

Since: integer-gmp-1.0.0.0

Version ofexportIntegerToAddr operating onBigNats.

DumpInteger (without sign) toaddr in base-256 representation.

exportIntegerToAddriaddre

See description ofexportIntegerToMutableByteArray for more details.

Since: integer-gmp-1.0.0.0

Version ofexportIntegerToAddr operating onWords.

Version ofexportIntegerToMutableByteArray operating onBigNats.

Since: integer-gmp-1.0.0.0

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

The call

exportIntegerToMutableByteArrayimbaoffsetmsbf

writes

• theIntegeri
• into theMutableByteArray#mba starting atoffset
• with most significant byte first ifmsbf is1# or least significant byte first ifmsbf is0#, and
• returns number of bytes written.

Use "sizeInBaseIntegeri 256#" to compute the exact number of bytes written in advance fori /= 0. In case ofi == 0,exportIntegerToMutableByteArray will write and report zero bytes written, whereassizeInBaseInteger report one byte.

It's recommended to avoid callingexportIntegerToMutableByteArray for small integers as this function would currently convert those to big integers in msbf to callmpz_export().

Since: integer-gmp-1.0.0.0

Version ofexportIntegerToMutableByteArray operating onWords.

Since: integer-gmp-1.0.0.0

Version ofimportIntegerFromAddr constructing aBigNat

ReadInteger (without sign) from memory location ataddr in base-256 representation.

importIntegerFromAddraddrsizemsbf

See description ofimportIntegerFromByteArray for more details.

Since: integer-gmp-1.0.0.0

Version ofimportIntegerFromByteArray constructing aBigNat

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

The call

importIntegerFromByteArraybaoffsetsizemsbf

reads

• size bytes from theByteArray#ba starting atoffset
• with most significant byte first ifmsbf is1# or least significant byte first ifmsbf is0#, and
• returns a newInteger

Since: integer-gmp-1.0.0.0