Rational reconstruction (mathematics)

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

edit

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

edit

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

edit
  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, S2CID 10695567
  2. ^ Wang, Paul S.; Guy, M. J. T.; Davenport, J. H. (May 1982), "P-adic reconstruction of rational numbers", SIGSAM Bulletin, 16 (2), New York, NY, USA: Association for Computing Machinery: 2–3, CiteSeerX 10.1.1.395.6529, doi:10.1145/1089292.1089293, S2CID 44536107.