Detailed Description

Author: hacatu

Version: 0.2.0

LICENSE

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

DESCRIPTION

Functions for dealing with modular arithmetic on 64 bit integers (not suitable for large integers which may overflow, around 2^31. a bignum-enabled version may be created to handle this)

Definition in file modular_math.h.

Go to the source code of this file.

Data Structures
struct	nut_u64_Pitcharr
	A fixed capacity array. More...

Macros
#define	NUT_ATTR_ACCESS(...)
	Wrapper for gcc's `access` function annotation - no clang equivalent, and currently disabled because it is bugged See https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html.

#define	NUT_ATTR_NO_SAN(name)
	Prevent clang from reporting spurious errors when a length zero array is passed to a length annotated function parameter.

#define	NUT_ATTR_CONST
	Wrapper for gnu::const attr - such a function has no side effects and cannot read memory.

#define	NUT_ATTR_PURE
	Wrapper for gnu::pure attr - similar to const but the function can read non-volatile memory (including passed-in pointers)

#define	NUT_ATTR_NODISCARD
	Wrapper for nodiscard attr - requires return value be used.

#define	NUT_ATTR_NONNULL(...)
	Wrapper for gnu::nonnull attr.

#define	NUT_ATTR_RETURNS_NONNULL
	Wrapper for gnu::returns_nonnull attr.

#define	NUT_ATTR_MALLOC
	Wrapper for gnu::malloc attr - indicates the function returns a malloc'd pointer that must be free'd.

#define	NUT_ATTR_ARTIFICIAL
	Wrapper for gnu::artificial attr - hint that the function should be ignored in debuggers.

Typedefs
typedef signed __int128	int128_t
	Pretty name for signed 128 bit integer.

typedef unsigned __int128	uint128_t
	Pretty name for unsigned 128 bit integer.

Functions
uint64_t	nut_u64_pow (uint64_t b, uint64_t e)
	Compute nonnegative integral power of integer using binary exponentiation.

uint128_t	nut_u128_pow (uint128_t b, uint64_t e)
	Compute nonnegative integral power of integer using binary exponentiation.

uint64_t	nut_u64_powmod (uint64_t b, uint64_t e, uint64_t n)
	Compute nonnegative integral power of a number modulo another using binary exponentiation.

uint64_t	nut_u64_binom (uint64_t n, uint64_t k)
	Compute single binomial coefficient semi-naively.

uint64_t	nut_u64_binom_next (uint64_t n, uint64_t k, uint64_t prev)
	Compute the binomial coefficient for (n choose k) given the binomial coefficient for (n choose k-1) Simply uses the recurrence (n choose k) = (n - k + 1)/k * (n choose k-1) The starting point should be (n choose 0) = 1.

uint64_t	nut_u64_prand (uint64_t a, uint64_t b)
	Generate a (pseudo)random integer uniformly from [a, b).

uint64_t	nut_u64_rand (uint64_t a, uint64_t b)
	Generate a (strong) random integer uniformly from [a, b).

int64_t	nut_i64_egcd (int64_t a, int64_t b, int64_t restrict _t, int64_t restrict _s)
	Compute d = gcd(a, b) and x, y st.

int64_t	nut_i64_modinv (int64_t a, int64_t b)
	Find the multiplicative inverse of a mod b If b is a power of 2, use `nut_i64_modinv_2t` Just a wrapper around `nut_i64_egcd`.

uint64_t	nut_u64_modinv_2t (uint64_t a, uint64_t t)
	Find the multiplicative inverse of a mod 2t This uses a hensel/newton like iterative algorithm, described here https://crypto.stackexchange.com/a/47496 Basically, we use a lookup table to get the inverse mod 28, and then use the fact that ax = 1 mod 2k --> ax(2-ax) = 1 mod 2(2k) to lift the inverse to mod 216, mode 232, etc as needed.

int64_t	nut_i64_mod (int64_t a, int64_t n)
	Compute the Euclidean remainder r = a mod n for positive n so that 0 <= r < n.

int64_t	nut_i64_crt (int64_t a, int64_t p, int64_t b, int64_t q)
	Compute n mod pq st n = a mod p and n = b mod q, where p and q are coprime.

int128_t	nut_i128_crt (int64_t a, int64_t p, int64_t b, int64_t q)
	Compute n mod pq st n = a mod p and n = b mod q, where p and q are coprime.

