Integer (opaque pointer)

newFmpz

Create a new Fmpz.

withFmpz x f

Apply f to x.

withNewFmpz f

Apply f to a new Fmpz.

Data structure containing the CFmpz pointer

Data structure containing CFmpzFactor pointer

_fmpz_new_mpz

initialises a new mpz_t and returns a pointer to it. This is only used internally.

_fmpz_cleanup_mpz_content

this function does nothing in the reentrant version of fmpz.

_fmpz_cleanup

this function does nothing in the reentrant version of fmpz.

_fmpz_promote f

if \(f\) doesn't represent an mpz_t, initialise one and associate it to \(f\).

_fmpz_promote_val f

if \(f\) doesn't represent an mpz_t, initialise one and associate it to \(f\), but preserve the value of \(f\).

This function is for internal use. The resulting fmpz will be backed by an mpz_t that can be passed to GMP, but the fmpz will be in an inconsistent state with respect to the other Flint fmpz functions such as fmpz_is_zero, etc.

_fmpz_demote f

if \(f\) represents an mpz_t clear it and make \(f\) just represent an slong.

_fmpz_demote_val f

if \(f\) represents an mpz_t and its value will fit in an slong, preserve the value in \(f\) which we make to represent an slong, and clear the mpz_t.

fmpz_init f

A small fmpz_t is initialised, i.e.just a slong. The value is set to zero.

fmpz_init2 f limbs

Initialises the given fmpz_t to have space for the given number of limbs.

If limbs is zero then a small fmpz_t is allocated, i.e.just a slong. The value is also set to zero. It is not necessary to call this function except to save time. A call to fmpz_init will do just fine.

fmpz_clear f

Clears the given fmpz_t, releasing any memory associated with it, either back to the stack or the OS, depending on whether the reentrant or non-reentrant version of FLINT is built.

fmpz_init_set_si f g

Initialises \(f\) and sets it to the value of \(g\).

fmpz_randbits f state bits

Generates a random signed integer whose absolute value has precisely the given number of bits.

fmpz_randtest f state bits

Generates a random signed integer whose absolute value has a number of bits which is random from \(0\) up to bits inclusive.

fmpz_randtest_unsigned f state bits

Generates a random unsigned integer whose value has a number of bits which is random from \(0\) up to bits inclusive.

fmpz_randtest_not_zero f state bits

As per fmpz_randtest, but the result will not be \(0\). If bits is set to \(0\), an exception will result.

fmpz_randm f state m

Generates a random integer in the range \(0\) to \(m - 1\) inclusive.

fmpz_randtest_mod f state m

Generates a random integer in the range \(0\) to \(m - 1\) inclusive, with an increased probability of generating values close to the endpoints.

fmpz_randtest_mod_signed f state m

Generates a random integer in the range \((-m/2, m/2]\), with an increased probability of generating values close to the endpoints or close to zero.

fmpz_randprime f state bits proved

Generates a random prime number with the given number of bits.

The generation is performed by choosing a random number and then finding the next largest prime, and therefore does not quite give a uniform distribution over the set of primes with that many bits.

Random number generation is performed using the standard Flint random number generator, which is not suitable for cryptographic use.

If proved is nonzero, then the integer returned is guaranteed to actually be prime.

fmpz_get_si f

Returns \(f\) as a slong. The result is undefined if \(f\) does not fit into a slong.

fmpz_get_ui f

Returns \(f\) as an ulong. The result is undefined if \(f\) does not fit into an ulong or is negative.

fmpz_get_uiui hi low f

If \(f\) consists of two limbs, then *hi and *low are set to the high and low limbs, otherwise *low is set to the low limb and *hi is set to \(0\).

fmpz_get_nmod f mod

Returns \(f \mod n\).

fmpz_get_d f

Returns \(f\) as a double, rounding down towards zero if \(f\) cannot be represented exactly. The outcome is undefined if \(f\) is too large to fit in the normal range of a double.

fmpz_set_mpf f x

Sets \(f\) to the mpf_t \(x\), rounding down towards zero if the value of \(x\) is fractional.

fmpz_get_mpf x f

Sets the value of the mpf_t \(x\) to the value of \(f\).

fmpz_get_mpfr x f rnd

Sets the value of \(x\) from \(f\), rounded toward the given direction rnd.

fmpz_get_d_2exp exp f

Returns \(f\) as a normalized double along with a \(2\)-exponent exp, i.e.if \(r\) is the return value then \(f = r 2^{exp}\), to within 1 ULP.

fmpz_get_mpz x f

Sets the mpz_t \(x\) to the same value as \(f\).

fmpz_get_mpn n n_in

Sets the mp_ptr \(n\) to the same value as \(n_{in}\). Returned integer is number of limbs allocated to \(n\), minimum number of limbs required to hold the value stored in \(n_{in}\).

fmpz_get_str str b f

Returns the representation of \(f\) in base \(b\), which can vary between \(2\) and \(62\), inclusive.

If str is NULL, the result string is allocated by the function. Otherwise, it is up to the caller to ensure that the allocated block of memory is sufficiently large.

fmpz_set_si f val

Sets \(f\) to the given slong value.

fmpz_set_ui f val

Sets \(f\) to the given ulong value.

fmpz_set_d f c

Sets \(f\) to the double \(c\), rounding down towards zero if the value of \(c\) is fractional. The outcome is undefined if \(c\) is infinite, not-a-number, or subnormal.

fmpz_set_d_2exp f d exp

Sets \(f\) to the nearest integer to \(d 2^{exp}\).

