From 07ec522630e0c08e010e0d2fcc5e7ae7bb29b649 Mon Sep 17 00:00:00 2001 From: Marco Bodrato Date: Sun, 19 Jun 2022 15:30:05 +0200 Subject: mpz/stronglucas.c: Skip D if it's a multiple of 3. --- mpz/stronglucas.c | 30 ++++++++++++++++++++++-------- 1 file changed, 22 insertions(+), 8 deletions(-) (limited to 'mpz') diff --git a/mpz/stronglucas.c b/mpz/stronglucas.c index 1b2eff2fe..0bf1ce019 100644 --- a/mpz/stronglucas.c +++ b/mpz/stronglucas.c @@ -148,20 +148,34 @@ mpz_stronglucas (mpz_srcptr x, mpz_ptr V, mpz_ptr Qk) maxD = GMP_NUMB_MAX; maxD = MIN (maxD, ULONG_MAX); - D = GMP_NUMB_BITS % 16 == 0 ? (GMP_NUMB_BITS % 32 == 0 ? 17 : 15) : 5; + unsigned Ddiff = 2; +#if GMP_NUMB_BITS % 16 == 0 + const unsigned D2 = 6; +#if GMP_NUMB_BITS % 32 == 0 + D = 19; + Ddiff = 4; +#else + D = 17; +#endif +#else + const unsigned D2 = 4; + D = 7; +#endif - /* Search a D such that (D/n) = -1 in the sequence 5,-7,9,-11,.. */ - /* For those Ds we have (D/n) = (n/|D|) */ + /* Search a D such that (D/n) = -1 in the sequence 5,-7,9,-11,.. */ + /* For those Ds we have (D/n) = (n/|D|) */ /* FIXME: Should we loop only on prime Ds? */ - /* The only interesting composite D is 15. */ - do + /* The only interesting composite D is 15, because 3 is not tested. */ + for (;;) { + jac = mpz_oddjacobi_ui (n, D); + if (jac != 1) + break; if (UNLIKELY (D >= maxD)) return 1; - D += 2; - jac = mpz_oddjacobi_ui (n, D); + D += Ddiff; + Ddiff = D2 - Ddiff; } - while (jac == 1); if (UNLIKELY (jac == 0)) return 0; -- cgit v1.2.1