fmpz_factor.h

Initialise factor (representing 1) and free the memory it uses.

Sets z to the i-th base factor->p + i, for 0 \le i < factor->num.

Set n to the integer represented by factor, including the sign. fmpz_factor_expand calls fmpz_factor_expand_multiexp, which processes the bits of all exponents simultaneously, from the top: at each step it squares the result and multiplies it by the product of the bases whose exponent has that bit set. This is much faster than fmpz_factor_expand_iterative, which raises each base to its power and multiplies the powers one at a time.

Print factor to stdout or to fs as p1^e1 * p2^e2 * ... (omitting exponents equal to 1), preceded by -1 * if the sign is negative. Zero is printed as 0, and 1 and -1 as 1 and -1. Return the number of characters written.

Sets factor to the factorisation of n into primes. The sign of n goes into the sign field; for n = 0 the sign is 0 and there are no factors. Every base is a prime whose primality has been proved.

fmpz_factor for a machine integer n (using n_factor).

Appends the factorisation of n > 1 to factor, without the initial trial division of fmpz_factor: it is meant for integers already known to have no small prime factors. It does not reset factor or set its sign.

Factors n into primes of up to roughly bits bits and possibly one remaining cofactor, which may or may not be prime. Returns 1 if the factorisation is known to be complete; otherwise returns 0, and the last entry (whose exponent may exceed 1) is a composite cofactor that needs further work. Requires bits \ge 1.

fmpz_factor_smooth (which calls this with adaptive = 0). If adaptive is nonzero, the bound bits is lowered whenever the unfactored part gets smaller (after trial division and after each factor found by the elliptic curve method) to the bound that fmpz_factor_no_trial would choose for a number of that size, so that the search stops once finishing the cofactor with the quadratic sieve is expected to be faster. This is used by fmpz_factor_no_trial.

Sets factor to the sign of n and the prime factors of n found by trial division: the power of 2 and the primes flint_primes[i] with start \le i < start + num_primes. Returns 1 if the remaining cofactor is 1 and 0 otherwise; the cofactor itself is not stored. If n fits in a small fmpz (at most \mathtt{FLINT\_BITS} - 2 bits), it is instead factored completely, and 1 is returned.

Sets factor to the sign of n and the prime factors of n among the first num_primes primes, found with the product tree method of flint_mpn_factor_trial_tree. If the cofactor is not 1, it is appended as the last entry (with exponent 1, and not necessarily prime) and 0 is returned; otherwise 1 is returned. Requires 0 \le num_primes \le 3512 (an exception is raised otherwise). If n fits in a small fmpz, it is instead factored completely.

Given a partial factorisation f of an integer (bases need not be prime, coprime or in any order, and may be 1), sets res to a factorisation of the same integer whose bases are pairwise coprime and greater than 1, by the factor refinement algorithm of Bach, Driscoll and Shallit [BDS1993], which uses repeated GCDs. The result need not consist of primes and is not sorted.

Looks for a factor of the composite odd n by Pollard's rho method with Brent's cycle detection [Pol1975; Bre1980], using up to max_tries random polynomials x^2 + a and starting points, each for about max_iters iterations. If a nontrivial factor is found, sets factor to it and returns its number of limbs; otherwise returns 0. The factor need not be prime. For even n it returns 1 and the factor 2. Single-word n are passed to n_factor_pollard_brent. The expected number of iterations to find a prime factor p is O(\sqrt p).

One attempt of fmpz_factor_pollard_brent with the polynomial x^2 + a and the starting point y given by ai and yi (with 1 \le a \le n - 3 and 1 \le y < n). Returns the number of limbs of the factor found, or 0.

Williams' p + 1 method [Wil1982]: looks for a factor of n with a stage 1 bound B1 and a stage 2 bound of at least \mathit{B2\_sqrt}^2, using the Lucas sequence with starting value c > 2. If a factor is found, sets factor to it and returns 1; otherwise returns 0. For even n it returns the factor 2.