fmpz_neg_ui f val

Sets \(f\) to the given ulong value, and then negates \(f\).

fmpz_set_uiui f hi lo

Sets \(f\) to lo, plus hi shifted to the left by FLINT_BITS.

fmpz_neg_uiui f hi lo

Sets \(f\) to lo, plus hi shifted to the left by FLINT_BITS, and then negates \(f\).

fmpz_set_signed_uiui f hi lo

Sets \(f\) to lo, plus hi shifted to the left by FLINT_BITS, interpreted as a signed two's complement integer with 2 * FLINT_BITS bits.

fmpz_set_signed_uiuiui f hi mid lo

Sets \(f\) to lo, plus mid shifted to the left by FLINT_BITS, plus hi shifted to the left by 2*FLINT_BITS bits, interpreted as a signed two's complement integer with 3 * FLINT_BITS bits.

fmpz_set_ui_array out in n

Sets out to the nonnegative integer in[0] + in[1]*X + ... + in[n - 1]*X^(n - 1) where X = 2^FLINT_BITS. It is assumed that n > 0.

fmpz_set_signed_ui_array out in n

Sets out to the integer represented in in[0], ..., in[n - 1] as a signed two's complement integer with n * FLINT_BITS bits. It is assumed that n > 0. The function operates as a call to fmpz_set_ui_array followed by a symmetric remainder modulo \(2^(n*FLINT\_BITS)\).

fmpz_get_ui_array out n in

Assuming that the nonnegative integer in can be represented in the form out[0] + out[1]*X + ... + out[n - 1]*X^(n - 1), where \(X = 2^{FLINT\_BITS}\), sets the corresponding elements of out so that this is true. It is assumed that n > 0.

fmpz_get_signed_ui_array out n in

Retrieves the value of \(in\) modulo \(2^{n * FLINT\_BITS}\) and puts the \(n\) words of the result in out[0], ..., out[n-1]. This will give a signed two's complement representation of \(in\) (assuming \(in\) doesn't overflow the array).

fmpz_get_signed_uiui hi lo in

Retrieves the value of \(in\) modulo \(2^{2 * FLINT\_BITS}\) and puts the high and low words into *hi and *lo respectively.

fmpz_set_mpz f x

Sets \(f\) to the given mpz_t value.

fmpz_set_str f str b

Sets \(f\) to the value given in the null-terminated string str, in base \(b\). The base \(b\) can vary between \(2\) and \(62\), inclusive. Returns \(0\) if the string contains a valid input and \(-1\) otherwise.

fmpz_set_ui_smod f x m

Sets \(f\) to the signed remainder \(y \equiv x \bmod m\) satisfying \(-m/2 < y \leq m/2\), given \(x\) which is assumed to satisfy \(0 \leq x < m\).

flint_mpz_init_set_readonly z f

Sets the uninitialised mpz_t \(z\) to the value of the readonly fmpz_t \(f\).

Note that it is assumed that \(f\) does not change during the lifetime of \(z\).

The integer \(z\) has to be cleared by a call to flint_mpz_clear_readonly.

The suggested use of the two functions is as follows:

fmpz_t f;
...
{
    mpz_t z;

    flint_mpz_init_set_readonly(z, f);
    foo(..., z);
    flint_mpz_clear_readonly(z);
}

This provides a convenient function for user code, only requiring to work with the types fmpz_t and mpz_t.

In critical code, the following approach may be favourable:

fmpz_t f;
...
{
    __mpz_struct *z;

    z = _fmpz_promote_val(f);
    foo(..., z);
    _fmpz_demote_val(f);
}

flint_mpz_clear_readonly z

Clears the readonly mpz_t \(z\).

fmpz_init_set_readonly f z

Sets the uninitialised fmpz_t \(f\) to a readonly version of the integer \(z\).

Note that the value of \(z\) is assumed to remain constant throughout the lifetime of \(f\).

The fmpz_t \(f\) has to be cleared by calling the function fmpz_clear_readonly.

The suggested use of the two functions is as follows:

mpz_t z;
...
{
    fmpz_t f;

    fmpz_init_set_readonly(f, z);
    foo(..., f);
    fmpz_clear_readonly(f);
}

fmpz_clear_readonly f

Clears the readonly fmpz_t \(f\).

fmpz_read f

Reads a multiprecision integer from stdin. The format is an optional minus sign, followed by one or more digits. The first digit should be non-zero unless it is the only digit.

In case of success, returns a positive number. In case of failure, returns a non-positive number.

This convention is adopted in light of the return values of scanf from the standard library and mpz_inp_str from MPIR.

fmpz_fread file f

Reads a multiprecision integer from the stream file. The format is an optional minus sign, followed by one or more digits. The first digit should be non-zero unless it is the only digit.

In case of success, returns a positive number. In case of failure, returns a non-positive number.

This convention is adopted in light of the return values of scanf from the standard library and mpz_inp_str from MPIR.

fmpz_inp_raw x fin

Reads a multiprecision integer from the stream file. The format is raw binary format write by fmpz_out_raw.

In case of success, return a positive number, indicating number of bytes read. In case of failure 0.

This function calls the mpz_inp_raw function in library gmp. So that it can read the raw data written by mpz_inp_raw directly.

fmpz_print x

Prints the value \(x\) to stdout, without a carriage return(CR). The value is printed as either \(0\), the decimal digits of a positive integer, or a minus sign followed by the digits of a negative integer.

In case of success, returns a positive number. In case of failure, returns a non-positive number.

