Fast rational function reconstruction

Let F be a field and let f and g be polynomials in F(t) satisfying degf > degg. Recall that on input of f and g the extended Euclidean algorithm computes a sequence of polynomials (si,ti,ri) satisfying sif + tig = ri. Thus for i with gcd(ti,f) = 1, we obtain rational functions ri/ti2 F(t) satisfying ri/ti g (mod f). In this paper we modify the fast extended Euclidean al- gorithm to compute the smallest ri/ti, that is, an ri/ti min- imizing degri + degti. This means that in an output sen- sitive modular algorithm when we are recovering rational functions in F(t) from their images modulo f(t) where f(t) is increasing in degree, we can recover them as soon as the degree of f is large enough and we can do this fast. We have implemented our modified fast Euclidean algo- rithm for F = Zp, p a word sized prime, in Java. Our fast algorithm beats the ordinary Euclidean algorithm around degree 200. This has application to polynomial gcd compu- tation and linear algebra over Zp(t).