Rational reconstruction (mathematics)

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 is considered modulo a number m, one will obtain the number . 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 and . One then repeats the following steps until the first component of w becomes . Put , put z = v โˆ’ qw. The new v and w are then obtained by putting v = w and w = z.

Then with w such that , one makes the second component positive by putting w = โˆ’w if . If and , then the fraction exists and and , else no such fraction exists.

References

  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).


This article is issued from Wikipedia - version of the 6/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.