qsieve_knuth_schroeppel qs_inf

Return the Knuth-Schroeppel multiplier for the \(n\), integer to be factored based upon the Knuth-Schroeppel function.

qsieve_primes_init qs_inf

Compute the factor base prime along with there inverse for \(kn\), where \(k\) is Knuth-Schroeppel multiplier and \(n\) is the integer to be factored. It also computes the square root of \(kn\) modulo factor base primes.

qsieve_primes_increment qs_inf delta

It increase the number of factor base primes by amount 'delta' and calculate inverse of those primes along with the square root of \(kn\) modulo those primes.

qsieve_init_A0 qs_inf

First it chooses the possible range of factor of \(A _0\), based on the number of bits in optimal value of \(A _0\). It tries to select range such that we have plenty of primes to choose from as well as number of factor in \(A _0\) are sufficient. For input of size less than 130 bit, this selection method doesn't work therefore we randomly generate 2 or 3-subset of all the factor base prime as the factor of \(A _0\). Otherwise, if we have to select \(s\) factor for \(A _0\), we generate \(s - 1\)-subset from odd indices of the possible range of factor and then search last factor using binary search from the even indices of possible range of factor such that value of \(A _0\) is close to it's optimal value.

qsieve_next_A0 qs_inf

Find next candidate for \(A _0\) as follows: generate next lexicographic \(s - 1\)-subset from the odd indices of possible range of factor base and choose the last factor from even indices using binary search so that value \(A _0\) is close to it's optimal value.

qsieve_init_poly_first qs_inf

Initializes the value of \(A = q _0 * A _0\), where \(q _0\) is non-factor base prime. precompute the data necessary for generating different \(B\) value using grey code formula. Combine the data calculated for the factor of \(A _0\) along with the parameter \(q _0\) to obtain data as for factor of \(A\). It also calculates the sieve offset for all the factor base prime, for first polynomial.

qsieve_init_poly_next qs_inf

Generate next polynomial or next \(B\) value for particular \(A\) and also updates the sieve offsets for all the factor base prime, for this \(B\) value.

qsieve_compute_C qs_inf

Given \(A\) and \(B\), calculate \(C = (B ^2 - A) / N\).

qsieve_do_sieving qs_inf sieve

First initialize the sieve array to zero, then for each \(p \in\) factor base, add \(\log_2(p)\) to the locations \(\operatorname{soln1} _p + i * p\) and \(\operatorname{soln2} _p + i * p\) for \(i = 0, 1, 2,\dots\), where \(\operatorname{soln1} _p\) and \(\operatorname{soln2} _p\) are the sieve offsets calculated for \(p\).

qsieve_do_sieving2 qs_inf

Perform the same task as above but instead of sieving over whole array at once divide the array in blocks and then sieve over each block for all the primes in factor base.

qsieve_evaluate_candidate qs_inf i sieve

For location \(i\) in sieve array value at which, is greater than sieve threshold, check the value of \(Q(x)\) at position \(i\) for smoothness. If value is found to be smooth then store it for later processing, else check the residue for the partial if it is found to be partial then store it for late processing.

qsieve_evaluate_sieve qs_inf sieve

Scan the sieve array for location at, which accumulated value is greater than sieve threshold.

qsieve_collect_relations qs_inf sieve

Call for initialization of polynomial, sieving, and scanning of sieve for all the possible polynomials for particular hypercube i.e. \(A\).

qsieve_write_to_file qs_inf prime Y

Write a relation to the file. Format is as follows, first write large prime, in case of full relation it is 1, then write exponent of small primes, then write number of factor followed by offset of factor in factor base and their exponent and at last value of \(Q(x)\) for particular relation. each relation is written in new line.

qsieve_get_table_entry qs_inf prime

Return the pointer to the location of 'prime' is hash table if it exist, else create and entry for it in hash table and return pointer to that.

qsieve_add_to_hashtable qs_inf prime

Add 'prime' to the hast table.

qsieve_parse_relation qs_inf str

Given a string representation of relation from the file, parse it to obtain all the parameters of relation.

qsieve_merge_relation qs_inf a b

Given two partial relation having same large prime, merge them to obtain a full relation.

qsieve_compare_relation a b

Compare two relation based on, first large prime, then number of factor and then offsets of factor in factor base.

qsieve_remove_duplicates rel_list num_relations

Remove duplicate from given list of relations by sorting relations in the list.

qsieve_process_relation qs_inf

After we have accumulated required number of relations, first process the file by reading all the relations, removes singleton. Then merge all the possible partial to obtain full relations.

qsieve_factor factors n

Factor \(n\) using the quadratic sieve method. It is required that \(n\) is not a prime and not a perfect power. There is no guarantee that the factors found will be prime, or distinct.