Rational reconstruction (mathematics)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 \frac{r}{s} is considered modulo a number m, one will obtain the number n = r\times s^{-1}\pmod{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. [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{\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 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 \frac{r}{s} exists and r = w_{1} and s = w_{2}, else no such fraction exists.


  1. ^ P. S. Wang, a p-adic algorithm for univariate partial fractions, Proceedings of SYMSAC ´81, ACM Press, 212 (1981); P. S. Wang, M. J. T. Guy, and J. H. Davenport, p-adic reconstruction of rational numbers, SIGSAM Bulletin 16 (1982).