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