Direct (interleaved) modular multiplication

[fredrik-johansson]

In most places, we compute A*B mod M by first computing A*B, then reducing mod M. An alternative is to use a multiplication algorithm that works directly mod M. For example, suppose we have polynomials

A = a0 + a1*x + ... + a_(n-1)*x^(n-1)
B = b0 + b1*x + ... + b_(n-1)*x^(n-1)
M = ... + m_n*x^n

Using Horner's rule, we have

AB mod M = a*b0 + x*(a*b1 + x*(a*b2 + ... + x*a*b_(n-1))...)

where each step on the right-hand side is a linear-time operation mod M. This is called "interleaved modular multiplication" or "Blakley modular multiplication" in the literature. In principle I think this does essentially the same work as a classical multiplication followed by a classical division, just interleaved, but it would be interesting to investigate whether it performs better in some circumstances. If nothing else, one advantage is that one can write the output in-place without allocating temporary space for the length-2n product.

Obviously this also works for integers if one takes x to be the radix. One then has a bunch of linear (n+1) by n limb remainders interleaved with addmul_1's. There's some potential for using weakly normalized representations in the intermediate steps.

Something along these lines is surely useful for preconditioned multiplication. Suppose A is invariant: we can then precompute an n by n matrix with the coefficients of A*x^i mod M, i=0,...,n-1 and form AB mod M as a matrix-vector product which should have basically the same cost as a full classical multiplication (without reduction mod M). This should save time in vec_mul/addmul/submul_scalar operations over Z/mZ (multi-word m), finite fields and number fields when one is dealing with basecase-sized moduli. Where else? Note that we already use a form of this trick in poly_compose_mod where it is baked into the Brent-Kung matrix multiplication.

Some variant of Karatsuba multiplication can presumably be done with iterleaved reduction too, but I'm not sure how well that works. (Does preconditioning extend to Karatsuba?)