int64_t	nut_i64_lcm (int64_t a, int64_t b)
	Compute the least common multiple of a and b Divides the product by the gcd so can overflow for large arguments.

uint64_t	nut_u64_binom_next_mod_2t (uint64_t n, uint64_t k, uint64_t t, uint64_t restrict v2, uint64_t restrict p2)
	Compute the binomial coefficient for (n choose k) given the binomial coefficient for (n choose k-1) Simply uses the recurrence (n choose k) = (n - k + 1)/k * (n choose k-1) The starting point should be (n choose 0) = 1.

int64_t	nut_i64_jacobi (int64_t n, int64_t k)
	Compute the Jacobi symbol of n mod k.

uint64_t *	nut_u64_make_jacobi_tbl (uint64_t p, int64_t partial_sums[restrict static p])
	Compute the Jacobi symbol for all numbers mod a prime.

int64_t	nut_u64_jacobi_tbl_get (uint64_t n, uint64_t p, const uint64_t is_qr[restrict static(p+63)/64])
	Convenience function to get the jacobi symbol for n from a table The table should come from `nut_u64_make_jacobi_tbl`.

int64_t	nut_i64_rand_nr_mod (int64_t p)
	Compute a random number mod a prime that is not a quadratic residue.

int64_t	nut_i64_sqrt_shanks (int64_t n, int64_t p)
	Compute the square root of a quadratic residue mod a prime.

int64_t	nut_i64_sqrt_cipolla (int64_t n, int64_t p)
	Compute the square root of a quadratic residue mod a prime.

int64_t	nut_i64_sqrt_mod (int64_t n, int64_t p)
	Compute the square root of a quadratic residue mod a prime.

uint64_t	nut_i32_fastmod_init (uint32_t pd)
	Compute a constant to use to do modular division faster.

uint64_t	nut_u32_fastmod_init (uint32_t d)
	Compute a constant to use to do modular division faster.

uint128_t	nut_i64_fastmod_init (uint64_t pd)
	Compute a constant to use to do modular division faster.

uint128_t	nut_u64_fastmod_init (uint64_t d)
	Compute a constant to use to do modular division faster.

int32_t	nut_i32_fastmod_trunc (int32_t n, uint32_t pd, uint64_t c)
	Compute n mod d, choosing the smallest signed remainder.

int32_t	nut_i32_fastmod_floor (int32_t n, uint32_t pd, uint64_t c)
	Compute n mod d, choosing the euclidean remainder.

uint32_t	nut_u32_fastmod (uint32_t n, uint32_t d, uint64_t c)
	Compute n mod d faster using a precomputed constant.

int64_t	nut_i64_fastmod_trunc (int64_t n, uint64_t pd, uint128_t c)
	Compute n mod d, choosing the smallest signed remainder.

int64_t	nut_i64_fastmod_floor (int64_t n, uint64_t pd, uint128_t c)
	Compute n mod d, choosing the euclidean remainder.

uint64_t	nut_u64_fastmod (uint64_t n, uint64_t d, uint128_t c)
	Compute n mod d faster using a precomputed constant.

Macro Definition Documentation

◆ NUT_ATTR_ACCESS

#define NUT_ATTR_ACCESS ( ... )

Wrapper for gcc's access function annotation - no clang equivalent, and currently disabled because it is bugged See https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html.

Definition at line 40 of file modular_math.h.

◆ NUT_ATTR_NO_SAN

#define NUT_ATTR_NO_SAN ( name )

Prevent clang from reporting spurious errors when a length zero array is passed to a length annotated function parameter.

Definition at line 47 of file modular_math.h.

◆ NUT_ATTR_CONST

#define NUT_ATTR_CONST

Wrapper for gnu::const attr - such a function has no side effects and cannot read memory.

Definition at line 54 of file modular_math.h.

◆ NUT_ATTR_PURE

#define NUT_ATTR_PURE

Wrapper for gnu::pure attr - similar to const but the function can read non-volatile memory (including passed-in pointers)

Definition at line 61 of file modular_math.h.

◆ NUT_ATTR_NODISCARD

#define NUT_ATTR_NODISCARD

Wrapper for nodiscard attr - requires return value be used.

Definition at line 68 of file modular_math.h.

◆ NUT_ATTR_NONNULL

#define NUT_ATTR_NONNULL ( ... )

Wrapper for gnu::nonnull attr.

Definition at line 75 of file modular_math.h.

◆ NUT_ATTR_RETURNS_NONNULL

