asymptotically fast Jacobi symbol

Paul Zimmermann Paul.Zimmermann at loria.fr
Sat Jan 23 18:59:46 CET 2010


>   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 (which is
>   very difficult to achieve).
> 
> Nice work!

thank you.

> I don't understand your comment about difficultly of 100x speedup.
> Surely 100x is not difficult to achieve when comparing a O(n^2)
> algorithm with a O(M(n)log(n)) algorithm?

I meant there are now only few functions where GMP implements
sub-optimal algorithms (with respect to the state-of-the-art).
The Jacobi symbol is one of those.

> When comparing the fast GCD algorithms, Niels' ngcd is the current
> champion.  Your and Stehlé's right-to-left algorithm is unfortunately
> slower.  (I write unfortunately since its relative simplicity is a great
> advantage from an implementation perspective.)

this is not completely correct. As demonstrated on 
http://www.loria.fr/~zimmerma/mca/pub226.html, our right-to-left algorithm
is 6.3% faster than mpz_gcd for 10^8 limbs.

> Which algorithm do you expect to be fastest for Jacobi symbol
> computation, one based on ngcd, or your present suggestion?

I have no definite answer to that. You need to implement one
based on ngcd and compare.

Paul


More information about the gmp-devel mailing list