Checking for congruent to negative numbers

Seth Troisi braintwo at gmail.com
Fri Nov 10 10:40:33 CET 2023


Several places in gmp-ecm there's a number x that has been reduced mod n
and I need to check that it's not congruent to {1, -1} or {1, 2, -1, -2}.
It's easy to check for congruent to small positive numbers with
mpz_cmp_ui(x, 1) == 0, but there doesn't seem to be a
mpz_congruent_si_p(const mpz_t n, long int c, const mpz_t d). The cleanest
way I can think to do this is with

mpz_t tmp;
mpz_init_set(tmp, n);
if (c > 0)
  mpz_sub_ui(tmp, tmp, c);
else
 mpz_add_ui(tmp, tmp, abs(c));
bool result = mpz_divisible_p(tmp, d);
mpz_clear(tmp);
return result;

Possibly adding faster code for the cases where 0 <= n < d

Is there a better way to do this? Would gmp be interested in me adding
mpz_congruent_si_p?

Thanks,
Seth


More information about the gmp-discuss mailing list