fmpz.h

Macros converting between an fmpz that holds a pointer and the mpz_ptr itself. PTR_TO_COEFF shifts the pointer right by two bits and sets the tag bits 01; this relies on mpz_structs being aligned to at least four bytes. COEFF_TO_PTR must only be applied to values for which COEFF_IS_MPZ is true.

Initialises f to zero. This only stores a zero word and allocates nothing.

Initialises f to zero with space for limbs limbs. If limbs is zero, this is fmpz_init; otherwise an mpz is attached and grown to limbs limbs, so that f is temporarily not in canonical form (its value is 0 in an mpz) until the first assignment. Only useful to avoid reallocations when the final size is known.

Releases the memory used by f. A large value gives its mpz back to the memory manager (see Memory management); a small value needs no work.

Initialise f and set it to g.

Sets f to g.

Swaps f and g by exchanging the two words; no limbs are copied.

Set f to 0 and 1. A large value of f is released.

Set f to val, and fmpz_neg_ui to -val.

Set f to h 2^{\mathtt{FLINT\_BITS}} + l, respectively to its negative, where h and l are the unsigned words hi and lo.

Set r to the integer whose two's complement representation with 2\mathtt{FLINT\_BITS} (respectively 3\mathtt{FLINT\_BITS}) bits is hi, lo (respectively hi, mid, lo), the most significant word first. These convert the results of double-word signed arithmetic such as smul_ppmm.

Set out to the integer with the n \ge 1 limbs in[0], ..., in[n-1], least significant first: interpreted as an unsigned integer, or as a two's complement integer of n \mathtt{FLINT\_BITS} bits.

Write the n \ge 1 limbs of in to out, least significant first. The unsigned version requires 0 \le in < 2^{n \mathtt{FLINT\_BITS}}; the signed version writes in modulo 2^{n \mathtt{FLINT\_BITS}}, which is its two's complement representation if it fits in n \mathtt{FLINT\_BITS} bits.

Sets z to the integer with the n limbs src, negated if negative is

1. Requires n \ge 2 and src[n-1] nonzero, so that the value does not fit inline; use fmpz_set_ui and fmpz_neg_ui for one limb, or fmpz_set_ui_array in general.

Return f as an slong, respectively an ulong. The result is unspecified if f does not fit (use fmpz_fits_si and fmpz_abs_fits_ui to check); currently fmpz_get_ui returns the low limb of |f|, so a negative f is not reduced modulo 2^{\mathtt{FLINT\_BITS}}.

Sets *hi and *low to the high and low limbs of f, for 0 \le f < 2^{2\mathtt{FLINT\_BITS}}.

Sets *hi and *lo to the two limbs of x modulo 2^{2\mathtt{FLINT\_BITS}}, its two's complement representation if x fits in 2\mathtt{FLINT\_BITS} bits.

Returns f \bmod n in [0, n) for the modulus n of mod, for any f.

Returns f as a double, rounded towards zero if it is not exactly representable. The result is undefined if |f| exceeds the range of double; use fmpz_get_d_2exp for large values.

Sets f to c rounded towards zero. The result is undefined if c is infinite or a NaN.

Returns a double d with 0.5 \le |d| < 1 and sets *exp to e such that d 2^e approximates f; d is f 2^{-e} truncated to 53 bits. For f = 0 it returns 0 and sets *exp to 0.

Sets f to d 2^{\mathit{exp}} rounded towards zero, so that 0.75 \cdot 2^0 gives 0.

Convert between fmpz_t and an initialised GMP mpz_t, copying the value. Declared only if gmp.h is included before the FLINT headers.

Convert between fmpz_t and GMP's mpf_t; fmpz_set_mpf truncates a fractional value towards zero. Declared only if gmp.h is included first.

Sets the MPFR number x to f, rounded in the direction rnd to the precision of x. Declared only if mpfr.h is included before the FLINT headers.

Allocates an array with flint_malloc, stores the limbs of |n_{in}| in it, sets *n to it and returns the number of limbs (at least 1). The caller frees the array with flint_free. For n_{in} = 0 the array has one limb, which is 0.

flint_mpz_init_set_readonly sets the uninitialised mpz_t z to the value of f, sharing the limbs of f if it is large; z must not be modified, f must not change while z is in use, and z is released with flint_mpz_clear_readonly.

