2-adic square root algorithm
Paul.Zimmermann at loria.fr
Fri Dec 11 14:16:31 CET 2009
Pierrick Gaudry suggested the following idea this morning: it might be doable
to design a 2-adic (i.e., LSB) variant of the "recursive square root" algorithm
(Algorithm 1.12 page 42 in Modern Computer Arithmetic 0.4).
Assume you have computed a LSB square root of m mod \beta, i.e., you have
written m = t^2 + \beta r (here r might be negative, and we assume m odd).
Now you lift this square root as follows: we want to compute the LSB square
root of m + \beta m' in the form m + \beta m' = (t + \beta s)^2 + \beta^2 r'.
This yields s = (r + m')/(2t) mod \beta, and the new remainder r' can be
constructed by the remainder of that LSB division, and s^2.
PS: what is not clear to me is what to do when r+m' is odd, since then for
\beta a power of two we cannot divide r+m' by 2.
More information about the gmp-devel