Jacobi symbol using Lehmer's algorithm.

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  Other mpz functions used are mpz_fdiv_r, mpz_sub_ui, mpz_fdiv_q_2exp,
  mpz_cmp, mpz_sub, mpz_cmpabs_ui, mpz_sgn. Should any of those also be
  replaced by refmpz functions? I don't fully understand the logic here.

Me neither.  :-)

Some guidelines I try to follow:

o The ref functions should be conservatively implemented.

o We must not make the ref functions so slow that they seriously hurt
  the amont of testing possible.  E.g., we should avoid \Omega(n f(n))
  complexity where the tested function is O(f(n)).

o We should either use other ref functions for our implementation,
  alternatively non-ref functions in a different way than the library
  functions.

o It is OK to use the library functions if we don't have a ref function
  or if the ref function's slowness is a serious problem, but then we
  have to make sure we don't use it the same way as the library function
  for which we're implementing a ref function.

  > You're planning to start using refmpz_legendre?  (If the function is
  > unused, we might as well remove it, or ifdef it out.)
  
  Yes. For a start, I'm adding support in try.c, so I can get some testing
  of the reference function before I check it in...
  
:-)

-- 
Torbjörn