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$. That is,
$n$ is an integer with the property that $ns\equiv r\pmod$. 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\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_\leq N$, one makes the second component positive by putting ''w'' = −''w'' if $w_<0$. If w_2 and $\gcd(w_1,w_2)=1$, then the fraction $\frac$ exists and $r = w_$ and $s = w_$, else no such fraction exists.

References

{{reflist

Number theoretic algorithms