Cofactor canonicalisation of mpn_gcdext

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I suppose I have to make some calculations to completely understand
> this, so maybe what I say is simply dumb.  I'd expect wanted S to be of
> size vn (and the unwanted T to be of size un).

I think you're right. For the case that U < V and the S cofactor is
wanted, with current mpn_gcdext we can choose between the following
methods (and I don't promise this is exhaustive):

1. (G, T) <-- mpn_gcdext(V, U)
   S = (G - T U) / V       // un x vn mul, (un+vn)/vn divexact)
   Return (G, S)

2. Divide: (Q, V') <-- div_qr(V, U)
   (G, S') <-- mpn_gcdext(U, V')
   T' <-- (G - S'U) / V'   // un x un mul, 2un / un divexact
   S <-- S' - Q T'         // (vn - un) x un mul
   Return (G, S)

Method (1) is what's currently implemented, I think. It's not obvious
to me when (or if) method (2) should be more efficient.

And for certain cases (e.g., un == vn), I think both methods can be
beaten by a mpn_gcdext variant which computes (G, T).

BTW, the (G - TU) / V can be done mod B^{vn} for both the multiplication
and the division, using mullo and bdiv_q (IIRC, efficient *division* mod
(2^n±1) won't work).

> Computing T' should therefore not be too costly.

I take it you're focusing on the case of V much larger than U? Or are
you thinking that in general, an additional mul and divexact will not be
very significant compared to the rest of the gcd computation?

Regards,
/Niels


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