Looks for a factor of n = n_in by Lenstra's elliptic curve method [Len1987] with Montgomery's curves and arithmetic [Mon1987], trying up to curves random curves with stage 1 bound B1 and stage 2 bound B2 (B_1 < B_2). Returns 1 if a factor is found in stage 1, 2 if it is found in stage 2, -1 if it is found while setting up a curve, and 0 otherwise; the factor (not necessarily prime) is written to f. Single-word n are passed to n_factor_ecm.

Sets res to Euler's totient \varphi(n) = \prod p_i^{e_i - 1}(p_i - 1) of the integer whose factorisation into distinct primes is fac (the sign is ignored).

Returns the Möbius function \mu(n): 0 if some exponent exceeds 1, and (-1)^k for k distinct primes otherwise.

Sets res to \sigma_k(n) = \sum_{d \mid n} d^k = \prod_i (p_i^{k(e_i + 1)} - 1)/(p_i^k - 1) (the number of divisors for k = 0).

Initialise ecm_inf for moduli of sz limbs, and free it. The stage 2 tables are not allocated by fmpz_factor_ecm_init.

Sets (x : z) to 2 (x_0 : z_0) by Montgomery's doubling formula x = (x_0 + z_0)^2 (x_0 - z_0)^2, z = 4 x_0 z_0 \bigl((x_0 - z_0)^2 + a_{24} \cdot 4 x_0 z_0\bigr) modulo n.

Sets (x : z) to (x_1 : z_1) + (x_2 : z_2) given their difference (x_0 : z_0), by Montgomery's differential addition x = z_0 (x_1 x_2 - z_1 z_2)^2, z = x_0 (x_2 z_1 - x_1 z_2)^2 modulo n (up to a common factor 4).

Sets (x : z) to k (x_0 : z_0) by the Montgomery ladder (one doubling and one differential addition per bit of k).

Sets up a curve and a starting point by Suyama's parametrisation from the parameter \sigma = sig: with u = \sigma^2 - 5 and v = 4\sigma, the point is (u^3 : v^3) and a_{24} = (v - u)^3 (3u + v) / (16 u^3 v); the starting point is stored in ecm_inf->x, ecm_inf->z and a_{24} in ecm_inf->a24. Returns 0 on success; if the inversion needed for a_{24} reveals a factor of n, writes it to f and returns its number of limbs; returns -1 if the curve is degenerate.

Stage 1: multiplies the point by p^{\lfloor \log_p B_1 \rfloor} for each of the num primes p \le B_1 in prime_array, taking the GCD of z with n after each prime. If a nontrivial factor is found, writes it to f and returns its number of limbs; otherwise returns 0.

Stage 2 (the standard continuation, by baby steps and giant steps): with the primorial P \approx \sqrt{B_2}, accumulates the product of X_{mP} Z_j - X_j Z_{mP} over all m and j such that mP \pm j is a prime in (B_1, B_2] (from the tables in ecm_inf), and takes one GCD with n at the end. Returns the number of limbs of the factor found, or 0.

Make room for len factors, and set the number of factors (freeing the bases beyond the new length).

Append the factor p^{\mathit{exp}}. No check is made that p is not already present.

Appends the factors of factor2 to factor1, with their exponents multiplied by exp. The bases must be distinct from those of factor1; they are not merged.

Appends the factorisation of the word n (computed by n_factor); for n = 0 it instead clears factor and sets its sign to 0.

Sets y \gets y^2 + a modulo the shifted modulus n with inverse ninv, the iteration of Pollard's rho method. Requires y, a < n; the result is reduced.

The limb-level implementation of fmpz_factor_pollard_brent_single, in the shifted representation, for \mathit{n\_size} \ge 2 limbs. GCDs are taken once every 100 iterations on the accumulated product of the differences, with backtracking if the product becomes 0 \bmod n. Returns the number of limbs of the (shifted) factor, or 0.