diff options
author | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2022-06-19 15:30:05 +0200 |
---|---|---|
committer | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2022-06-19 15:30:05 +0200 |
commit | 07ec522630e0c08e010e0d2fcc5e7ae7bb29b649 (patch) | |
tree | f67d5c489f57313d8841d7b563694e6103168f0d /mpz/stronglucas.c | |
parent | 67ce09579f0ab1bf9f89a536261270669e61b67e (diff) | |
download | gmp-07ec522630e0c08e010e0d2fcc5e7ae7bb29b649.tar.gz |
mpz/stronglucas.c: Skip D if it's a multiple of 3.
Diffstat (limited to 'mpz/stronglucas.c')
-rw-r--r-- | mpz/stronglucas.c | 30 |
1 files changed, 22 insertions, 8 deletions
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; |