Fast rational function reconstruction

Let F be a field, f, g E F[z] with rn = deg f > deg g > 0. Our problem is to find a rational f~mction n/d E F(x) where n / d = g mod f: gcd(f, d) = gcd(n, d) = 1 and deg n + deg d < m. If degree bounds N > deg 12 and D > deg d satisfying N + D < m are known, then bhe problem is solved by the Extended Euclidean Algorithm in F[z]. If degree bounds are not known it is still possible to find n/d with high probability. One way is to use rnaximal q~~otient rational f~mction reconstruction. We have implemented the algorithm for F[x] = Zp[x], with p a prime. To speed up the algorithm, our implementation uses Karatsuba's algorithm for multiplication in Z,[z] and a Fast Extended Euclidean Algorithm. As an application, we have modified Brown's modular GCD algorithm to use the maximal quotient algorithm. The modification reduces the number of evaluation points needed by the algorithm.