Rational reconstruction (mathematics) explained

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 twonumerical parameters N and D . Whenever m > 2 ND 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.^[1]

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{ (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 (r)/(s) exists and r = w _{1} and s = w _{2} , else no such fraction exists.

Notes and References

1. .