This convention is adopted in light of the return values of flint_printf from the standard library and mpz_out_str from MPIR.

fmpz_fprint file x

Prints the value \(x\) to file, without a carriage return(CR). The value is printed as either \(0\), the decimal digits of a positive integer, or a minus sign followed by the digits of a negative integer.

In case of success, returns a positive number. In case of failure, returns a non-positive number.

This convention is adopted in light of the return values of flint_printf from the standard library and mpz_out_str from MPIR.

fmpz_out_raw fout x

Writes the value \(x\) to file. The value is written in raw binary format. The integer is written in portable format, with 4 bytes of size information, and that many bytes of limbs. Both the size and the limbs are written in decreasing significance order (i.e., in big-endian).

The output can be read with fmpz_inp_raw.

In case of success, return a positive number, indicating number of bytes written. In case of failure, return 0.

The output of this can also be read by mpz_inp_raw from GMP >= 2, Since this function calls the mpz_inp_raw function in library gmp.

fmpz_sizeinbase f b

Returns the size of the absolute value of \(f\) in base \(b\), measured in numbers of digits. The base \(b\) can be between \(2\) and \(62\), inclusive.

fmpz_bits f

Returns the number of bits required to store the absolute value of \(f\). If \(f\) is \(0\) then \(0\) is returned.

fmpz_size f

Returns the number of limbs required to store the absolute value of \(f\). If \(f\) is zero then \(0\) is returned.

fmpz_sgn f

Returns \(-1\) if the sign of \(f\) is negative, \(+1\) if it is positive, otherwise returns \(0\).

fmpz_val2 f

Returns the exponent of the largest power of two dividing \(f\), or equivalently the number of trailing zeros in the binary expansion of \(f\). If \(f\) is zero then \(0\) is returned.

fmpz_swap f g

Efficiently swaps \(f\) and \(g\). No data is copied.

fmpz_set f g

Sets \(f\) to the same value as \(g\).

fmpz_zero f

Sets \(f\) to zero.

fmpz_one f

Sets \(f\) to one.

fmpz_abs_fits_ui f

Returns whether the absolute value of \(f\) fits into an ulong.

fmpz_fits_si f

Returns whether the value of \(f\) fits into a slong.

fmpz_setbit f i

Sets bit index \(i\) of \(f\).

fmpz_tstbit f i

Test bit index \(i\) of \(f\) and return \(0\) or \(1\), accordingly.

fmpz_abs_lbound_ui_2exp exp x bits

For nonzero \(x\), returns a mantissa \(m\) with exactly bits bits and sets exp to an exponent \(e\), such that \(|x| \ge m 2^e\). The number of bits must be between 1 and FLINT_BITS inclusive. The mantissa is guaranteed to be correctly rounded.

fmpz_abs_ubound_ui_2exp exp x bits

For nonzero \(x\), returns a mantissa \(m\) with exactly bits bits and sets exp to an exponent \(e\), such that \(|x| \le m 2^e\). The number of bits must be between 1 and FLINT_BITS inclusive. The mantissa is either correctly rounded or one unit too large (possibly meaning that the exponent is one too large, if the mantissa is a power of two).

fmpz_cmp_si f g

Returns a negative value if \(f < g\), positive value if \(g < f\), otherwise returns \(0\).

fmpz_cmpabs f g

Returns a negative value if \(\lvert f\rvert < \lvert g\rvert\), positive value if \(\lvert g\rvert < \lvert f \rvert\), otherwise returns \(0\).

fmpz_cmp2abs f g

Returns a negative value if \(\lvert f\rvert < \lvert 2g\rvert\), positive value if \(\lvert 2g\rvert < \lvert f \rvert\), otherwise returns \(0\).

fmpz_equal_si f g

Returns \(1\) if \(f\) is equal to \(g\), otherwise returns \(0\).

fmpz_is_zero f

Returns \(1\) if \(f\) is \(0\), otherwise returns \(0\).

fmpz_is_one f

Returns \(1\) if \(f\) is equal to one, otherwise returns \(0\).

fmpz_is_pm1 f

Returns \(1\) if \(f\) is equal to one or minus one, otherwise returns \(0\).

fmpz_is_even f

Returns whether the integer \(f\) is even.

fmpz_is_odd f

Returns whether the integer \(f\) is odd.

fmpz_neg f1 f2

Sets \(f_1\) to \(-f_2\).

fmpz_abs f1 f2

Sets \(f_1\) to the absolute value of \(f_2\).

fmpz_add f g h

Sets \(f\) to \(g + h\).

fmpz_sub f g h

Sets \(f\) to \(g - h\).

fmpz_mul f g h

Sets \(f\) to \(g \times h\).

fmpz_mul2_uiui f g x y

Sets \(f\) to \(g \times x \times y\) where \(x\) and \(y\) are of type ulong.

fmpz_mul_2exp f g e

Sets \(f\) to \(g \times 2^e\).

Note: Assumes that e + FLINT_BITS does not overflow.

fmpz_one_2exp f e

Sets \(f\) to \(2^e\).

fmpz_addmul f g h

Sets \(f\) to \(f + g \times h\).

fmpz_submul f g h

Sets \(f\) to \(f - g \times h\).

fmpz_fmma f a b c d

Sets \(f\) to \(a \times b + c \times d\).

fmpz_fmms f a b c d

Sets \(f\) to \(a \times b - c \times d\).

fmpz_tdiv_r_2exp s g exp

