Cofactor canonicalisation of mpn_gcdext

Torbjorn Granlund tg at
Mon May 2 11:41:23 CEST 2011

nisse at (Niels Möller) writes:

  I've fixed the documentation, and I've changed mpz_gcdext to no longer
  allocate these extra limbs. It seems to still work fine.
Should we perhaps keep a compatibility note in the documentation, since
lean allocation in applications will introduce nasty buffer overrun bugs,
if linked to GMP 4.3 or older?

  When looking at mpz_gcdext, I wonder what's the best strategy for the
  case that U < V and the cofactor corersponding to U is wanted? If I
  understand the currentt mpz_gcdext correctly, it calls with U and V
  swapped, to get the cofactor T, and then computes
    S = (G - T V) / U
  This is a multiply of size un × vn followed by a divexact of (un+vn) /
  I imagine this may be pretty good when vn is much larger than un, since
  it lets mpn_gcdext work with the smaller cofactor T of size un during
  all the reductions, and then there's a single computation at the end
  involving numbers of size vn.
  But when U and V are of about the same size (in particular, when un ==
  vn and U < V), it should be faster to compute the desired cofactor
  directly, which would need some alternative or generalized mpn_gcdext.
  Current mpn_gcdext requires that U >= V, and starts by replacing U by U
  mod V (quotient discarded, since the cofactor S is invariant under this
  reduction). For U < V, one would do an initial division V / U, and in
  this case the quotient is needed for proper initialization of the
  cofactor variable.
Perhaps mpz_gcdext (or some mpn_gcdext2) could perform an initial step
(i.e., division) for this case, to avoid adding overhead to mpn_gcdext?

  I'm afraid any improvment would involve some non-trivial tuning based on
  the relative size of un and vn.
I agree.  :-)


More information about the gmp-devel mailing list