fmpz_init_set_readonly sets the uninitialised fmpz_t f to the value of z, sharing the limbs of z if the value is large; f must not be modified, z must not change while f is in use, and f is released with fmpz_clear_readonly.

Returns the representation of f in base b, 2 \le b \le 62, with a leading minus sign if f < 0. If str is NULL, the string is allocated with flint_malloc and must be freed with flint_free; otherwise it is written to str, which must have room for fmpz_sizeinbase(f, b) + 2 characters.

Sets f to the integer written in base b, 2 \le b \le 62, in the null-terminated string str, and returns 0. White space before and after the number and a minus sign are accepted. Returns -1 if the string is not a valid integer, in which case f is undefined.

Print x in decimal to file or to stdout, with a minus sign if negative and no newline. Return the number of characters written, or a nonpositive value on error.

Read a decimal integer (optional white space and minus sign, then digits) from file or from stdin into f. Return a positive value on success and 0 on failure, following mpz_inp_str.

Write x to, respectively read it from, a stream in GMP's portable binary format: four bytes holding the signed number of bytes, then the bytes of |x|, most significant first. Files are interchangeable with mpz_out_raw and mpz_inp_raw. Return the number of bytes written or read, and 0 on error.

Set f to a uniformly random integer with exactly bits bits (its top bit set), nonnegative for the unsigned version and with a random sign otherwise. For bits = 0 the result is 0.

Set f to a random integer whose absolute value has a random number of bits between 0 and bits, nonnegative for the unsigned version. The values are biased towards sparse binary representations, 0, 1 and COEFF_MAX, which exercise special cases in tests.

As fmpz_randtest, but never 0. Requires bits \ge 1.

Sets f to a uniformly random integer in [0, m) for m > 0, and in (m, 0] for m < 0.

Sets f to a uniformly random integer in [1, m). Requires m \ge 2.

Set f to a random integer in [0, m), respectively (-m/2, m/2], for m > 0, with an increased probability of values near the ends of the range (and near zero for the signed version).

Sets f to a random prime with exactly bits \ge 2 bits: the next prime after a random integer of that size, retried until it has the right size, so the distribution is not exactly uniform over primes. If proved is nonzero the result is proved prime, otherwise it is a probable prime as in fmpz_nextprime.

Returns -1, 0 or 1 according to the sign of f.

Return whether f = 0, f = 1 and f = \pm 1.

Return whether f is even, respectively odd.

Return 1 if f = g and 0 otherwise.

Return a negative value, zero or a positive value according to whether f < g, f = g or f > g.

Compare |f| with |g|, respectively with |2g|, returning a negative value, zero or a positive value.

Return the number of bits, respectively limbs, of |f|; both are 0 for f = 0.

Returns the number of digits of |f| in base b, 2 \le b \le 62, and 1 for f = 0. Unlike GMP's mpz_sizeinbase, the result is exact for all bases.

Returns the exponent of the largest power of 2 dividing x (the number of trailing zero bits), and 0 for x = 0.

Return whether |f| fits in an ulong, respectively whether f fits in an slong.

For x \ne 0 and 1 \le bits \le \mathtt{FLINT\_BITS}, return a mantissa m with exactly bits bits and set *exp to e such that m 2^e \le |x| (lower bound, m is |x| truncated), respectively m 2^e \ge |x| (upper bound, m is |x| rounded up, which may increase e by one if the rounding carries).

Returns an approximation of \log x for x > 0, with a relative error of a few units in the last place of a double.

Return \lfloor \log_b x \rfloor and \lceil \log_b x \rceil, computed exactly. Require x \ge 1 and b \ge 2.

Set f_1 to -f_2, respectively |f_2|.

Set f to g + h, respectively g - h (with x in place of h).

Set f to g h (with x in place of h). Two small operands are multiplied inline; large ones go to flint_mpn_mul or flint_mpn_sqr, which switch from basecase code through Karatsuba and GMP's Toom–Cook algorithms to FFT multiplication (Multiplying integers).

Sets f to g h_1 h_2.

Set f to f + g h, respectively f - g h (with x in place of h), without a temporary for the product when the operands are small.

