Side-channel silent division
Niels Möller
nisse at lysator.liu.se
Wed Nov 14 10:58:05 CET 2012
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.
More information about the gmp-devel
mailing list