Jacobi symbol using Lehmer's algorithm.

[Niels Möller]

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.

Ok.

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

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

Regards,
/Niels

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