en>Miracle Pen: Miracle Pen moved page The Rebound Attack to Rebound attack over redirect: case

2014-01-17T22:12:08Z

Miracle Pen moved page The Rebound Attack to Rebound attack over redirect: case

New page

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 <math>\frac{r}{s}</math> is considered modulo a number ''m'', one will obtain the number <math>n = r\times s^{-1}\pmod{m}</math>. If |''r''| < ''N'' and 0 < ''s'' < ''D'' then ''r'' and ''s'' can be uniquely determined from ''n'' if ''m'' > 2''ND'' using the [[Euclidean algorithm]], as follows. <ref>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).</ref>

One puts <math>v = (m,0)</math> and <math>w = (n,1)</math>. One then repeats the following steps until the first component of ''w'' becomes <math>\leq N</math>. Put <math>q = \left\lfloor{\frac{v_{1}}{w_{1}}}\right\rfloor</math>, put ''z'' = ''v'' − ''qw''. The new ''v'' and ''w'' are then obtained by putting ''v'' = ''w'' and ''w'' = ''z''.

Then with ''w'' such that <math>w_{1}\leq N</math>, one makes the second component positive by putting ''w'' = −''w'' if <math>w_{2}<0</math>. If <math>w_2<D</math> and <math>\gcd(w_1,w_2)=1</math>, then the fraction <math>\frac{r}{s}</math> exists and <math>r = w_{1}</math> and <math>s = w_{2}</math>, else no such fraction exists.

==References==
<references/>

{{numtheory-stub}}

[[Category:Number theory]]

Rebound attack - Revision history

en>Miracle Pen: Miracle Pen moved page The Rebound Attack to Rebound attack over redirect: case