#define NUT_ATTR_RETURNS_NONNULL

Wrapper for gnu::returns_nonnull attr.

Definition at line 82 of file modular_math.h.

◆ NUT_ATTR_MALLOC

#define NUT_ATTR_MALLOC

Wrapper for gnu::malloc attr - indicates the function returns a malloc'd pointer that must be free'd.

Definition at line 89 of file modular_math.h.

◆ NUT_ATTR_ARTIFICIAL

#define NUT_ATTR_ARTIFICIAL

Wrapper for gnu::artificial attr - hint that the function should be ignored in debuggers.

Definition at line 96 of file modular_math.h.

Typedef Documentation

◆ int128_t

typedef signed __int128 int128_t

Pretty name for signed 128 bit integer.

GCC implements 128 bit arithmetic in terms of 64 bit arithmetic.

Definition at line 20 of file modular_math.h.

◆ uint128_t

typedef unsigned __int128 uint128_t

Pretty name for unsigned 128 bit integer.

GCC implements 128 bit arithmetic in terms of 64 bit arithmetic.

Definition at line 23 of file modular_math.h.

Function Documentation

◆ nut_u64_pow()

uint64_t nut_u64_pow	(	uint64_t	b,
		uint64_t	e
	)

Compute nonnegative integral power of integer using binary exponentiation.

Parameters

[in] b,e base and exponent

Returns: b^e, not checked for overflow

◆ nut_u128_pow()

uint128_t nut_u128_pow	(	uint128_t	b,
		uint64_t	e
	)

Compute nonnegative integral power of integer using binary exponentiation.

Parameters

[in] b,e base and exponent

Returns: b^e, not checked for overflow

◆ nut_u64_powmod()

uint64_t nut_u64_powmod	(	uint64_t	b,
		uint64_t	e,
		uint64_t	n
	)

Compute nonnegative integral power of a number modulo another using binary exponentiation.

Parameters

[in] b,e,n base, exponent, and modulus

Returns: b^e mod n, computed via binary exponentiation

◆ nut_u64_binom()

uint64_t nut_u64_binom	(	uint64_t	n,
		uint64_t	k
	)

Compute single binomial coefficient semi-naively.

Repeatedly does multiplications by n, n-1, n-2, ..., n-k+1 interleaved with divisions by 1, 2, 3, ..., k. Overflows quickly, look into mod m versions if using large inputs. See nut_u64_binom_next to iterate over values (n choose k), (n choose k+1). See nut_u64_binom_next_mod_2t to iterate over values mod powers of 2

Parameters

[in] n,k Binomial coefficient arguments

◆ nut_u64_binom_next()

uint64_t nut_u64_binom_next	(	uint64_t	n,
		uint64_t	k,
		uint64_t	prev
	)

Compute the binomial coefficient for (n choose k) given the binomial coefficient for (n choose k-1) Simply uses the recurrence (n choose k) = (n - k + 1)/k * (n choose k-1) The starting point should be (n choose 0) = 1.

To start at k != 0, use nut_u64_binom. See nut_u64_binom_next_mod_2t to iterate over values mod powers of 2.

Parameters

[in]	n,k	Binomial coefficient arguments
[in]	prev	Binomial coefficient value for (n choose k-1)

◆ nut_u64_prand()

uint64_t nut_u64_prand	(	uint64_t	a,
		uint64_t	b
	)

Generate a (pseudo)random integer uniformly from [a, b).

Currently calls nut_u64_rand so this number is generated from /dev/random but this function exists to provide a weaker, pseudorandom number source if this turns out to be a bottleneck.

Parameters

[in] a,b bounds of the interval [a, b)

Returns: (pseudo)random integer uniformly chosen from [a, b)

◆ nut_u64_rand()

uint64_t nut_u64_rand	(	uint64_t	a,
		uint64_t	b
	)

Generate a (strong) random integer uniformly from [a, b).

Currently uses /dev/random via the getrandom function, but this is a Linux api.

Parameters

[in] a,b bounds of the interval [a, b)

Returns: (strong) random integer uniformly chosen from [a, b)

◆ nut_i64_egcd()

int64_t nut_i64_egcd	(	int64_t	a,
		int64_t	b,
		int64_t *restrict	_t,
		int64_t *restrict	_s
	)

Compute d = gcd(a, b) and x, y st.

xa + by = d.

Parameters

[in]	a,b	numbers to find gcd of
[out]	_t,_s	pointers to output x and y to respectively (ignored if NULL)

