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 $n \equiv r/s\pmod{m}$ . That is,

$n$ is an integer with the property that $ns\equiv r\pmod{m}$ . The rational number $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 $m$ is sufficiently large relative to $r$ and $s$ .

Typically, it is assumed that a range for the possible values of $r$ and $s$ is known: $|r| < N$ and $0 < s < D$ for some two

numerical parameters $N$ and $D$ . Whenever $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 $r/s$ from $n$ and $m$ using the Euclidean algorithm, as follows.{{citation|last=Wang|first=Paul S.|contribution=A p-adic algorithm for univariate partial fractions|doi=10.1145/800206.806398|isbn=0-89791-047-8|location=New York, NY, USA|pages=212–217|publisher=Association for Computing Machinery|title=Proceedings of the Fourth International Symposium on Symbolic and Algebraic Computation (SYMSAC '81)|year=1981|title-link=International Symposium on Symbolic and Algebraic Computation|s2cid=10695567 }}{{citation|last1=Wang|first1=Paul S.|last2=Guy|first2=M. J. T.|author2-link=Michael Guy|last3=Davenport|first3=J. H.|author3-link=James H. Davenport|date=May 1982|doi=10.1145/1089292.1089293|issue=2|journal=ACM SIGSAM Bulletin|location=New York, NY, USA|pages=2–3|publisher=Association for Computing Machinery|title=P-adic reconstruction of rational numbers|volume=16|citeseerx=10.1.1.395.6529|s2cid=44536107 }}.

One puts $v = (m,0)$ and $w = (n,1)$ . One then repeats the following steps until the first component of w becomes $\leq N$ . Put $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 $w_{1}\leq N$ , one makes the second component positive by putting w = −w if $w_{2}<0$ . If $w_2 and \gcd(w_1,w_2)=1, then the fraction \frac{r}{s} exists and r = w_{1} and s = w_{2}, else no such fraction exists.$

References

Category:Number theoretic algorithms