Set f to ab + cd, respectively ab - cd.

Set f to g 2^{\mathit{exp}}, respectively 2^{\mathit{exp}}. fmpz_mul_2exp assumes that \mathit{exp} + \mathtt{FLINT\_BITS} does not overflow an ulong.

Set f to g h / 2^{\mathit{exp}} (with x in place of h), rounded towards zero.

Set f to g^{\mathit{exp}}, respectively x to b^e, with 0^0 = 1.

Sets a to b^e with 0^0 = 1 and returns 1. For |b| \ge 2 and an exponent e that does not fit in an slong (the result would not fit in memory), returns 0 and leaves a unchanged. Throws an exception if e < 0.

Set f to \lfloor \sqrt g \rfloor and r to g - f^2, for g \ge 0. Throw an exception if g < 0. In fmpz_sqrtrem, f and r must be distinct objects.

If a is a perfect square, sets s to \sqrt a \ge 0 and returns 1; otherwise returns 0 and leaves s undefined. Faster than fmpz_is_square followed by fmpz_sqrt.

Returns whether f is a perfect square (f \ge 0).

Sets r to the n-th root of f rounded towards zero and returns 1 if it is exact and 0 otherwise. Requires n \ge 1, and f \ge 0 if n is even; otherwise an exception is raised.

If f = r^k for some k \ge 2, sets root to r and returns k; otherwise returns 0. Negative f are allowed (then k is odd). The exponent is not necessarily the largest one: 2^{120} currently gives k = 2, and -2^{120} gives k = 3. By convention 0 and 1 give k = 2 and -1 gives k = 1.

Set f to the quotient q of g by h, rounded towards zero, -\infty and +\infty respectively, and s to the remainder g - qh. The remainder has the sign of g (tdiv), of h (fdiv) or of -h (cdiv), and |s| < |h|. Throw an exception if h = 0.

Sets q to a/b rounded to the nearest integer, ties to even, and r to a - qb, so that |r| \le |b|/2. Throws an exception if b = 0.

Set f to the quotient of g by h, rounded towards zero, -\infty and +\infty respectively. Throw an exception if h = 0.

Sets f to the remainder of fmpz_fdiv_qr, which has the sign of h. Throws an exception if h = 0.

Set f to the quotient, respectively the remainder, of g by 2^{\mathit{exp}} with the rounding of the prefix. fmpz_fdiv_q_2exp is an arithmetic right shift and fmpz_fdiv_r_2exp the reduction to [0, 2^{\mathit{exp}}).

Return the absolute value of the remainder of g by h with the rounding of the prefix. fmpz_fdiv_ui thus returns g \bmod h in [0, h). Throw an exception if h = 0.

Set f to g / h, assuming that h divides g. This is not checked; if the division is not exact the result is meaningless. Faster than the other divisions, since it uses 2-adic (Hensel) division. Throw an exception if h = 0.

Sets f to g / (h_1 h_2), assuming that h_1 h_2 divides g. Throws an exception if h_1 or h_2 is 0.

Checked exact division: if h divides g, set q = g/h and return 1; otherwise set q = 0 and return 0. Division by zero counts as exact only for g = 0 (with q = 0).

Older name for fmpz_div.

Returns whether g divides f, that is, whether f = qg for an integer q. Every g divides 0, and 0 divides only 0.

Return whether g divides f. As for fmpz_divisible, every g divides 0, and 0 divides only 0.

Compute a precomputed inverse of f \ne 0, respectively release it.

As fmpz_fdiv_qr and fmpz_fdiv_r, using the precomputed inverse inv of h, for many divisions by the same multi-limb h.

Sets f to g \bmod h in [0, |h|). Requires h \ne 0, which is not checked (a zero divisor crashes with a division by zero).

Sets f to g \bmod h in [0, h) and also returns it. Throws an exception if h = 0.

Sets f to the symmetric remainder y \equiv g \pmod h with -|h|/2 < y \le |h|/2. Requires h \ne 0 (not checked).

Sets f to the symmetric remainder y \equiv x \pmod m with -m/2 < y \le m/2, for 0 \le x < m (not checked).

Sets r to -a modulo mod for 0 \le a < mod (not checked).

