Schönhage's algorithm for fast integer GCD

Niels Möller nisse@lysator.liu.se
14 Jun 2003 10:00:56 +0200


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