qsieve.h

Finds a nontrivial factorisation of n, which must be composite and not a perfect power; the sign of n is multiplied into factors->sign. The bases written to factors (which should be freshly initialised) multiply to |n| with the stored exponents, but they need not be prime: the sieve splits n along the square roots it finds and stops as soon as all parts are probable primes or it runs out of square roots. Use fmpz_factor for a complete factorisation into proven primes.

qsieve_factor with the given tuning parameters instead of those from the table (see qsieve_tune for their meaning). Used for tuning.

Initialise qs_inf for factoring n, with the tuning parameters of the table row for the bit size of n, respectively the given ones. The sieve values are biased so that an entry is over the threshold exactly when its top bit is set, which lets the scan of the sieve test a word at a time.

Frees n, kn, the factor base and the relation store of qs_inf.

Chooses the Knuth–Schroeppel multiplier k for n, among the 29 squarefree numbers from 1 to 47, maximising the expected contribution of the small primes to the sieve: kn \bmod 8 and the primes p (up to ks_primes of them) for which kn is a square modulo p, minus \frac12 \log k [Sil1987]. Stores it in qs_inf->k and returns 0, or returns a small prime factor of n if one is found (2 if n is even).

Extends the factor base to num_primes primes: the multiplier, 2, and the primes p for which kn is a nonzero square modulo p, with their inverses and the square roots of kn modulo p. If a prime dividing n is met, it is stored in small_factor and the extension stops. Returns the factor base.

Compute the initial factor base (of fb_primes primes, plus ks_primes extra primes held in reserve), respectively extend it by delta primes when sieving has to continue with a larger factor base. Return a small prime factor of n if one is found, and 0 otherwise.

Allocate the polynomial data (for s factors of A, the factor base and one qs_poly_s per thread), set up the parameters of the bucket sieve, and free them.

Chooses the number s of prime factors of A and the range of the factor base from which they are taken (primes of about (\log_2 A)/s bits, following msieve), allocates the polynomial data and computes the first A. Returns 0 if no suitable range exists, in which case the factor base must be extended.

Finds the next value of A. If A has s > 3 factors, the first s - 1 are chosen at random among the smallest primes of the allowed range whose index is not divisible by 4 (the number of candidates being adjusted so that the products have about the right size), and the last factor is found by binary search among those with index divisible by 4, so that A is within a factor of two of its optimal value; values of A used before are rejected. With at most 3 factors, the next subset in lexicographic order is used. Returns 0 if no new value is found.

Restart the enumeration of the values of A after a failed linear algebra step, and free the list of the values of A used so far.

For the current A, computes the data for generating the values of B (for each prime q_i \mid A, the term B_i = (A/q_i) \gamma_i with \gamma_i \equiv \sqrt{kn} (A/q_i)^{-1} \pmod{q_i}, and 2 B_i A^{-1} \bmod p for every factor base prime p), the first B and the sieve start positions (\pm \sqrt{kn} - B) A^{-1} \bmod p for every factor base prime.

Moves to the (i+1)-th value of B in Gray code order, updating B and the sieve start positions by adding or subtracting 2 B_\nu and its precomputed multiples.

Sets C = (B^2 - kn)/A for the current polynomial (an exact division).

Copies the current B and sieve start positions to the per-thread data poly.

Sieve the interval for the polynomial poly: initialise the sieve and add the approximate logarithm of p at the positions congruent to either start position modulo p, for every factor base prime p beyond the small primes. The first version sieves the whole array prime by prime; the second works block by block, with the primes below QS_SMALL_BOUND sieved over L1-sized sub-blocks; the third (used unless the sieve is small) adds a bucket sieve for the primes above BLOCK_SIZE: each of them is visited once per polynomial and its hits are appended to a bucket per sub-block, and the buckets are applied to the sub-blocks in turn and kept for qsieve_evaluate_candidate.

Scans the sieve for entries over the threshold, testing a word at a time, and calls qsieve_evaluate_candidate for each. Returns the number of relations found.

Checks whether Q(x) at sieve position i factors over the factor base, apart from at most one large prime below the large prime bound. The small primes are divided out by trial division, the medium primes by checking the sieve start positions, and the large factor base primes are read off the buckets. Full and partial relations are stored with qsieve_add_relation. Returns the number of relations found (0 or 1).

Sieves with all the polynomials for the current A (distributing the values of B over the threads) and returns the number of relations found.

Initialise the store of relations (called by qsieve_init_with_tune), free it (called by qsieve_clear), and discard all relations while keeping the allocations (used when the linear algebra failed to split n and sieving starts again with a larger factor base).

Appends a relation to the store, with large primes prime and prime2 (prime2 = 1 for at most one large prime, both 1 for a full relation), the square root Y, and the small prime exponents and remaining factors taken from poly. The store supports two large primes, but the sieve currently only produces partial relations with one. Called from the sieving threads, so the caller must hold qs_inf->mutex.

Adds the edge prime – prime2 (with prime2 = 1 for a single large prime) to the graph of large primes, incrementing qs_inf->num_cycles if it closes a new independent cycle, as detected by a union-find structure. The caller must hold qs_inf->mutex.

Return the entry of prime in the hash table of large primes, creating it if necessary, and add an occurrence of prime to the table.

Returns a copy of the i-th relation of the store, which the caller must free.

Combines two partial relations with the same large prime \ell into a full relation (the product, with \ell^2 removed from the factorisation and Y adjusted accordingly).

Comparison of relations (by large prime, then number of factors, then the factors), for sorting, and removal of duplicates from a list of relations by sorting it; returns the new length.

Inserts the given full relations as columns of the matrix, recording their factors and Y values for the square root step.

Processes the relations once enough are expected: removes duplicates, combines the partial relations along the independent cycles of the graph of large primes (found from a spanning forest) into full relations, and if there are at least extra_rels more than factor base primes inserts them in the matrix and returns 1. Otherwise lowers the estimate qs_inf->num_cycles by the shortfall and returns 0, so that sieving continues. Returns -1 if a large prime turned out to divide n (stored in qs_inf->small_factor).

Allocate, resize after the factor base was extended, and free the matrix and the data for the square root step.

Light filtering of the sparse matrix: repeatedly deletes the columns that contain a row with a single nonzero entry, then trims the matrix to a few more columns than rows, updating the dimensions.

Montgomery's block Lanczos algorithm over \mathbb{F}_2 with blocks of 64 vectors [Mon1995]: returns an array of ncols words whose bit l in entry i gives the i-th coordinate of the l-th vector of a basis of (part of) the null space of the matrix with columns B, or NULL if the iteration failed (it is then retried with another random start). Adapted from msieve by Jason Papadopoulos.

Returns the entry i of the l-th null space vector (nonzero if it is 1).

For the l-th null space vector, sets Y to the product of the Y values of the relations in it and X to the square root of the product of their factor base primes (from the halved exponent counts), both modulo N = kn. Then X^2 \equiv Y^2 \pmod{kn}, and \gcd(X - Y, n) is a factor of n, nontrivial with probability at least about 1/2 if n is not a prime power.

Inline helpers for matrix columns: append the row entry, exchange two columns, set the weight to zero, and free the column's data.