# 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