gcdext_1 questions

[Niels Möller]

Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

> If you consider instead the "binary recursive gcd" we defined with
> Damien Stehlé, it removes 1.95 bit per iteration.

I haven't considered this for small sizes (at least not for some years,
I don't remember if I looked into that when I implemented it the
subquadratic algorithm for large integers, where my implementation was
10% slower than the left-to-right algorithm).

The basic iteration would be count_trailing_zeros, shift, table lookup
to get an inverse (and an unlikely newton iteration if there are many
bits), a multiply to get the quotient, and another multiply and shift to
get the remainder.

But it's not clear to me what book-keeping and postprocessing is needed
to get cofactors according to the required conventions.

Regards,
/Niels

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