Divide-and-conquer gcdext

[Niels Möller]

Current subquadratic gcd and gcdext basically works as follows:

gcd: Like Lehmer, but in each iteration chop off the top 1/3 of the
numbers (rather than the top two limbs) and use hgcd. All the subtle
details are in the implementation of hgcd.

gcdext: Like gcd, but also update the cofactor of interest.

For gcdext, this has the drawback that as the cofactors grow large, they
are updated in smaller and smaller steps (until the numbers being
reduced fall below the threshold).

One consequence is that choosing a good ratio for the split (for gcd,
1/3 seems pretty good) is a lot harder. Another problem, I just
realized, is that it may be a bad way to go about it.

I think the following algorithm, which is more explicitly a divide and
conquer algorithm, will do the cofactor computation more efficiently, as
a tree of fairly balanced multiplications.

gcdext (a, b):  // Inputs of size n

  1. (M, a', b') <-- hgcd(a, b)  // M, a', b' all of size roughly n/2
  2. (g, s') <-- gcdext(a', b')
  3. Compute s from g, s' and M.
  4. Return (g, s)

In step 1, one should use a tweaked hgcd which returns only the matrix
elements needed in step 3. In step 3, one most likely needs also t' = (g
- s' a')/b'. It *might* be more efficient to have gcdext return both
cofactors.

In step 1, one also has the option of not passing all limbs of a and b
to hgcd (which will give us a smaller M but larger a' and b'). The
optimal splitting strategy here should be reasonable easy to tune,
unlike for the current gcdext code.

Asymptotically, if M(n) is the complexity of multiplication, complexity
for gcd is O(M(n) log n). I wonder what the additional work in gcdext
should be, if just O(M(n)) is sufficient, or if it takes O(M(n) log (n))
to compute the cofactor. For the currrent implementation, I'm fairly
sure it takes more than O(M(n)).

What do you think? I'm not aware of anything about this in the
literature (it's obvious that hgcd can be used for an efficient gcdext,
but the details can then be left for the interested reader). But I may
well have missed some important publications. Or important
non-publications...

Regards,
/Niels

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