Sets \(f\) to the quotient of \(g\) by \(h\) and/or \(s\) to the remainder. For the 2exp functions, g = 2^exp. \(If :math:`h\) is \(0\) an exception is raised.

Rounding is made in the following way:

• fdiv rounds the quotient via floor rounding.
• cdiv rounds the quotient via ceil rounding.
• tdiv rounds the quotient via truncation, i.e. rounding towards zero.
• ndiv rounds the quotient such that the remainder has the smallest absolute value. In case of ties, it rounds the quotient towards zero.

fmpz_tdiv_ui g h

Returns the absolute value remainder of \(g\) divided by \(h\), following the convention of rounding as seen above. If \(h\) is zero an exception is raised.

fmpz_divexact_ui f g h

Sets \(f\) to the quotient of \(g\) and \(h\), assuming that the division is exact, i.e.(g) is a multiple of \(h\). If \(h\) is \(0\) an exception is raised.

fmpz_divexact2_uiui f g x y

Sets \(f\) to the quotient of \(g\) and \(h = x \times y\), assuming that the division is exact, i.e.(g) is a multiple of \(h\). If \(x\) or \(y\) is \(0\) an exception is raised.

fmpz_divisible_si f g

Returns \(1\) if there is an integer \(q\) with \(f = q g\) and \(0\) if there is none.

fmpz_divides q g h

Returns \(1\) if there is an integer \(q\) with \(f = q g\) and sets \(q\) to the quotient. Otherwise returns \(0\) and sets \(q\) to \(0\).

fmpz_mod f g h

Sets \(f\) to the remainder of \(g\) divided by \(h\) such that the remainder is positive. Assumes that \(h\) is not zero.

fmpz_mod_ui f g h

Sets \(f\) to the remainder of \(g\) divided by \(h\) such that the remainder is positive and also returns this value. Raises an exception if \(h\) is zero.

fmpz_smod f g h

Sets \(f\) to the signed remainder \(y \equiv g \bmod h\) satisfying \(-\lvert h \rvert/2 < y \leq \lvert h\rvert/2\).

fmpz_preinvn_init inv f

Compute a precomputed inverse inv of f for use in the preinvn functions listed below.

fmpz_preinvn_clear inv

Clean up the resources used by a precomputed inverse created with the fmpz_preinvn_init function.

fmpz_fdiv_qr_preinvn f s g h hinv

As per fmpz_fdiv_qr, but takes a precomputed inverse hinv of \(h\) constructed using fmpz_preinvn.

This function will be faster than fmpz_fdiv_qr_preinvn when the number of limbs of \(h\) is at least PREINVN_CUTOFF.

fmpz_pow_ui f g x

Sets \(f\) to \(g^x\). Defines \(0^0 = 1\).

fmpz_pow_fmpz f g x

Sets \(f\) to \(g^x\). Defines \(0^0 = 1\). Return \(1\) for success and \(0\) for failure. The function throws only if \(x\) is negative.

fmpz_powm f g e m

Sets \(f\) to \(g^e \bmod{m}\). If \(e = 0\), sets \(f\) to \(1\).

Assumes that \(m \neq 0\), raises an abort signal otherwise.

fmpz_clog x b

Returns \(\lceil\log_b x\rceil\).

Assumes that \(x \geq 1\) and \(b \geq 2\) and that the return value fits into a signed slong.

fmpz_flog x b

Returns \(\lfloor\log_b x\rfloor\).

Assumes that \(x \geq 1\) and \(b \geq 2\) and that the return value fits into a signed slong.

fmpz_dlog x

Returns a double precision approximation of the natural logarithm of \(x\).

The accuracy depends on the implementation of the floating-point logarithm provided by the C standard library. The result can typically be expected to have a relative error no greater than 1-2 bits.

fmpz_sqrtmod b a p

If \(p\) is prime, set \(b\) to a square root of \(a\) modulo \(p\) if \(a\) is a quadratic residue modulo \(p\) and return \(1\), otherwise return \(0\).

If \(p\) is not prime the return value is with high probability \(0\), indicating that \(p\) is not prime, or \(a\) is not a square modulo \(p\). If \(p\) is not prime and the return value is \(1\), the value of \(b\) is meaningless.

fmpz_sqrt f g

Sets \(f\) to the integer part of the square root of \(g\), where \(g\) is assumed to be non-negative. If \(g\) is negative, an exception is raised.

fmpz_sqrtrem f r g

Sets \(f\) to the integer part of the square root of \(g\), where \(g\) is assumed to be non-negative, and sets \(r\) to the remainder, that is, the difference \(g - f^2\). If \(g\) is negative, an exception is raised. The behaviour is undefined if \(f\) and \(r\) are aliases.

fmpz_is_square f

Returns nonzero if \(f\) is a perfect square and zero otherwise.

fmpz_root r f n

Set \(r\) to the integer part of the \(n\)-th root of \(f\). Requires that \(n > 0\) and that if \(n\) is even then \(f\) be non-negative, otherwise an exception is raised. The function returns \(1\) if the root was exact, otherwise \(0\).

fmpz_is_perfect_power root f

If \(f\) is a perfect power \(r^k\) set root to \(r\) and return \(k\), otherwise return \(0\). Note that \(-1, 0, 1\) are all considered perfect powers. No guarantee is made about \(r\) or \(k\) being the smallest possible value. Negative values of \(f\) are permitted.

fmpz_fac_ui f n

Sets \(f\) to the factorial \(n!\) where \(n\) is an ulong.

fmpz_fib_ui f n

Sets \(f\) to the Fibonacci number \(F_n\) where \(n\) is an ulong.

fmpz_bin_uiui f n k

Sets \(f\) to the binomial coefficient \({n \choose k}\).

_fmpz_rfac_ui r x a b

Sets \(r\) to the rising factorial \((x+a) (x+a+1) (x+a+2) \cdots (x+b-1)\). Assumes \(b > a\).

fmpz_rfac_ui r x k

Sets \(r\) to the rising factorial \(x (x+1) (x+2) \cdots (x+k-1)\).

fmpz_rfac_uiui r x k

Sets \(r\) to the rising factorial \(x (x+1) (x+2) \cdots (x+k-1)\).

fmpz_mul_tdiv_q_2exp f g h exp

Sets \(f\) to the product \(g\) and \(h\) divided by 2^exp, rounding down towards zero.

fmpz_mul_si_tdiv_q_2exp f g x exp

Sets \(f\) to the product \(g\) and \(x\) divided by 2^exp, rounding down towards zero.

fmpz_gcd f g h

Sets \(f\) to the greatest common divisor of \(g\) and \(h\). The result is always positive, even if one of \(g\) and \(h\) is negative.

fmpz_gcd3 f a b c

Sets \(f\) to the greatest common divisor of \(a\), \(b\) and \(c\). This is equivalent to calling fmpz_gcd twice, but may be faster.

fmpz_lcm f g h

Sets \(f\) to the least common multiple of \(g\) and \(h\). The result is always nonnegative, even if one of \(g\) and \(h\) is negative.

fmpz_gcdinv d a f g

Given integers \(f, g\) with \(0 \leq f < g\), computes the greatest common divisor \(d = \gcd(f, g)\) and the modular inverse \(a = f^{-1} \pmod{g}\), whenever \(f \neq 0\).

Assumes that \(d\) and \(a\) are not aliased.

fmpz_xgcd d a b f g

Computes the extended GCD of \(f\) and \(g\), i.e. the values \(a\) and \(b\) such that \(af + bg = d\), where \(d = \gcd(f, g)\). Here \(a\) will be the same as calling fmpz_gcdinv when \(f < g\) (or vice versa for \(b\) when \(g < f\)).

To obtain the canonical solution to Bézout's identity, call fmpz_xgcd_canonical_bezout instead. This is also faster.

Assumes that there is no aliasing among the outputs.

fmpz_xgcd_canonical_bezout d a b f g

Computes the extended GCD \(\mathrm{xgcd}(f, g) = (d, a, b)\) such that the solution is the canonical solution to Bézout's identity. We define the canonical solution to satisfy one of the following if one of the given conditions apply:

\[\begin{aligned} \operatorname{xgcd}(\pm g, g) &= \bigl(|g|, 0, \operatorname{sgn}(g)\bigr)\\ \operatorname{xgcd}(f, 0) &= \bigl(|f|, \operatorname{sgn}(f), 0\bigr)\\ \operatorname{xgcd}(0, g) &= \bigl(|g|, 0, \operatorname{sgn}(g)\bigr)\\ \operatorname{xgcd}(f, \mp 1) &= (1, 0, \mp 1)\\ \operatorname{xgcd}(\mp 1, g) &= (1, \mp 1, 0)\quad g \neq 0, \pm 1\\ \operatorname{xgcd}(\mp 2 d, g) &= \bigl(d, {\textstyle\frac{d - |g|}{\mp 2 d}}, \operatorname{sgn}(g)\bigr)\\ \operatorname{xgcd}(f, \mp 2 d) &= \bigl(d, \operatorname{sgn}(f), {\textstyle\frac{d - |g|}{\mp 2 d}}\bigr). \end{aligned}\]

If the pair \((f, g)\) does not satisfy any of these conditions, the solution \((d, a, b)\) will satisfy the following:

\[`\] \[|a| < \Bigl| \frac{g}{2 d} \Bigr|, \qquad |b| < \Bigl| \frac{f}{2 d} \Bigr|.\]