If \gcd(g, h) = 1, sets f to the inverse of g modulo h in [0, |h|) and returns 1; otherwise returns 0 and f is undefined. Every g is invertible modulo h = \pm 1, with inverse 0. Throws an exception if h = 0.

Set f to g^e \bmod m in [0, m), for m \ge 1 (an exception is raised otherwise). For m = 1 the result is 0, and otherwise g^0 = 1. fmpz_powm accepts e < 0 if g is invertible modulo m and raises an exception if it is not.

For a prime p: if a is a square modulo p, sets b to a square root and returns 1, otherwise sets b to 0 and returns 0. Primality of p is not checked; for composite p a return value of 1 means nothing.

Sets rop to op with all factors f removed and returns their number, the largest v with f^v \mid op. Requires f \ge 2 (an exception is raised otherwise). For op = 0, rop is set to 0 and 0 is returned.

Returns the Jacobi symbol \left(\frac{a}{p}\right) for any a and odd p > 0. The conditions on p are not checked.

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

Sets the outputs so that the solutions x \in [0, n) of ax \equiv b \pmod n are exactly \mathit{xstart} + i \cdot \mathit{xstride} for 0 \le i < \mathit{xlength}; there are none if xlength is 0. Requires n > 0; the outputs must be distinct objects.

Sets rop to the inverse of op modulo 2^N. Throws an exception if op is even.

Hensel division: sets rop to the unique q \in [0, 2^N) with qb \equiv a \pmod{2^N}. Throws an exception if b is even.

If op is an odd square modulo 2^N (for N \ge 3: op \equiv 1 \pmod 8), set rop to a square root y, respectively an inverse square root (\mathit{op}\, y^2 \equiv 1), modulo 2^N, and return 1; otherwise return 0. The root returned is the one congruent to 1 modulo 4, reduced modulo 2^N. Even op is not supported (0 is returned).

Set f to \gcd(g, h) \ge 0, with \gcd(0, 0) = 0.

Sets f to \gcd(a, b, c) \ge 0. Faster than two calls to fmpz_gcd when one operand is small or the GCD of the two shortest operands is 1.

Sets f to the least common multiple of g and h, which is nonnegative, and 0 if g or h is 0.

Sets d = \gcd(f, g) \ge 0 and cofactors a, b with af + bg = d. The outputs must be distinct objects.

As fmpz_xgcd, but the cofactors are the canonical Bézout coefficients defined on GCD, LCM and Bézout coefficients: the minimal ones, with fixed choices in the degenerate cases. Usually faster than fmpz_xgcd.

For 0 \le f < g, sets d = \gcd(f, g) and a to a cofactor in [0, g) with af \equiv d \pmod g, so that a = f^{-1} \bmod g if d = 1. For f = 0 it sets d = g and a = 0. The outputs must be distinct objects.

Runs the extended Euclidean algorithm on r_2 > r_1 > 0 until the remainder drops to at most L, with Lehmer's acceleration. On return r_2 and r_1 are the last two remainders and co2, co1 the corresponding cofactors, with co2\cdot r_1 - co1\cdot r_2 = \pm r_{2,\mathrm{orig}}. No aliasing is allowed.

Set out to the unique x \equiv r_1 \pmod{m_1}, x \equiv r_2 \pmod {m_2} in [0, m_1 m_2) if sign is 0, and in (-m_1 m_2/2, m_1 m_2/2] otherwise. Require coprime m_1, m_2 > 0, -m_1 \le r_1 < m_1 and 0 \le r_2 < m_2; only the coprimality is checked (by fmpz_CRT, which raises an exception).

As fmpz_CRT_ui with precomputed data: m2inv = n_preinvert_limb(m2), m1m2 = m_1 m_2 and c = m_1^{-1} \bmod m_2. Used when the same pair of moduli recurs.

Initialise C for the \mathit{num\_primes} \ge 1 pairwise coprime nonzero word-size moduli in primes (they need not be prime; the array is copied), respectively release it. fmpz_comb_init2 precomputes only what the operations in flags (FMPZ_COMB_MOD, FMPZ_COMB_CRT or both) need.

Allocate, respectively free, scratch space for calls with C. A scratch space is not thread-safe; each thread needs its own.

