Rebound attack

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}(\mathrm{mod}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.

One puts $v=(m,0)$ and $w=(n,1)$. One then repeats the following steps until the first component of w becomes $\le N$. Put $q=\lfloor \frac{v_1}{w_1}\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\le 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.