Assumes that there is no aliasing among the outputs.

fmpz_xgcd_partial co2 co1 r2 r1 L

This function is an implementation of Lehmer extended GCD with early termination, as used in the qfb module. It terminates early when remainders fall below the specified bound. The initial values r1 and r2 are treated as successive remainders in the Euclidean algorithm and are replaced with the last two remainders computed. The values co1 and co2 are the last two cofactors and satisfy the identity co2*r1 - co1*r2 == +/- r2_orig upon termination, where r2_orig is the starting value of r2 supplied, and r1 and r2 are the final values.

Aliasing of inputs is not allowed. Similarly aliasing of inputs and outputs is not allowed.

_fmpz_remove x f finv

Removes all factors \(f\) from \(x\) and returns the number of such.

Assumes that \(x\) is non-zero, that \(f > 1\) and that finv is the precomputed double inverse of \(f\) whenever \(f\) is a small integer and \(0\) otherwise.

Does not support aliasing.

fmpz_remove rop op f

Remove all occurrences of the factor \(f > 1\) from the integer op and sets rop to the resulting integer.

If op is zero, sets rop to op and returns \(0\).

Returns an abort signal if any of the assumptions are violated.

fmpz_invmod f g h

Sets \(f\) to the inverse of \(g\) modulo \(h\). The value of \(h\) may not be \(0\) otherwise an exception results. If the inverse exists the return value will be non-zero, otherwise the return value will be \(0\) and the value of \(f\) undefined. As a special case, we consider any number invertible modulo \(h = \pm 1\), with inverse 0.

fmpz_negmod f g h

Sets \(f\) to \(-g \pmod{h}\), assuming \(g\) is reduced modulo \(h\).

