Rational reconstruction (mathematics)
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 formula_1. That is, formula_2 is an integer with the property that formula_3. The rational number formula_4 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 formula_5 is sufficiently large relative to formula_6 and formula_7. Typically, it is  assumed that a range for the possible values of formula_6 and formula_7 is known: formula_10 and formula_11 for some two numerical parameters formula_12 and formula_13. Whenever formula_14 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 formula_4 from formula_2 and formula_5 using the Euclidean algorithm, as follows. One puts formula_18 and formula_19. One then repeats the following steps until the first component of "w" becomes formula_20. Put formula_21, put "z" = "v" − "qw". The new "v" and "w" are then obtained by  putting "v" = "w" and "w" = "z". Then with "w" such that formula_22, one makes the second component positive by putting "w" = −"w" if formula_23. If formula_24 and formula_25, then the fraction formula_26 exists and formula_27 and formula_28, else no such fraction exists.