Fast constant-time gcd computation and modular inversion

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> I've now implemented inverse too.
 
And now I've tried a different variant, using redc for the cofactor
updates. Cofactors are now canonically reduced (which seems unexpectedly
cheap). In the case that m is not normalized, so that 2m fits in n
limbs, one could use a more relaxed range, 0 <= u, v < 2m, and get rid
of a conditional adjustment when doing redc in the loop.

Using redc is a rather good fit, because in each iteration, we shift f,
g *almost* a limb (62 bits on a 64-bit machine), except for the last
iteration where we do less bits. While cofactors are multiplied by
2^{-64} mod m in each iteration. So there's a discrepancy of a few bits
per iteration, which one can handle using very few extra redc calls
outside of the loop (it's O(n^2) work, but with a pretty small
constant).

Speed is rather close to the previous version, but the only needed
precomputation is binvert_limb for the redc. And the calls to
mpn_sec_mul and mpn_sec_div_r are gone.

I also added benchmarking of the existing mpn_sec_invert, for
comparison. This is how it looks now:

invert size 1, ref 0.327 (us), old 2.771 (us), djb 1.087 (us)
invert size 2, ref 0.757 (us), old 5.366 (us), djb 1.571 (us)
invert size 3, ref 1.082 (us), old 8.110 (us), djb 2.336 (us)
[...]
invert size 17, ref 5.106 (us), old 163.962 (us), djb 18.082 (us)
invert size 18, ref 5.189 (us), old 170.565 (us), djb 18.608 (us)
invert size 19, ref 5.715 (us), old 185.143 (us), djb 20.794 (us)

One possible optimization would be to keep cofactors in signed (two's
complement) representation for the first few iterations, when they are
still small and don't need any reduction. And cofactor update for the
very first iteration could be much more efficient.

Regards,
/Niels

-------------- next part --------------
A non-text attachment was scrubbed...
Name: sec-gcd.c
Type: text/x-csrc
Size: 15177 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20220922/69d3bbef/attachment.bin>
-------------- next part --------------

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.