fmpz_jacobi a n

Computes the Jacobi symbol \(\left(\frac{a}{n}\right)\) for any \(a\) and odd positive \(n\).

fmpz_kronecker a n

Computes the Kronecker symbol \(\left(\frac{a}{n}\right)\) for any \(a\) and any \(n\).

fmpz_divides_mod_list xstart xstride xlength a b n

Set \(xstart\), \(xstride\), and \(xlength\) so that the solution set for x modulo \(n\) in \(a x = b mod n\) is exactly \(\{xstart + xstride i | 0 \le i < xlength\}\). This function essentially gives a list of possibilities for the fraction \(a/b\) modulo \(n\). The outputs may not be aliased, and \(n\) should be positive.

fmpz_bit_pack arr shift bits coeff negate borrow

Shifts the given coefficient to the left by shift bits and adds it to the integer in arr in a field of the given number of bits:

shift  bits  --------------

X X X C C C C 0 0 0 0 0 0 0

An optional borrow of \(1\) can be subtracted from coeff before it is packed. If coeff is negative after the borrow, then a borrow will be returned by the function.

The value of shift is assumed to be less than FLINT_BITS. All but the first shift bits of arr are assumed to be zero on entry to the function.

The value of coeff may also be optionally (and notionally) negated before it is used, by setting the negate parameter to \(-1\).

fmpz_bit_unpack coeff arr shift bits negate borrow

A bit field of the given number of bits is extracted from arr, starting after shift bits, and placed into coeff. An optional borrow of \(1\) may be added to the coefficient. If the result is negative, a borrow of \(1\) is returned. Finally, the resulting coeff may be negated by setting the negate parameter to \(-1\).

The value of shift is expected to be less than FLINT_BITS.

fmpz_bit_unpack_unsigned coeff arr shift bits

A bit field of the given number of bits is extracted from arr, starting after shift bits, and placed into coeff.

The value of shift is expected to be less than FLINT_BITS.

fmpz_complement r f

The variable r is set to the ones-complement of f.

fmpz_clrbit f i

Sets the ith bit in f to zero.

fmpz_combit f i

Complements the ith bit in f.

fmpz_and r a b

Sets r to the bit-wise logical and of a and b.

fmpz_or r a b

Sets r to the bit-wise logical (inclusive) or of a and b.

fmpz_xor r a b

Sets r to the bit-wise logical exclusive or of a and b.

fmpz_popcnt a

Returns the number of '1' bits in the given Z (aka Hamming weight or population count). The return value is undefined if the input is negative.

fmpz_CRT_ui out r1 m1 r2 m2 sign

Uses the Chinese Remainder Theorem to compute the unique integer \(0 \le x < M\) (if sign = 0) or \(-M/2 < x \le M/2\) (if sign = 1) congruent to \(r_1\) modulo \(m_1\) and \(r_2\) modulo \(m_2\), where where \(M = m_1 \times m_2\). The result \(x\) is stored in out.

It is assumed that \(m_1\) and \(m_2\) are positive integers greater than \(1\) and coprime.

If sign = 0, it is assumed that \(0 \le r_1 < m_1\) and \(0 \le r_2 < m_2\). Otherwise, it is assumed that \(-m_1 \le r_1 < m_1\) and \(0 \le r_2 < m_2\).

fmpz_CRT out r1 m1 r2 m2 sign

Use the Chinese Remainder Theorem to set out to the unique value \(0 \le x < M\) (if sign = 0) or \(-M/2 < x \le M/2\) (if sign = 1) congruent to \(r_1\) modulo \(m_1\) and \(r_2\) modulo \(m_2\), where where \(M = m_1 \times m_2\).

It is assumed that \(m_1\) and \(m_2\) are positive integers greater than \(1\) and coprime.

If sign = 0, it is assumed that \(0 \le r_1 < m_1\) and \(0 \le r_2 < m_2\). Otherwise, it is assumed that \(-m_1 \le r_1 < m_1\) and \(0 \le r_2 < m_2\).

fmpz_multi_mod_ui out in comb temp

Reduces the multiprecision integer in modulo each of the primes stored in the comb structure. The array out will be filled with the residues modulo these primes. The structure temp is temporary space which must be provided by fmpz_comb_temp_init and cleared by fmpz_comb_temp_clear.

fmpz_multi_CRT_ui output residues comb ctemp sign

This function takes a set of residues modulo the list of primes contained in the comb structure and reconstructs a multiprecision integer modulo the product of the primes which has these residues modulo the corresponding primes.

If \(N\) is the product of all the primes then out is normalised to be in the range \([0, N)\) if sign = 0 and the range \([-(N-1)/2, N/2]\) if sign = 1. The array temp is temporary space which must be provided by fmpz_comb_temp_init and cleared by fmpz_comb_temp_clear.

Data structure containing CFmpzComb pointer

Data structure containing CFmpzCombTemp pointer

fmpz_comb_init comb primes num_primes

Initialises a comb structure for multimodular reduction and recombination. The array primes is assumed to contain num_primes primes each of FLINT_BITS - 1 bits. Modular reductions and recombinations will be done modulo this list of primes. The primes array must not be free'd until the comb structure is no longer required and must be cleared by the user.

fmpz_comb_temp_init temp comb

Creates temporary space to be used by multimodular and CRT functions based on an initialised comb structure.

fmpz_comb_clear comb

Clears the given comb structure, releasing any memory it uses.

fmpz_comb_temp_clear temp

