Rational reconstruction (mathematics)

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.

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.