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.

In the rational reconstruction problem, one is given as input a value

n ≡ r

( mod

{\displaystyle n}

is an integer with the property that

( mod

The rational number

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

is sufficiently large relative to

Typically, it is assumed that a range for the possible values of

for some two numerical parameters

and a solution exists, the solution is unique and can be found efficiently.

Using a method from Paul S. Wang, it is possible to recover

using the Euclidean algorithm, as follows.

[1][2] One puts

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.

, one makes the second component positive by putting w = −w if

gcd (

, then the fraction

exists and

, else no such fraction exists.