Returns: d

◆ nut_i64_modinv()

int64_t nut_i64_modinv	(	int64_t	a,
		int64_t	b
	)

Find the multiplicative inverse of a mod b If b is a power of 2, use nut_i64_modinv_2t Just a wrapper around nut_i64_egcd.

If a and b are not coprime, then the value returned will just be the bezout coefficient for a, and will yield gcd(a, b) when multiplied with a mod b instead of 1.

◆ nut_u64_modinv_2t()

uint64_t nut_u64_modinv_2t	(	uint64_t	a,
		uint64_t	t
	)

Find the multiplicative inverse of a mod 2**t This uses a hensel/newton like iterative algorithm, described here https://crypto.stackexchange.com/a/47496 Basically, we use a lookup table to get the inverse mod 2**8, and then use the fact that ax = 1 mod 2**k --> ax(2-ax) = 1 mod 2**(2k) to lift the inverse to mod 2**16, mode 2**32, etc as needed.

This does cap out at 2**64.

Parameters

[in]	a	number to invert, MUST be odd.
[in]	t	Exponent of modulus, ie we want to work mod 2**t, MUST be <= 64. 0 and 1 are allowed, but won't give very interesting results.

Returns: b such that a*b = 1 mod 2**t and 0 <= b < 2**t

◆ nut_i64_mod()

int64_t nut_i64_mod	(	int64_t	a,
		int64_t	n
	)

Compute the Euclidean remainder r = a mod n for positive n so that 0 <= r < n.

Parameters

[in] a,n dividend and divisor

Returns: a mod n

◆ nut_i64_crt()

int64_t nut_i64_crt	(	int64_t	a,
		int64_t	p,
		int64_t	b,
		int64_t	q
	)

Compute n mod pq st n = a mod p and n = b mod q, where p and q are coprime.

Parameters

[in] a,p,b,q Chinese Remainder Theorem parameters. The residues a and b should not be negative. The moduli p and q should be coprime.

Returns: 0 <= 0 < pq so that n = a mod p and n = b mod q

◆ nut_i128_crt()

int128_t nut_i128_crt	(	int64_t	a,
		int64_t	p,
		int64_t	b,
		int64_t	q
	)

Compute n mod pq st n = a mod p and n = b mod q, where p and q are coprime.

Parameters

[in] a,p,b,q Chinese Remainder Theorem parameters. The residues a and b should not be negative. The moduli p and q should be coprime.

Returns: 0 <= 0 < pq so that n = a mod p and n = b mod q

◆ nut_i64_lcm()

int64_t nut_i64_lcm	(	int64_t	a,
		int64_t	b
	)

Compute the least common multiple of a and b Divides the product by the gcd so can overflow for large arguments.

Parameters

[in] a,b numbers to find nut_i64_lcm of

Returns: nut_i64_lcm(a, b)

◆ nut_u64_binom_next_mod_2t()

uint64_t nut_u64_binom_next_mod_2t	(	uint64_t	n,
		uint64_t	k,
		uint64_t	t,
		uint64_t *restrict	v2,
		uint64_t *restrict	p2
	)

Compute the binomial coefficient for (n choose k) given the binomial coefficient for (n choose k-1) Simply uses the recurrence (n choose k) = (n - k + 1)/k * (n choose k-1) The starting point should be (n choose 0) = 1.

To start at k != 0, use nut_u64_binom. See nut_u64_binom_next_mod_2t to iterate over values mod powers of 2.

Parameters

[in]	n,k	Binomial coefficient arguments
[in]	t	Exponent of modulus, ie we want to work mod 2^t
[in,out]	v2	2-adic valuation of (n choose k-1), that is, the highest power of 2 dividing (n choose k-1). This will be updated in-place, so to start from (n choose 0) it can just be initialized to 0.
[in,out]	p2	2-coprime part of (n choose k-1), that is, (n choose k-1) divided by 2^v2, This will be updated in-place, so to start from (n choose 0) it can just be initialized to 1.

Returns: (n choose k) mod 2^t, which is equal to 2^v2 * p2 mod 2^t

◆ nut_i64_jacobi()

int64_t nut_i64_jacobi	(	int64_t	n,
		int64_t	k
	)

Compute the Jacobi symbol of n mod k.

Uses modified euclidean algorithm.

Parameters

[in] n,k Jacobi symbol parameters

