From 4171ca33536219248afa1b74a561f1adc5739b64 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Wed, 9 Jul 2025 21:22:12 -0700 Subject: [PATCH] factor: fix mp_factor_using_pollard_rho aliasing * src/factor.c (mp_factor_using_pollard_rho): Fix recently-introduced aliasing bug by computing q before g gets updated in place. Problem discovered on a hypothetical platform where W_TYPE_SIZE is neither 32 nor 64. --- src/factor.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/src/factor.c b/src/factor.c index 134c092f84..fe3a639a14 100644 --- a/src/factor.c +++ b/src/factor.c @@ -939,7 +939,7 @@ mp_finish_in_single (struct mp_factors *mp_factors, mpz_t n) return mp_finish_up_in_single (mp_factors, n, 0); } -/* Return some or all factors of T, where B^2 / 2 <= T. +/* Return some or all factors of T. Divide T by the factors found. */ static struct mp_factors mp_factor_using_division (mpz_t t) @@ -1534,6 +1534,10 @@ mp_factor_using_pollard_rho (struct mp_factors *factors, while (gn == 1 && gp[0] == 1); mpz_t g = MPZ_ROINIT_N (gp, gn); + 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, g)) { if (mp_prime_p (g)) @@ -1542,10 +1546,6 @@ mp_factor_using_pollard_rho (struct mp_factors *factors, mp_factor_using_pollard_rho (factors, gp, gn, a + 1); } - 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)) { if (mp_prime_p (q)) @@ -1601,7 +1601,7 @@ factor (struct factors *factors, mp_limb_t t1, mp_limb_t t0) return factor_up (factors, t1, t0, 0); } -/* Return the prime factors of T, where B^2 / 2 <= T. */ +/* Return the prime factors of T. */ static struct mp_factors mp_factor (mpz_t t) { -- 2.47.3