Sets out[i] to in modulo the i-th modulus of C, in [0, m_i), for any in.

Sets output to the integer congruent to residues[i] \in [0, m_i) modulo each modulus of comb, in [0, M) if sign is 0 and in (-M/2, M/2] otherwise, where M is the product of the moduli.

One-shot versions of fmpz_multi_mod_ui and fmpz_multi_CRT_ui that do not need an fmpz_comb_t. If prod is not NULL, the CRT version also sets it to the product of the moduli.

Initialise CRT, respectively release P.

Prepares CRT for the \mathit{len} \ge 1 moduli (signs are ignored) and returns 1 if they are usable: one nonzero modulus, or several that are pairwise coprime and none of which is 0 or \pm 1. Otherwise returns 0, and later reconstructions give undefined results.

Sets output to the integer congruent to inputs[i] modulo the i-th modulus of P, for any values inputs[i]: in [0, M) if sign is 0 and in (-M/2, M/2] otherwise, where M is the product of the absolute values of the moduli.

As fmpz_multi_CRT_precomp, with the result in outputs[0] and the other entries of the array, which must have P->localsize initialised entries, used as scratch space.

Combines fmpz_multi_CRT_precompute and fmpz_multi_CRT_precomp and returns the value of the former.

Initialise, respectively release, P.

Prepares P for reduction modulo the r \ge 1 moduli f (signs are ignored) and returns 1 if none of them is zero, 0 otherwise.

Set outputs[i] to input modulo the i-th modulus m_i of P: in [0, |m_i|) if sign is 0 and in (-|m_i|/2, |m_i|/2] otherwise. The underscore version takes scratch space tmp of P->localsize initialised entries.

Returns bit i of f (0 or 1).

Set, clear and complement bit i of f.

Sets r to the one's complement -f - 1 of f.

Set r to the bitwise and, inclusive or and exclusive or of a and b.

Returns the number of one bits of c \ge 0. For negative c (infinitely many one bits) it returns 0.

Pack an integer into, respectively extract it from, a field of bits bits starting at bit shift <\mathtt{FLINT\_BITS} of the limb array arr. Signed fields are stored in two's complement with a borrow that propagates to the next field. These are the building blocks of Kronecker substitution in fmpz_poly.

Sets f to n!, from a table for n \le 20 (on 64-bit machines) and with GMP's mpz_fac_ui otherwise.

Sets res to the binomial coefficient \binom{n}{k}, which is 0 for k > n.

Set r to the rising factorial x(x+1)\cdots(x+n-1), with value 1 for n = 0. Any sign of x is allowed.

Sets r to (x+a)(x+a+1)\cdots(x+b-1) for x \ge 0 and b > a, by binary splitting with several factors packed per word at the leaves.

Sets f to the Fibonacci number F_n.

Sets res to the primorial n\#, the product of the primes p \le n, by a balanced product tree over word-size factors.

Sets res to Euler's totient \varphi(n), the number of 1 \le k \le n with \gcd(k, n) = 1, and to 0 for n \le 0. Word-size n use n_euler_phi; larger n are factored. The function fmpz_factor_euler_phi of fmpz_factor takes a factorisation.

Returns the Möbius function \mu(|n|): 0 if n has a square factor > 1, otherwise (-1)^k for k prime factors; \mu(0) = 0. Factors n unless it fits in a word.

Sets res to \sigma_k(|n|), the sum of the k-th powers of the positive divisors of n, and to 0 for n = 0. Factors n.

Returns 0 if p is composite and 1 if it is a probable prime. For p up to about 81 bits on 64-bit machines (where n_is_prime and n_ll_is_prime decide primality), the answer is exact; otherwise the test is trial division, a perfect square check and the Baillie–PSW test (a base-2 strong probable prime test and a Lucas test), for which no composite that passes is known.

Returns 1 if n is prime and 0 otherwise, with a proof.

Returns 1 if n is a strong probable prime to base a, and 0 otherwise.

Returns 1 if n is a Lucas probable prime with parameters chosen by Selfridge's method A [PSW1980], and 0 otherwise. No prime is declared composite.

Returns 1 if n passes the Baillie–PSW test [PSW1980] (a strong probable prime test to base 2 and a Lucas test), and 0 otherwise. No composite passing it is known, and no prime fails it.

