asymptotically fast Jacobi symbol

[Niels Möller]

Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

> GMP 5.0.0 implements a quadratic algorithm for the Jacobi symbol. In
> http://wwwmaths.anu.edu.au/~brent/pub/pub236.html we describe a subquadratic
> algorithm, and exhibit speedups of almost a factor of 100 over GMP 

Sounds great! I've had a first reading of the paper.

If I look at the quadratic algorithm in Cohen's book (Algorithm 1.4.10,
page 29,
http://books.google.com/books?id=hXGr-9l1DXcC&lpg=PA27&ots=yva-LSAPHh&dq=Kronecker%20symbol%20reciprocity&pg=PA29#v=onepage&q=Kronecker%20symbol%20reciprocity&f=false,
this algorithm works from left to right in that it computes quotients
like in Euclid's algorithm, but also right to left in that power of twos
are handled specially. So it's not a trivial fit to left-to-right hgcd.

The point of subquadratic left-to-right gcd is that one computes all
quotients, but not all remainders (since the latter would imply
quadratic time). But to compute the Jacobi/Kronecker symbol, one would
need to compute the least significant bits of each remainder, which
might be possible but seems somewhat unnatural in this setting.

For that reason, doing it as a pure right-to-left algorithm like in your
paper seems attractive (you have a somewhat analogous problem in that
you need to know the sign bit from the left end, and you handle that by
forcing all intermediates to be positive which brings some new
complications compared to binary recursive gcd).

But I'm still curious about earlier work on fast left-to-right Jacobi.
Your paper mentions a poorly documented left-to-right-algorithm due to
Bach, Shallit and Bachmann, and another one by Schönhage and Weilert.
Are any of these available online?

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.