Clears temporary space temp used by multimodular and CRT functions using the given comb structure.

Data structure containing CFmpzMultiCRT pointer

fmpz_multi_CRT_init CRT

Initialize CRT for Chinese remaindering.

fmpz_multi_CRT_precompute CRT moduli len

Configure CRT for repeated Chinese remaindering of moduli. The number of moduli, len, should be positive. A return of 0 indicates that the compilation failed and future calls to fmpz_crt_precomp will leave the output undefined. A return of 1 indicates that the compilation was successful, which occurs if and only if either (1) len == 1 and modulus + 0 is nonzero, or (2) no modulus is \(0,1,-1\) and all moduli are pairwise relatively prime.

fmpz_multi_CRT_precomp output P inputs

Set output to an integer of smallest absolute value that is congruent to values + i modulo the moduli + i in fmpz_crt_precompute.

fmpz_multi_CRT output moduli values len

Perform the same operation as fmpz_multi_CRT_precomp while internally constructing and destroying the precomputed data. All of the remarks in fmpz_multi_CRT_precompute apply.

fmpz_multi_CRT_clear P

Free all space used by CRT.

fmpz_is_strong_probabprime n a

Returns \(1\) if \(n\) is a strong probable prime to base \(a\), otherwise it returns \(0\).

fmpz_is_probabprime_lucas n

Performs a Lucas probable prime test with parameters chosen by Selfridge's method \(A\) as per [BaiWag1980].

Return \(1\) if \(n\) is a Lucas probable prime, otherwise return \(0\). This function declares some composites probably prime, but no primes composite.

fmpz_is_probabprime_BPSW n

Perform a Baillie-PSW probable prime test with parameters chosen by Selfridge's method \(A\) as per [BaiWag1980].

Return \(1\) if \(n\) is a Lucas probable prime, otherwise return \(0\).

There are no known composites passed as prime by this test, though infinitely many probably exist. The test will declare no primes composite.

fmpz_is_probabprime p

Performs some trial division and then some probabilistic primality tests. If \(p\) is definitely composite, the function returns \(0\), otherwise it is declared probably prime, i.e. prime for most practical purposes, and the function returns \(1\). The chance of declaring a composite prime is very small.

Subsequent calls to the same function do not increase the probability of the number being prime.

fmpz_is_prime_pseudosquare n

Return \(0\) is \(n\) is composite. If \(n\) is too large (greater than about \(94\) bits) the function fails silently and returns \(-1\), otherwise, if \(n\) is proven prime by the pseudosquares method, return \(1\).

Tests if \(n\) is a prime according to [Theorem 2.7] [LukPatWil1996].

We first factor \(N\) using trial division up to some limit \(B\). In fact, the number of primes used in the trial factoring is at most FLINT_PSEUDOSQUARES_CUTOFF.

Next we compute \(N/B\) and find the next pseudosquare \(L_p\) above this value, using a static table as per https://oeis.org/A002189/b002189.txt.

As noted in the text, if \(p\) is prime then Step 3 will pass. This test rejects many composites, and so by this time we suspect that \(p\) is prime. If \(N\) is \(3\) or \(7\) modulo \(8\), we are done, and \(N\) is prime.

We now run a probable prime test, for which no known counterexamples are known, to reject any composites. We then proceed to prove \(N\) prime by executing Step 4. In the case that \(N\) is \(1\) modulo \(8\), if Step 4 fails, we extend the number of primes \(p_i\) at Step 3 and hope to find one which passes Step 4. We take the test one past the largest \(p\) for which we have pseudosquares \(L_p\) tabulated, as this already corresponds to the next \(L_p\) which is bigger than \(2^{64}\) and hence larger than any prime we might be testing.

As explained in the text, Condition 4 cannot fail if \(N\) is prime.

The possibility exists that the probable prime test declares a composite prime. However in that case an error is printed, as that would be of independent interest.

fmpz_is_prime_pocklington F R n pm1 num_pm1

Applies the Pocklington primality test. The test computes a product \(F\) of prime powers which divide \(n - 1\).

The function then returns either \(0\) if \(n\) is definitely composite or it returns \(1\) if all factors of \(n\) are \(1 \pmod{F}\). Also in that case, \(R\) is set to \((n - 1)/F\).

N.B: a return value of \(1\) only proves \(n\) prime if \(F \ge \sqrt{n}\).

The function does not compute which primes divide \(n - 1\). Instead, these must be supplied as an array pm1 of length num_pm1. It does not matter how many prime factors are supplied, but the more that are supplied, the larger F will be.

There is a balance between the amount of time spent looking for factors of \(n - 1\) and the usefulness of the output (F may be as low as \(2\) in some cases).

A reasonable heuristic seems to be to choose limit to be some small multiple of \(\log^3(n)/10\) (e.g. \(1, 2, 5\) or \(10\)) depending on how long one is prepared to wait, then to trial factor up to the limit. (See _fmpz_nm1_trial_factors.)

Requires \(n\) to be odd.

_fmpz_nm1_trial_factors n pm1 num_pm1 limit

Trial factors \(n - 1\) up to the given limit (approximately) and stores the factors in an array pm1 whose length is written out to num_pm1.

One can use \(\log(n) + 2\) as a bound on the number of factors which might be produced (and hence on the length of the array that needs to be supplied).

fmpz_is_prime_morrison F R n pp1 num_pp1

Applies the Morrison \(p + 1\) primality test. The test computes a product \(F\) of primes which divide \(n + 1\).

