Jacobi symbol using Lehmer's algorithm.
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
* 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