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