asymptotically optimal mpz_jacobi?

Paul Zimmermann Paul.Zimmermann at
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.

Paul Zimmermann

More information about the gmp-discuss mailing list