mpz reuse test takes too much time

[Niels Möller]

Marc Glisse <marc.glisse at inria.fr> writes:

> On Sat, 3 Dec 2016, Niels Möller wrote:
>
>> Hmm, you changed the code to not only allow G to be NULL, but allow NULL
>> S too?
>
> That was already the case before my patch. 

Sorry for the confusin, I had forgotten it was your change.

> Since s and t may get swapped depending on the values of a and b, you
> cannot really support t==NULL without supporting s==NULL. You may
> prefer not documenting it though...

I think that's an implementation detail that shouldn't be documented.
Can we just strike it from the docs? (And possibly back it up with an
ASSERT at function entry).

In the case

  mpn_gcdext(G, S, NULL, A, B)

with size(A) < size(B), IIRC we currently handle that by swapping
arguments, calling mpn_gcdext to compute T (even though the caller
didn't need that, and produce S with an multiplication using multiply +
exact division.

That doesn't seem ideal. The alternative would be to do an up-front
division, and call mpn_gcdext with inputs A, B mod A, and some different
postprocessing (I don't have the cofactor stuff in my head at the
moment, it should be somewhere between easy and trivial, and likely
involving the quotient floor (B/A).

One also needs to keep in mind that if |A| < |B|, then typically |T| <
|S| too. Which could influence algorithm choice if the size difference
|is large.

Regards,
/Niels

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