asymptotically fast Jacobi symbol

[Torbjorn Granlund]

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

Nice work!

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?

For 10^9 limbs, GMP's asymptotically fastest multiplication is about
1,000,000 times faster that GMP's schoolbook multiplication...

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.)

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

-- 
Torbjörn