Re: Modular Inversion

A few years ago I wrote:
: Has anyone tried a Lehmer/Knuth/Schoenhage/Gosper/etc. version of the
: Brent-Kung-Bojanczyk algorithm? See Knuth 3rd edition exercise 4.5.2-40
: or http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub096.html.
: 
: This algorithm is almost entirely 2-adic. As Knuth says: ``We don't need
: the most significant words.'' This strikes me as a huge advantage.

Stehle and Zimmerman presented an answer to this at ANTS a few weeks
ago. Actually, they presented something even better, namely a fast gcd
algorithm that's _completely_ 2-adic:

   http://www.loria.fr/~stehle/downloads/antsgcd.pdf

The idea is to expand the input ratio into a continued fraction, where
the quotients are chosen from

   {+-1/2,+-1/4,+-3/4,+-1/8,+-3/8,+-5/8,+-7/8,+-1/16,+-3/16,...}

rather than the usual {1,2,3,...}. Example, starting from {525,266}:

   525 =  (1/2) 266 + 392;  ord_2 392 = 3
   266 = (-3/4) 392 + 560;  ord_2 560 = 4
   392 = (-1/2) 560 + 672;  ord_2 672 = 5
   560 = (-1/2) 672 + 896;  ord_2 896 = 7
   672 =  (3/4) 896 +   0

Evidently gcd{525,266} is the odd part of 896. Of course, the algorithm
can also be used to compute modular reciprocals.

As far as I know, there's only one purely 2-adic gcd algorithm before
this in the literature: Purdy's algorithm, which replaces (a,b) with
(a+b,a-b) and then divides out powers of 2. But that algorithm can be
rather slow---consider, for example, (2^n+1,1)---and I don't see how to
turn it into an essentially-linear-time algorithm.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago