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 [math]\displaystyle{ n \equiv r/s\pmod{m} }[/math]. That is, [math]\displaystyle{ n }[/math] is an integer with the property that [math]\displaystyle{ ns\equiv r\pmod{m} }[/math]. The rational number [math]\displaystyle{ r/s }[/math] 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 [math]\displaystyle{ m }[/math] is sufficiently large relative to [math]\displaystyle{ r }[/math] and [math]\displaystyle{ s }[/math]. Typically, it is assumed that a range for the possible values of [math]\displaystyle{ r }[/math] and [math]\displaystyle{ s }[/math] is known: [math]\displaystyle{ |r| \lt N }[/math] and [math]\displaystyle{ 0 \lt s \lt D }[/math] for some two numerical parameters [math]\displaystyle{ N }[/math] and [math]\displaystyle{ D }[/math]. Whenever [math]\displaystyle{ m \gt 2ND }[/math] 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 [math]\displaystyle{ r/s }[/math] from [math]\displaystyle{ n }[/math] and [math]\displaystyle{ m }[/math] using the Euclidean algorithm, as follows.

One puts [math]\displaystyle{ v = (m,0) }[/math] and [math]\displaystyle{ w = (n,1) }[/math]. One then repeats the following steps until the first component of w becomes [math]\displaystyle{ \leq N }[/math]. Put [math]\displaystyle{ q = \left\lfloor{\frac{v_{1}}{w_{1}}}\right\rfloor }[/math], put z = v − qw. The new v and w are then obtained by putting v = w and w = z.

Then with w such that [math]\displaystyle{ w_{1}\leq N }[/math], one makes the second component positive by putting w = −w if [math]\displaystyle{ w_{2}\lt 0 }[/math]. If [math]\displaystyle{ w_2\lt D }[/math] and [math]\displaystyle{ \gcd(w_1,w_2)=1 }[/math], then the fraction [math]\displaystyle{ \frac{r}{s} }[/math] exists and [math]\displaystyle{ r = w_{1} }[/math] and [math]\displaystyle{ s = w_{2} }[/math], else no such fraction exists.