Cofactor canonicalisation of mpn_gcdext
nisse at lysator.liu.se
Mon May 2 12:21:49 CEST 2011
Torbjorn Granlund <tg at gmplib.org> writes:
> 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?
Maybe. If so, a similar note should be added to mpn_gcd (it also used to
destroy inputs plus an extra limb, right)?
> 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?
That was my first thought too, but it's not so easy, I'm afraid. Say U <
V, and we first divide
V = Q U + V'
Then call mpn_gcdext on U, V', so that
G = S' U + T' V' (where T' is implicit)
Then the needed cofactor is
S = S' - Q T' (an addition, since S' and T' have opposite signs)
So we'd still have to compute the implicit T' (which can be expected to
be of size roughly sn - qn),
So I think this mehod might make sense for the case that V is much larger
than U, but for U and V of roughly the same size, I think it will be
faster to compute S directly, using Q to initiale the cofactor variable.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel