Cofactor canonicalisation of mpn_gcdext

Niels Möller nisse at
Mon May 2 20:05:43 CEST 2011

Torbjorn Granlund <tg at> 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?


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