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