From 3ee25abfd365d3cd64019de63a1654db8204ca22 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Thu, 3 Jul 2025 23:11:26 -0700 Subject: [PATCH] factor: prefer exact division MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit * src/factor.c (mp_factor_using_division, mp_factor_using_pollard_rho): Use exact division when it suffices, as it’s typically faster. --- src/factor.c | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-) diff --git a/src/factor.c b/src/factor.c index 79eeabe829..849c684e61 100644 --- a/src/factor.c +++ b/src/factor.c @@ -987,7 +987,7 @@ mp_factor_using_division (mpz_t t) { for (m = 0; mpz_divisible_ui_p (t, d); m++) { - mpz_tdiv_q_ui (t, t, d); + mpz_divexact_ui (t, t, d); if (mp_finish_up_in_single (&factors, t, i, d)) { mp_factor_insert_ui (&factors, d, m + 1); @@ -1568,9 +1568,9 @@ mp_factor_using_pollard_rho (struct mp_factors *factors, mp_factor_using_pollard_rho (factors, gp, gn, a + 1); } - mpn_tdiv_qr (qp, tp, 0, mp, n, gp, gn); /* could use divexact */ - mp_size_t qn = n - gn + (qp[n - 1] != 0); - mpz_t q = MPZ_ROINIT_N (qp, qn); + mpz_t m = MPZ_ROINIT_N ((mp_limb_t *) mp, n), q; + mpz_init (q); + mpz_divexact (q, m, g); if (!mp_finish_in_single (factors, q)) { @@ -1579,10 +1579,13 @@ mp_factor_using_pollard_rho (struct mp_factors *factors, else { devmsg ("[composite factor--restarting pollard-rho] "); - mp_factor_using_pollard_rho (factors, qp, qn, a + 1); + mp_factor_using_pollard_rho (factors, mpz_limbs_read (q), + mp_size (q), a + 1); } } + mpz_clear (q); + finish: free (scratch); } -- 2.47.2