asymptotically optimal mpz_jacobi?

[Paul Zimmermann]

       Hi,

last April I asked:

> "GMP 5 will be released as soon as it is ready. This release will make all
>  major functions of GMP asymptotically optimal, including division, exact
>  division, modular computation, etc."
>
> Does "etc" also include mpz_jacobi?

a description of an O(M(n) log n) algorithm for the Jacobi symbol can be found
in the book Algorithmic Number Theory by Bach and Shallit (solution of exercise
5.52). It only needs the partial quotients mod 2 and the partial remainders
mod 4, thus it should be easy to adapt the fast gcd code.

Paul Zimmermann