[Gmp-commit] /var/hg/gmp: 2 new changesets

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/a81d59da5220
changeset: 18362:a81d59da5220
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Sun Jun 19 15:29:04 2022 +0200
description:
mpz/millerrabin.c: Use mp_bitcnt_t.

details:   /var/hg/gmp/rev/cc75cab76738
changeset: 18363:cc75cab76738
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Sun Jun 19 15:30:05 2022 +0200
description:
mpz/stronglucas.c: Skip D if it's a multiple of 3.

diffstat:

 mpz/millerrabin.c |  10 ++++------
 mpz/stronglucas.c |  30 ++++++++++++++++++++++--------
 2 files changed, 26 insertions(+), 14 deletions(-)

diffs (86 lines):

diff -r 58bb9b017366 -r cc75cab76738 mpz/millerrabin.c
--- a/mpz/millerrabin.c	Sun May 29 18:08:56 2022 +0200
+++ b/mpz/millerrabin.c	Sun Jun 19 15:30:05 2022 +0200
@@ -65,7 +65,7 @@
 mpz_millerrabin (mpz_srcptr n, int reps)
 {
   mpz_t nm, x, y, q;
-  unsigned long int k;
+  mp_bitcnt_t k;
   int is_prime;
   TMP_DECL;
   TMP_MARK;
@@ -79,7 +79,7 @@
   MPZ_TMP_INIT (q, SIZ (n));
 
   /* Find q and k, where q is odd and n = 1 + 2**k * q.  */
-  k = mpz_scan1 (nm, 0L);
+  k = mpn_scan1 (PTR (nm), 0);
   mpz_tdiv_q_2exp (q, nm, k);
   ++k;
 
@@ -199,16 +199,14 @@
 
 static int
 millerrabin (mpz_srcptr n, mpz_ptr x, mpz_ptr y,
-	     mpz_srcptr q, unsigned long int k)
+	     mpz_srcptr q, mp_bitcnt_t k)
 {
-  unsigned long int i;
-
   mpz_powm (y, x, q, n);
 
   if (mpz_cmp_ui (y, 1L) == 0 || mod_eq_m1 (y, n))
     return 1;
 
-  for (i = 1; i < k; i++)
+  for (mp_bitcnt_t i = 1; i < k; ++i)
     {
       mpz_powm_ui (y, y, 2L, n);
       if (mod_eq_m1 (y, n))
diff -r 58bb9b017366 -r cc75cab76738 mpz/stronglucas.c
--- a/mpz/stronglucas.c	Sun May 29 18:08:56 2022 +0200
+++ b/mpz/stronglucas.c	Sun Jun 19 15:30:05 2022 +0200
@@ -148,20 +148,34 @@
       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;