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.

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}<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.