mpn_sec_div_r

[Niels Möller]

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.