Euclids algorithm (First non-trivial algorithm known GCD(ro, r1= GCD( GCD(r, ro mod ru) Each iteration the total number of bits in the two numbers is reduced by at least 1 ==> number of recursion is O(input) Division, naively, takes o(input 2)operations FFT method for Division: O(input) log(input D)Euclid’s Algorithm (First non-trivial algorithm known) GCD(r0 , r1 ) = GCD(r1 , r0 -r1 ) = GCD(r1 , r0 mod r1 ) Each iteration, the total number of bits in the two numbers is reduced by at least 1 ==> number of recursion is O(|input|) Division, naively, takes O(|input|2 ) operations. FFT method for Division: O(|input| log (|input|))