In mathematics, rational reconstruction is a method that allows one to recover a rational number from its value modulo an integer. If a problem with a rational solution r s is considered modulo a number m, one will obtain the number n = r × s − 1 ( mod m ) . If |r| < N and 0 < s < D then r and s can be uniquely determined from n if m > 2ND 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 ≤ N . Put q = ⌊ v 1 w 1 ⌋ , 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 ≤ 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.
