Arbitrary-precision integers.

Compute greatest common divisor.

Compute greatest common divisor.

Extended euclidean algorithm.

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

Compute least common multiple.

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

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()`.

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

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

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

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

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.

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

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

 importIntegerFromAddr addr size order
 

See description of importIntegerFromByteArray for more details.

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().

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

 exportIntegerToAddr addr o e
 

See description of exportIntegerToMutableByteArray for more details.