Rebound attack

From formulasearchengine
Revision as of 23:12, 17 January 2014 by en>Miracle Pen (Miracle Pen moved page The Rebound Attack to Rebound attack over redirect: case)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 rs is considered modulo a number m, one will obtain the number n=r×s1(modm). 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 v=(m,0) and w=(n,1). One then repeats the following steps until the first component of w becomes N. Put q=v1w1, put z = v − qw. The new v and w are then obtained by putting v = w and w = z.

Then with w such that w1N, one makes the second component positive by putting w = −w if w2<0. If w2<D and gcd(w1,w2)=1, then the fraction rs exists and r=w1 and s=w2, 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).

Template:Numtheory-stub