From 82f0d48d954a40a5607bacaea9bf807d58420104 Mon Sep 17 00:00:00 2001 From: Marco Bodrato Date: Sat, 17 Oct 2020 11:55:31 +0200 Subject: bootstrap.c (mpz_invert_2exp): Simplify. --- bootstrap.c | 25 ++++++------------------- 1 file changed, 6 insertions(+), 19 deletions(-) (limited to 'bootstrap.c') diff --git a/bootstrap.c b/bootstrap.c index 5f8ed72c7..07eb416e3 100644 --- a/bootstrap.c +++ b/bootstrap.c @@ -105,33 +105,20 @@ mpz_preinv_invert (mpz_t inv, const mpz_t d, int numb_bits) mpz_clear (t); } -/* Calculate r satisfying r*d == 1 mod 2^n. */ +/* Calculate r satisfying r*a == 1 mod 2^n. */ void mpz_invert_2exp (mpz_t r, const mpz_t a, unsigned long n) { - unsigned long i; - mpz_t inv, prod; + mpz_t mod; assert (mpz_odd_p (a)); - mpz_init_set_ui (inv, 1L); - mpz_init (prod); + mpz_init (mod); + mpz_setbit (mod, n); - for (i = 1; i < n; i++) - { - mpz_mul (prod, inv, a); - if (mpz_tstbit (prod, i) != 0) - mpz_setbit (inv, i); - } - - mpz_mul (prod, inv, a); - mpz_tdiv_r_2exp (prod, prod, n); - assert (mpz_cmp_ui (prod, 1L) == 0); - - mpz_set (r, inv); + mpz_invert (r, a, mod); - mpz_clear (inv); - mpz_clear (prod); + mpz_clear (mod); } /* Calculate inv satisfying r*a == 1 mod 2^n. */ -- cgit v1.2.1