asymptotically optimal mpz_jacobi?
Paul.Zimmermann at loria.fr
Tue Nov 17 15:06:36 CET 2009
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.
More information about the gmp-discuss