2-adic square root algorithm

[Paul Zimmermann]

       Hi,

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.

Paul

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.