Returns: Jacobi symbol (0 if k | n, +1 if n is a quadratic residue mod an odd number of prime divisors of k (with multiplicity), -1 otherwise)

◆ nut_u64_make_jacobi_tbl()

uint64_t * nut_u64_make_jacobi_tbl	(	uint64_t	p,
		int64_t	partial_sums[restrict static p]
	)

Compute the Jacobi symbol for all numbers mod a prime.

Currently the modulus must be a prime

Parameters

[in]	p	prime to compute all jacobi(r/p) modulo
[out]	partial_sums	buffer to store sums jacobi(0/p) + ... + jacobi(r/p)

Returns: bit array is_qr where the bit for positive r is 0 if r is a nonresidue (jacobi symbol -1), or 1 if r is a residue (jacobi symbol 1). If r is zero, then its jacobi symbol is 0. nut_u64_jacobi_tbl_get handles this automatically

◆ nut_u64_jacobi_tbl_get()

int64_t nut_u64_jacobi_tbl_get	(	uint64_t	n,
		uint64_t	p,
		const uint64_t	is_qr[restrict static(p+63)/64]
	)

Convenience function to get the jacobi symbol for n from a table The table should come from nut_u64_make_jacobi_tbl.

Parameters

[in]	n	residue to find jacobi symbol for, does not need to be reduced
[in]	p	prime that the table was computed for
[in]	is_qr	table from `nut_u64_make_jacobi_symbol`

Returns: the jacobi symbol for jacobi(n/p)

◆ nut_i64_rand_nr_mod()

int64_t nut_i64_rand_nr_mod ( int64_t p )

Compute a random number mod a prime that is not a quadratic residue.

This is useful in Shanks's algorithm and others. This function works by rejection sampling using the Jacobi symbol as a test, which succeeds in 2(p-2)/(p-1) trials on average. If p is not prime, the Jacobi symbol can be positive for a nonresidue, so not all nonresidues are possible, and the number of trials on average could be larger than the prime p case.

Parameters

[in] p the modulus for which to generate a nonresidue. Should be prime.

Returns: a quadratic nonresidue mod p

◆ nut_i64_sqrt_shanks()

int64_t nut_i64_sqrt_shanks	(	int64_t	n,
		int64_t	p
	)

Compute the square root of a quadratic residue mod a prime.

If n is not a residue or p is not a prime, this function is not guaranteed to terminate.

Parameters

[in]	n	a quadratic residue mod p
[in]	p	a prime

Returns: r so that r^2 = n mod p

◆ nut_i64_sqrt_cipolla()

int64_t nut_i64_sqrt_cipolla	(	int64_t	n,
		int64_t	p
	)

Compute the square root of a quadratic residue mod a prime.

If n is not a residue or p is not a prime, the value returned may not be useful but the function will terminate.

Parameters

[in]	n	a quadratic residue mod p
[in]	p	a prime

Returns: r so that r^2 = n mod p

◆ nut_i64_sqrt_mod()

int64_t nut_i64_sqrt_mod	(	int64_t	n,
		int64_t	p
	)

Compute the square root of a quadratic residue mod a prime.

If n is not a residue or p is not a prime, this function is not guaranteed to terminate. If your use case does not guarantee this, call nut_u64_is_prime_dmr and nut_i64_jacobi beforehand. uses shortcuts for primes that are 3, 5, or 7 mod 8, otherwise uses Shanks's algorithm unless p-1 is divisible by a sufficiently high power of 2 so Cipolla's algorithm will be faster, in which case it is used. Only the Shank's branch can fail to terminate, although other branches give useless results if the preconditions are not met.

Parameters

[in]	n	a quadratic residue mod p
[in]	p	a prime

Returns: r so that r^2 = n mod p

◆ nut_i32_fastmod_init()

uint64_t nut_i32_fastmod_init ( uint32_t pd )

Compute a constant to use to do modular division faster.

Parameters

[in] pd absolute value of divisor

Returns: constant c for use with nut_i32_fastmod

◆ nut_u32_fastmod_init()

uint64_t nut_u32_fastmod_init ( uint32_t d )

Compute a constant to use to do modular division faster.

Parameters

[in] d divisor

Returns: constant c for use with nut_u32_fastmod

◆ nut_i64_fastmod_init()

uint128_t nut_i64_fastmod_init ( uint64_t pd )

Compute a constant to use to do modular division faster.

Parameters

[in] pd absolute value of divisor

