Schönhage's algorithm for fast integer GCD

[Niels Möller]

Kevin Ryde <user42@zip.com.au> writes:

> Yes, if I remember rightly a divide and conquer along those lines is
> the way to go.  I forget quite what the complexity comes out as, it
> might be a rather modestly sub-quadratic exponent, and biggish
> overheads.

The algorithm is supposed to have an asymptotic running time of
O(log(n) M(n)), where M(n) is the time to multiply two n-bit numbers
(whatever that is for the numbers of interest).

/Niels