The function then returns either \(0\) if \(n\) is definitely composite or it returns \(1\) if all factors of \(n\) are \(\pm 1 \pmod{F}\). Also in that case, \(R\) is set to \((n + 1)/F\).

N.B: a return value of \(1\) only proves \(n\) prime if \(F > \sqrt{n} + 1\).

The function does not compute which primes divide \(n + 1\). Instead, these must be supplied as an array pp1 of length num_pp1. It does not matter how many prime factors are supplied, but the more that are supplied, the larger \(F\) will be.

There is a balance between the amount of time spent looking for factors of \(n + 1\) and the usefulness of the output (F may be as low as \(2\) in some cases).

A reasonable heuristic seems to be to choose limit to be some small multiple of \(\log^3(n)/10\) (e.g. \(1, 2, 5\) or \(10\)) depending on how long one is prepared to wait, then to trial factor up to the limit. (See _fmpz_np1_trial_factors.)

Requires \(n\) to be odd and non-square.

_fmpz_np1_trial_factors n pp1 num_pp1 limit

Trial factors \(n + 1\) up to the given limit (approximately) and stores the factors in an array pp1 whose length is written out to num_pp1.

One can use \(\log(n) + 2\) as a bound on the number of factors which might be produced (and hence on the length of the array that needs to be supplied).

fmpz_is_prime n

Attempts to prove \(n\) prime. If \(n\) is proven prime, the function returns \(1\). If \(n\) is definitely composite, the function returns \(0\).

This function calls n_is_prime for \(n\) that fits in a single word. For \(n\) larger than one word, it tests divisibility by a few small primes and whether \(n\) is a perfect square to rule out trivial composites. For \(n\) up to about 81 bits, it then uses a strong probable prime test (Miller-Rabin test) with the first 13 primes as witnesses. This has been shown to prove primality [SorWeb2016].

For larger \(n\), it does a single base-2 strong probable prime test to eliminate most composite numbers. If \(n\) passes, it does a combination of Pocklington, Morrison and Brillhart, Lehmer, Selfridge tests. If any of these tests fails to give a proof, it falls back to performing an APRCL test.

The APRCL test could theoretically fail to prove that \(n\) is prime or composite. In that case, the program aborts. This is not expected to occur in practice.

fmpz_lucas_chain Vm Vm1 A m n

Given \(V_0 = 2\), \(V_1 = A\) compute \(V_m, V_{m + 1} \pmod{n}\) from the recurrences \(V_j = AV_{j - 1} - V_{j - 2} \pmod{n}\).

This is computed efficiently using \(V_{2j} = V_j^2 - 2 \pmod{n}\) and \(V_{2j + 1} = V_jV_{j + 1} - A \pmod{n}\).

No aliasing is permitted.

fmpz_lucas_chain_full Vm Vm1 A B m n

Given \(V_0 = 2\), \(V_1 = A\) compute \(V_m, V_{m + 1} \pmod{n}\) from the recurrences \(V_j = AV_{j - 1} - BV_{j - 2} \pmod{n}\).

This is computed efficiently using double and add formulas.

No aliasing is permitted.

fmpz_lucas_chain_double U2m U2m1 Um Um1 A B n

Given \(U_m, U_{m + 1} \pmod{n}\) compute \(U_{2m}, U_{2m + 1} \pmod{n}\).

Aliasing of \(U_{2m}\) and \(U_m\) and aliasing of \(U_{2m + 1}\) and \(U_{m + 1}\) is permitted. No other aliasing is allowed.

fmpz_lucas_chain_add Umn Umn1 Um Um1 Un Un1 A B n

Given \(U_m, U_{m + 1} \pmod{n}\) and \(U_n, U_{n + 1} \pmod{n}\) compute \(U_{m + n}, U_{m + n + 1} \pmod{n}\).

Aliasing of \(U_{m + n}\) with \(U_m\) or \(U_n\) and aliasing of \(U_{m + n + 1}\) with \(U_{m + 1}\) or \(U_{n + 1}\) is permitted. No other aliasing is allowed.

fmpz_lucas_chain_mul Ukm Ukm1 Um Um1 A B k n

Given \(U_m, U_{m + 1} \pmod{n}\) compute \(U_{km}, U_{km + 1} \pmod{n}\).

Aliasing of \(U_{km}\) and \(U_m\) and aliasing of \(U_{km + 1}\) and \(U_{m + 1}\) is permitted. No other aliasing is allowed.

fmpz_lucas_chain_VtoU Um Um1 Vm Vm1 A B Dinv n

Given \(V_m, V_{m + 1} \pmod{n}\) compute \(U_m, U_{m + 1} \pmod{n}\).

Aliasing of \(V_m\) and \(U_m\) and aliasing of \(V_{m + 1}\) and \(U_{m + 1}\) is permitted. No other aliasing is allowed.

fmpz_divisor_in_residue_class_lenstra fac n r s

If there exists a proper divisor of \(n\) which is \(r \pmod{s}\) for \(0 < r < s < n\), this function returns \(1\) and sets fac to such a divisor. Otherwise the function returns \(0\) and the value of fac is undefined.

We require \(\gcd(r, s) = 1\).

This is efficient if \(s^3 > n\).

fmpz_nextprime res n proved

Finds the next prime number larger than \(n\).

If proved is nonzero, then the integer returned is guaranteed to actually be prime. Otherwise if \(n\) fits in FLINT_BITS - 3 bits n_nextprime is called, and if not then the GMP mpz_nextprime function is called. Up to an including GMP 6.1.2 this used Miller-Rabin iterations, and thereafter uses a BPSW test.