crt_helpers.h

Fixed-length addition and subtraction#

Internal functions#

Reconstruction kernels#

Through token pasting, the header defines a family of inline functions for each pair (n, m) with n \in \{m, m + 1\} and 1 \le m \le n \le 8:

void _big_mul_n_m(ulong r[], ulong t[], ulong C[], ulong y);
void _big_addmul_n_m(ulong r[], ulong t[], ulong C[], ulong y);
void _reduce_big_sum_n(ulong r[], ulong t[], const ulong * limit);

(for instance _big_mul_3_2 and _reduce_big_sum_3; the trivial cases _big_mul_1_0 and _big_addmul_1_0 exist as well). Here C is an m-limb cofactor and y a limb. _big_mul_n_m sets an n-limb accumulator to Cy, and _big_addmul_n_m adds Cy to it. The accumulator is kept as two interleaved partial sums, r[0..n-1] and t[1..n-1]: the product C_j y of limb j of the cofactor goes into limbs j, j+1 of r for even j and of t for odd j, which keeps the carry chains short and lets the multiplications for all even j and all odd j be issued independently. _reduce_big_sum_n adds the two partial sums and subtracts the n-limb limit until the result is less than it, leaving the reduced value in r.

The kernels are written as straight-line code guarded by compile-time conditions instead of loops: the accumulators stay in registers only if every loop indexing them is completely unrolled, which compilers do not do reliably. For the same reason, a loop over a compile-time number of primes that calls _big_addmul_n_m should be preceded by the macro CRT_UNROLL_PRIMES.

A Chinese remaindering for k primes p_1, \ldots, p_k with product P of n limbs uses them as follows. With the cofactors C_j = P/p_j (of m \le n limbs) and the scaled residues y_j = x_j (P/p_j)^{-1} \bmod p_j, the sum \sum_j C_j y_j is congruent to the solution modulo P and less than \sum_j (P/p_j) p_j = kP. So _big_mul_n_m for the first prime, _big_addmul_n_m for the others and one _reduce_big_sum_n give the solution in [0, P), at the cost of km limb multiplications and fewer than k subtractions of P. See Multimodular reduction and Chinese remaindering for the use of such sums at the leaves of a subproduct tree.