Returns: constant c for use with nut_i64_fastmod

◆ nut_u64_fastmod_init()

uint128_t nut_u64_fastmod_init ( uint64_t d )

Compute a constant to use to do modular division faster.

Parameters

[in] d divisor

Returns: constant c for use with nut_u64_fastmod

◆ nut_i32_fastmod_trunc()

int32_t nut_i32_fastmod_trunc	(	int32_t	n,
		uint32_t	pd,
		uint64_t	c
	)

Compute n mod d, choosing the smallest signed remainder.

Parameters

[in]	n	dividend
[in]	pd	absolute value of divisor
[in]	c	constant from `nut_i32_fastmod_init`

Returns: n mod pd

◆ nut_i32_fastmod_floor()

int32_t nut_i32_fastmod_floor	(	int32_t	n,
		uint32_t	pd,
		uint64_t	c
	)

Compute n mod d, choosing the euclidean remainder.

Parameters

[in]	n	dividend
[in]	pd	absolute value of divisor
[in]	c	constant from `nut_i32_fastmod_init`

Returns: n mod pd

◆ nut_u32_fastmod()

uint32_t nut_u32_fastmod	(	uint32_t	n,
		uint32_t	d,
		uint64_t	c
	)

Compute n mod d faster using a precomputed constant.

Parameters

[in]	n	dividend
[in]	d	divisor
[in]	c	constant from `nut_u32_fastmod_init`

Returns: n mod d

◆ nut_i64_fastmod_trunc()

int64_t nut_i64_fastmod_trunc	(	int64_t	n,
		uint64_t	pd,
		uint128_t	c
	)

Compute n mod d, choosing the smallest signed remainder.

Parameters

[in]	n	dividend
[in]	pd	absolute value of divisor
[in]	c	constant from `nut_i64_fastmod_init`

Returns: n mod pd

◆ nut_i64_fastmod_floor()

int64_t nut_i64_fastmod_floor	(	int64_t	n,
		uint64_t	pd,
		uint128_t	c
	)

Compute n mod d, choosing the euclidean remainder.

Parameters

[in]	n	dividend
[in]	pd	absolute value of divisor
[in]	c	constant from `nut_i64_fastmod_init`

Returns: n mod pd

◆ nut_u64_fastmod()

uint64_t nut_u64_fastmod	(	uint64_t	n,
		uint64_t	d,
		uint128_t	c
	)

Compute n mod d faster using a precomputed constant.

Parameters

[in]	n	dividend
[in]	d	divisor
[in]	c	constant from `nut_u64_fastmod_init`

Returns: n mod d

Detailed Description

LICENSE

DESCRIPTION

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ NUT_ATTR_ACCESS

◆ NUT_ATTR_NO_SAN

◆ NUT_ATTR_CONST

◆ NUT_ATTR_PURE

◆ NUT_ATTR_NODISCARD

◆ NUT_ATTR_NONNULL

◆ NUT_ATTR_RETURNS_NONNULL

◆ NUT_ATTR_MALLOC

◆ NUT_ATTR_ARTIFICIAL

Typedef Documentation

◆ int128_t

◆ uint128_t

Function Documentation

◆ nut_u64_pow()

◆ nut_u128_pow()

◆ nut_u64_powmod()

◆ nut_u64_binom()

◆ nut_u64_binom_next()

◆ nut_u64_prand()

◆ nut_u64_rand()

◆ nut_i64_egcd()

◆ nut_i64_modinv()

◆ nut_u64_modinv_2t()

◆ nut_i64_mod()

◆ nut_i64_crt()

◆ nut_i128_crt()

◆ nut_i64_lcm()

◆ nut_u64_binom_next_mod_2t()

◆ nut_i64_jacobi()

◆ nut_u64_make_jacobi_tbl()

◆ nut_u64_jacobi_tbl_get()

◆ nut_i64_rand_nr_mod()

◆ nut_i64_sqrt_shanks()

◆ nut_i64_sqrt_cipolla()

◆ nut_i64_sqrt_mod()

◆ nut_i32_fastmod_init()

◆ nut_u32_fastmod_init()

◆ nut_i64_fastmod_init()

◆ nut_u64_fastmod_init()

◆ nut_i32_fastmod_trunc()

◆ nut_i32_fastmod_floor()

◆ nut_u32_fastmod()

◆ nut_i64_fastmod_trunc()

◆ nut_i64_fastmod_floor()

◆ nut_u64_fastmod()