Maximal quotient rational reconstruction: an almost optimal algorithm for rational reconstruction

ABSTRACT

Let n/d ∈ Q, m be a positive integer and let u = n/d mod m. Thus $u$ is the image of a rational number modulo m. The rational reconstruction problem is; given u and m find n/d. A solution was first given by Wang in 1981. Wang's algorithm outputs n/d when m > 2 M² where M = max(|n|,d). Because of the wide application of this algorithm in computer algebra, several authors have investigated its practical efficiency and asymptotic time complexity.In this paper we present a new solution which is almost optimal in the following sense; with controllable high probability, our algorithm will output n/d when m is a modest number of bits longer than 2 |n| d. This means that in a modular algorithm where m is a product of primes, the modular algorithm will need one or two primes more than the minimum necessary to reconstruct n/d; thus if |n| ⇐ d or d ⇐ |n| the new algorithm saves up to half the number of primes. Further, our algorithm will fail with high probability when m < 2 |n| d.

REFERENCES

• 1: Elizabeth A. Arnold, Modular algorithms for computing Gröbner bases, Journal of Symbolic Computation, v.35 n.4, p.403-419, April 2003 [doi>10.1016/S0747-7171(02)00140-2]
• 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 , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 5: The GNU Multiple Precision Arithmetic Library. Copyright, Free Software Foundation, Inc. (2002). http://www.gnu.org/software/gmp/gmp.html
• 6: Mark van Hoeij , Michael Monagan, A modular GCD algorithm over number fields presented with multiple extensions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.109-116, July 07-10, 2002, Lille, France [doi>10.1145/780506.780520]
• 7: Tudor Jebelean, Improving the Multiprecision Euclidian Algorithm, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.45-58, September 15-17, 1993
• 8: E. Kaltofen, H. Rolletschek. Computing Greatest Common Divisors and Factorization in Quadratic Number Fields. Mathematics of Computation, 53, pp. 697--720, 1989.
• 9: J. de Kleine, M. Monagan. A Modular Design and Implementation of Buchberger's Algorithm. Proceedings of the Rhine Workshop on Computer Algebra, 2002.
• 10: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 11: 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]
• 12: Lars Langemyr, An Asymptotically Fast Probabilitstic Algorithm for Computing Polynominal GCD's over an Algebraic Number Field, Proceedings of the 8th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.222-233, August 20-24, 1990
• 13: Peter Lawrence Montgomery, An FFT extension of the elliptic curve method of factorization, University of California at Los Angeles, Los Angeles, CA, 1992
• 14: 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]
• 15: A. Schönhage. Schnelle Berechnung von Kettenbruchenwicklungen. Acta Infomatica 1 pp. 139--144, 1971.
• 16: A. Steel (2003). Private communication.
• 17: 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]
• 18: Paul S. Wang , M. J. T. Guy , J. H. Davenport, P-adic reconstruction of rational numbers, ACM SIGSAM Bulletin, v.16 n.2, p.2-3, May 1982 [doi>10.1145/1089292.1089293]
• 19: Paul S. Wang, Early detection of true factors in univariate polynominal factorization, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.225-235, March 28-30, 1983

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms

Keywords:
euclidean algorithm, modular algorithms, rational reconstruction