Returns 0 if n is composite and 1 if it is proved prime by the pseudosquare test (Theorem 2.7 of [LukPatWil1996]), using a table of pseudosquares up to 2^{64}. Returns -1 if n is too large (above about 94 bits).

The n - 1 test of Pocklington and the n + 1 test of Morrison for odd n (non-square for Morrison), given the num_pm1 (num_pp1) primes pm1 (pp1) dividing n - 1 (n + 1). Return 0 if n is composite. Otherwise they set F to the factored part of n \mp 1 and R to (n \mp 1)/F and return 1, which proves that every prime factor of n is \equiv 1 \pmod F (respectively \equiv \pm 1). This proves n prime if F \ge \sqrt n (respectively F > \sqrt n + 1).

Trial factor n - 1 (respectively n + 1) by the primes up to about limit and store the primes found in the array, setting its length. The array needs room for \log_2 n + 2 entries. A limit of a small multiple of (\log n)^3 / 10 is a reasonable choice for the tests above.

Set V_m and V_{m+1} modulo n for the Lucas sequence V_0 = 2, V_1 = A, V_j = A V_{j-1} - V_{j-2} (respectively A V_{j-1} - B V_{j-2}), by the doubling formulas. No aliasing is allowed.

For the Lucas sequence U_0 = 0, U_1 = 1, U_j = A U_{j-1} - B U_{j-2} modulo n: given U_m, U_{m+1} (and U_n, U_{n+1}), compute U_{2m}, U_{2m+1}, respectively U_{m+n}, U_{m+n+1}, respectively U_{km}, U_{km+1}. Each output may alias the corresponding input (U_{2m} with U_m, and so on); no other aliasing is allowed.

Given V_m and V_{m+1} modulo n, sets U_m and U_{m+1}, where Dinv is the inverse of D = A^2 - 4B modulo n. U_m may alias V_m and U_{m+1} may alias V_{m+1}.

Sets res to the smallest prime greater than n (2 for n \le 1). If proved is nonzero, the result is proved prime with fmpz_is_prime; otherwise it is a probable prime (n_nextprime for small n, GMP's mpz_nextprime, a Baillie–PSW test, otherwise).

Lenstra's algorithm: for 0 < r < s < n with \gcd(r, s) = 1, finds a divisor of n congruent to r modulo s if there is one, sets fac to it and returns 1; otherwise returns 0. Efficient when s^3 > n, as in the final step of the n \pm 1 primality tests.

Take an initialised mpz with at least MPZ_MIN_ALLOC limbs from the memory manager, respectively give back the mpz that the large value f points to. The mpz given back must still have at least MPZ_MIN_ALLOC limbs.

Free the mpzs cached by the current thread (the second also frees the cache array). Called by flint_cleanup; they do nothing in builds configured with --enable-reentrant.

Ensure that f holds an mpz and return it. _fmpz_promote does not preserve the value of a small f (the mpz holds garbage); it is used before overwriting f. _fmpz_promote_val preserves the value. Either may leave f temporarily non-canonical.

_fmpz_demote releases the mpz of f, if any, and sets f to 0 (any value then fits inline). _fmpz_demote_val moves the value of f back inline if it fits, restoring canonical form.

Out-of-line parts of the inline assignment functions: set an initialised (_init_ versions: an uninitialised) f to a value that does not fit inline. Calling them with a value that fits leaves f non-canonical.

Helpers of the read-only conversions: wrap the mpz z in a fresh mpz slot of f, respectively release the mpz of such an f when its value is small.

Returns whether x is in canonical form: inline, or an mpz whose value does not fit inline and whose top limb is nonzero. Used in tests.

Sets r to a modulo m \ne 0 in a range selected by sign: for sign < 0 the remainder of truncating division (|r| < |m|, sign of a), for 0 that of floor division (|r| < |m|, sign of m), and for sign > 0 the symmetric remainder -|m| < 2r \le |m|. The scratch variable t must not alias any other argument.

Divides x \ne 0 in place by the largest power of f > 1 dividing it and returns the exponent. finv must be n_precompute_inverse(f) if f is small and 0 otherwise. x and f must be distinct.