asymptotically fast Jacobi symbol

Torbjorn Granlund tg at
Sat Jan 23 14:29:06 CET 2010

Paul Zimmermann <Paul.Zimmermann at> writes:

  GMP 5.0.0 implements a quadratic algorithm for the Jacobi symbol. In 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?


More information about the gmp-devel mailing list