Fast rational function reconstruction

ABSTRACT

Let F be a field and let f and g be polynomials in F[t] satisfying deg f > deg g. Recall that on input of f and g the extended Euclidean algorithm computes a sequence of polynomials (s_i, t_i, r_i) satisfying s_if + t_ig = r_i. Thus for i with gcd(t_i, f) = 1, we obtain rational functions r_i/t_i ∈ F(t) satisfying r_i/t_i ≡ g (mod f).In this paper we modify the fast extended Euclidean algorithm to compute the smallest r_i/t_i, that is, an r_i/t_i minimizing deg r_i + deg t_i. This means that in an output sensitive 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 algorithm for F = Z_p, p a word sized prime, in Java. Our fast algorithm beats the ordinary Euclidean algorithm around degree 200. This has application to polynomial gcd computation and linear algebra over Z_p(t).

REFERENCES

• 1: Richard P. Brent, Fred G. Gustavson, and David Y. Y. Yun. Fast solution of Toeplitz systems of equations and computation of Padé approximants. Journal of Algorithms, 1:259--295, 1980.
• 2: George E. Collins , Mark J. Encarnación, Efficient rational number reconstruction, Journal of Symbolic Computation, v.20 n.3, p.287-297, Sept. 1995 [doi>10.1006/jsco.1995.1051]
• 3: Mark J. Encarnación, Computing GCDs of polynomials over algebraic number fields, Journal of Symbolic Computation, v.20 n.3, p.299-313, Sept. 1995 [doi>10.1006/jsco.1995.1052]
• 4: Joachim Von Zur Gathen , Jurgen Gerhard, Modern Computer Algebra, Cambridge University Press, New York, NY, 2003
• 5: Sara Khodadad. Fast Rational Function Reconstruction. Master's thesis, Simon Fraser University (SFU), Burnaby, BC, Canada, 2005.
• 6: Lars Langemyr , Scott McCallum, The computation of polynomial greatest common divisors over an algebraic number field, Journal of Symbolic Computation, v.8 n.5, p.429-448, Nov. 1989 [doi>10.1016/S0747-7171(89)80053-7]
• 7: Daniel Lichtblau, Half-GCD and fast rational recovery, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.231-236, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073917]
• 8: J. von zur Gathen , Keju Ma, Analysis of Euclidean algorithms for polynomials over finite fields, Journal of Symbolic Computation, v.9 n.4, p.429-455, April 1990 [doi>10.1016/S0747-7171(08)80021-1]
• 9: Roman Maeder, Storage Allocation for the Karatsuba Integer Multipliation Algorithm, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.59-65, September 15-17, 1993
• 10: R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804045]
• 11: Michael Monagan, Maximal quotient rational reconstruction: an almost optimal algorithm for rational reconstruction, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.243-249, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005321]
• 12: Peter Lawrence Montgomery. An FFT extension of the elliptic curve method of factorization. PhD thesis, Los Angeles, CA, USA, 1992.
• 13: Victor Y. Pan , Xinmao Wang, Acceleration of Euclidean algorithm and extensions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.207-213, July 07-10, 2002, Lille, France [doi>10.1145/780506.780533]
• 14: A. Schönhage. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica, 1:139--144, 1971.
• 15: Allan Steel. Private communication.
• 16: Paul S. Wang, A p-adic algorithm for univariate partial fractions, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.212-217, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806398]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory

Keywords:
fast Euclidean algorithm, modular algorithms, rational reconstruction