Rational reconstruction (mathematics)

Summary

In mathematics, rational reconstruction is a method that allows one to recover a rational number from its value modulo a sufficiently large integer.

Problem statement

In the rational reconstruction problem, one is given as input a value . That is, is an integer with the property that . The rational number is unknown, and the goal of the problem is to recover it from the given information.

In order for the problem to be solvable, it is necessary to assume that the modulus is sufficiently large relative to and . Typically, it is assumed that a range for the possible values of and is known: and for some two numerical parameters and . Whenever and a solution exists, the solution is unique and can be found efficiently.

Solution

Using a method from Paul S. Wang, it is possible to recover from and using the Euclidean algorithm, as follows.[1][2]

One puts and . One then repeats the following steps until the first component of w becomes . Put , put z = v − qw. The new v and w are then obtained by putting v = w and w = z.

Then with w such that , one makes the second component positive by putting w = −w if . If and , then the fraction exists and and , else no such fraction exists.

References

  1. ^ Wang, Paul S. (1981), "A p-adic algorithm for univariate partial fractions", Proceedings of the Fourth International Symposium on Symbolic and Algebraic Computation (SYMSAC '81), New York, NY, USA: Association for Computing Machinery, pp. 212–217, doi:10.1145/800206.806398, ISBN 0-89791-047-8
  2. ^ Wang, Paul S.; Guy, M. J. T.; Davenport, J. H. (May 1982), "P-adic reconstruction of rational numbers", SIGSAM Bulletin, New York, NY, USA: Association for Computing Machinery, 16 (2): 2–3, CiteSeerX 10.1.1.395.6529, doi:10.1145/1089292.1089293.