Jacobi symbol using Lehmer's algorithm.

Niels Möller nisse at lysator.liu.se
Thu Feb 25 14:53:39 CET 2010

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

> Yesterday, I and Torbjörn had a short discussion on the Jacobi
> algorithm, including the testing issues, with Johan Håstad. We came up
> with the following strategy.

I'm slowly looking at the jacobi testing issues. In refmpz.c there are
three functions:

* refmpz_kronecker. Used in tests/devel/try.c. 

* refmpz_jacobi. Used by tests/devel/try.c. The definition is somewhat
  fishy to me, instead of asserting that b is odd, it removes any power
  of two present in b.

* refmpz_legendre. Not used at all.

I'm about to rewrite refmpz_legendre, using powm. I'm also tempted to
change refmpz_jaboci to require b odd, but I'm not sure if that's going
to break anything. After a quick look at try.c, it seems to do the right
thing and only pass odd b to jacobi.


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list