Side-channel silent division

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   If we can arrange for a loop which does a full quotent limb, and applies
>   it using mpn_submul_1 followed by an mpn_add_cnd_n per quotient3B, would
>   that be faster or otherwise preferable to your loop with two submul_1
>   per quotient limb?
>   
> "Quotient3B"?  Is "3B" a typo for " limb"?  :-)

Yup! I blame the terminal and its escape sequences.

> A loop around submul_1 + mpn_addcnd_n would get a smaller n^2 term on
> almost all machines, I think.

I was been thinking of the following algorithm (I think I wrote about
the mod variant a while ago).

Say we want to divide by an n-limb number D, and for simplicity, assume
that D is normalised.

First precompute the inverse v = floor(B^{n+1} / D) (one limb and a
bit), and the corresponding n-limb remainder, r, so that

  B^{n+1} = v * D + R

Now, if U is an n+2 limb number, we can reduce it as

  u_{n+1}^B{n+1} + U' = u_{n+1} v D + u_{n+1} R + U' 

Here, the product u_{n+1} * v is two limbs + a bit to be added to the
quotient, and U' + u_{n+1} r is n+1 limbs and a carry out. We can
iterate this to reduce u from n+m limbs to n + 1 (we then need something
different for the final quotient limb).

For side-channel silent division, we'd need to store away the q limbs
and add them up in a single loop after the main loop. The carry from
addmul_1 would have to be handled inside the loop, not sure how to best do
that.

For general schoolbook division, it's nice that we use addmul_1 rather
than submul_1, and when addmul_2 is available it might make sense to
extend to two quotient limbs at a time.

Ah, and one more thing: For the applications which are going to need
side-channel silent division, I think the common case is a mod operation
with invariant divisor. In this case, I think the above idea (but
without all the quotient book-keeping) is a pretty good alternative to
schoolbook.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.