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

In the rational reconstruction problem, one is given as input a value ${\displaystyle n\equiv r/s{\pmod {m}}}$. That is, ${\displaystyle n}$ is an integer with the property that ${\displaystyle ns\equiv r{\pmod {m}}}$. The rational number ${\displaystyle r/s}$ 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 ${\displaystyle m}$ is sufficiently large relative to ${\displaystyle r}$ and ${\displaystyle s}$. Typically, it is assumed that a range for the possible values of ${\displaystyle r}$ and ${\displaystyle s}$ is known: ${\displaystyle |r|<N}$ and ${\displaystyle 0<s<D}$ for some two numerical parameters ${\displaystyle N}$ and ${\displaystyle D}$. Whenever ${\displaystyle m>2ND}$ 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 ${\displaystyle r/s}$ from ${\displaystyle n}$ and ${\displaystyle m}$ using the Euclidean algorithm, as follows. ^{[1] [2]}

One puts ${\displaystyle v=(m,0)}$ and ${\displaystyle w=(n,1)}$. One then repeats the following steps until the first component of w becomes ${\displaystyle \leq N}$. Put ${\displaystyle q=\left\lfloor {\frac {v_{1}}{w_{1}}}\right\rfloor }$, put z = v − qw. The new v and w are then obtained by putting v = w and w = z.

Then with w such that ${\displaystyle w_{1}\leq N}$, one makes the second component positive by putting w = −w if ${\displaystyle w_{2}<0}$. If ${\displaystyle w_{2}<D}$ and ${\displaystyle \gcd(w_{1},w_{2})=1}$, then the fraction ${\displaystyle {\frac {r}{s}}}$ exists and ${\displaystyle r=w_{1}}$ and ${\displaystyle s=w_{2}}$, 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, S2CID   10695567
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, S2CID   44536107 .