Die ggT Methode arbeitet nur dann schnell, wenn die Multiplikation schnell ist. Bei der Schulmethode kommt man auf einen quadratischen Aufwand, was in diesem Fall der Probedivision entspricht. Bernstein verwendet die schnelle Fourier Transformation zur Multiplikation. Dann lohnt sich das.-- ThiloHarich 14:03, 24. Aug. 2007 (CEST)