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(\mathrm{mod}m)$. That is, $n$ is an integer with the property that $ns\equiv r(\mathrm{mod}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. One puts $v=(m,0)$ and $w=(n,1)$. One then repeats the following steps until the first component of w becomes $\le N$. Put $q=\lfloor \frac{v_1}{w_1}\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\le N$, one makes the second component positive by putting w = −w if $w_2<0$. If $w_2<D$ 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.