Misplaced Pages

Rational reconstruction (mathematics)

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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

One puts v = ( m , 0 ) {\displaystyle v=(m,0)} and w = ( n , 1 ) {\displaystyle w=(n,1)} . One then repeats the following steps until the first component of w becomes ≤ N {\displaystyle \leq N} . Put q = ⌊ v 1 w 1 ⌋ {\displaystyle 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 ≤ N {\displaystyle w_{1}\leq N} , one makes the second component positive by putting w = −w if w 2 < 0 {\displaystyle w_{2}<0} . If w 2 < D {\displaystyle w_{2}<D} and gcd ( w 1 , w 2 ) = 1 {\displaystyle \gcd(w_{1},w_{2})=1} , then the fraction r s {\displaystyle {\frac {r}{s}}} exists and r = w 1 {\displaystyle r=w_{1}} and s = w 2 {\displaystyle s=w_{2}} , else no such fraction exists.

References

  1. Wang, Paul S. (1981), "A p-adic algorithm for univariate partial fractions", Proceedings of the Fourth International Symposium on Symbolic and Algebraic Computation (SYMSAC '81), New York, NY, USA: Association for Computing Machinery, pp. 212–217, doi:10.1145/800206.806398, ISBN 0-89791-047-8, S2CID 10695567
  2. Wang, Paul S.; Guy, M. J. T.; Davenport, J. H. (May 1982), "P-adic reconstruction of rational numbers", SIGSAM Bulletin, 16 (2), New York, NY, USA: Association for Computing Machinery: 2–3, CiteSeerX 10.1.1.395.6529, doi:10.1145/1089292.1089293, S2CID 44536107.
Category: