asymptotically fast Jacobi symbol

[Torbjorn Granlund]

Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

  > 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.
  
Jacobi and n over k are the ones where GMP really performs poorly.

  > 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.
  
Is that because a certain efficiency of the gcd algorithm for 10^8
limbs, or is it perhaps due to non-linearity of the underlying
multiplication?

Or are you saying the bgcd is now superior to ngcd?

  > 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.
  
Does it suffer from the same inherent growth-to-the-left problem as the
gcd algorithm?

-- 
Torbjörn