mpn_sec_div_r
Niels Möller
nisse at lysator.liu.se
Mon Dec 3 21:43:13 UTC 2018
tg at gmplib.org (Torbjörn Granlund) writes:
> For invert_limb, we should write some leak-free C code for generating a
> suitable table, I suppose.
You mean leak-free code replacing the table lookup?
For 64-bits, the table used in x86_64/invert_limb is floor(0x7fd00 / x)
for 0x100 <= x < 0x200, 8 significant bits in, 10 significant bits out
(and with a corresponding error range symmetric around zero). This is
based on Algorithm 2 in https://gmplib.org/~tege/division-paper.pdf
We could do a 3 bit in, 4 bit out table lookup as
y = (0x123579cf >> (4*(x >> GMP_NUMB_BITS - 4) & 7))) & 0xf;
and we'd need 2 additioonal Newton iterations to get to the same
accuracy as the table being replaced. Might get a little tight.
We could aim to either get exactly the same values, or to get values
satisfying the paper's error bound
|2^50 - v_0 d_{40}| < 5 2^{39}
As been discussed a while ago, the algorithm in the paper takes care to
make the errors from all iterations but the first non-negative, to only
have to deal with unsigned values. But one might gain a little accuracy
by adding a constant in each iteration, to make the error range more
symmetrical around zero.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list