Jacobi symbol using Lehmer's algorithm.

Niels Möller nisse at lysator.liu.se
Thu Feb 25 16:45:31 CET 2010

Torbjorn Granlund <tg at gmplib.org> writes:

> Please use a refmpz_powm, not mpz_powm, since we might at some point use
> mpz_powm for mpz_legendre.


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.

> 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...

But the main plan is to use it for testing mpz_jacobi, as a reference
implementation for the case that b is prime or has a known prime

>   I'm also tempted to change refmpz_jaboci to require b odd, ...
> This makes sense.

I'll do that too, then. Hmm, the usual definition of the Jacobi symbol
also requires that b is positive, right? I think current try.c calls
mpz_jacobi it with negative b.


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