Subject: bug#12350: Composites identified as primes in factor.c (when HAVE_GMP)

From: Jim Meyering <[email-masked]>
Date: Sat, 15 Sep 2012 22:47:02 +0200

Torbjorn Granlund wrote:

>   > We won't be sending any more code replacement blobs to this address; it
>   > is most surely the wrong place.
>
>   I guess you're saying that because there's been too little feedback?
>
> Not really.  I suppose I'm sending a code replacement so that it get
> appended to a bug report.  My initial post was infact a bug report, but
> that was 30 posts ago...
>
>   IMHO, this is great work.
>
> Thanks.
>
>   You may consider it accepted.  That was clear in my mind from
>   the beginning.  Sorry if I didn't make that clear to you.
>   Now, it's just a matter of integrating it.
>
> Good.  I would certainly accept rejection, or partial rejection.  I
> suppose the code is a fair bit more complex than one might perhaps
> expect, but we don't know how to make it neater without a large
> performance penalty.  But we can make it much more complex if desirable.
> :-)
>
> I think the ugliest part is the interface to longlong.h.  I don't know
> how to make that better, though.
>
>   Here are some suggested changes -- I made these against
>   a temporary local git repository using your -005 tarball.
>   That was before I learned (just now) that you have a mercurial
>   repository.

Here are some more suggested changes.
Sorry about the terse commit logs.
The changes are mostly stylistic.

changeset:   121:80954440c618
tag:         tip
user:        Jim Meyering <[email-masked]>
date:        Sat Sep 15 22:37:19 2012 +0200
files:       factor.c
description:
use "unsigned long int" consistently, not "unsigned long"

 factor.c |  40 ++++++++++++++++++++--------------------
 1 files changed, 20 insertions(+), 20 deletions(-)

diff --git a/factor.c b/factor.c
--- a/factor.c
+++ b/factor.c
@@ -119,7 +119,7 @@
 #else
 typedef unsigned char UQItype;
 typedef		 long SItype;
-typedef unsigned long USItype;
+typedef unsigned long int USItype;
 #if HAVE_LONG_LONG
 typedef	long long int DItype;
 typedef unsigned long long int UDItype;
@@ -178,8 +178,8 @@
 struct mp_factors
 {
   mpz_t         *p;
-  unsigned long *e;
-  unsigned long nfactors;
+  unsigned long int *e;
+  unsigned long int nfactors;
 };
 #endif

@@ -189,7 +189,7 @@
 #define umul_ppmm(w1, w0, u, v)						\
   do {									\
     uintmax_t __x0, __x1, __x2, __x3;					\
-    unsigned long __ul, __vl, __uh, __vh;				\
+    unsigned long int __ul, __vl, __uh, __vh;				\
     uintmax_t __u = (u), __v = (v);					\
 									\
     __ul = __ll_lowpart (__u);						\
@@ -530,9 +530,9 @@
 static void
 mp_factor_insert (struct mp_factors *factors, mpz_t prime)
 {
-  unsigned long nfactors = factors->nfactors;
+  unsigned long int nfactors = factors->nfactors;
   mpz_t         *p  = factors->p;
-  unsigned long *e  = factors->e;
+  unsigned long int *e  = factors->e;
   long i;

   /* Locate position for insert new or increment e.  */
@@ -567,7 +567,7 @@
 }

 static void
-mp_factor_insert_ui (struct mp_factors *factors, unsigned long prime)
+mp_factor_insert_ui (struct mp_factors *factors, unsigned long int prime)
 {
   mpz_t pz;

@@ -1367,13 +1367,13 @@
 #endif

 static void
-factor_using_pollard_rho (uintmax_t n, unsigned long a, struct factors *factors)
+factor_using_pollard_rho (uintmax_t n, unsigned long int a,
+			  struct factors *factors)
 {
   uintmax_t x, z, y, P, t, ni, g;
-  unsigned long k, l;

-  k = 1;
-  l = 1;
+  unsigned long int k = 1;
+  unsigned long int l = 1;

   redcify (P, 1, n);
   addmod (x, P, P, n);		/* i.e., redcify(2) */
@@ -1407,7 +1407,7 @@
 	  z = x;
 	  k = l;
 	  l = 2 * l;
-	  for (unsigned long i = 0; i < k; i++)
+	  for (unsigned long int i = 0; i < k; i++)
 	    {
 	      x = mulredc (x, x, n, ni);
 	      addmod (x, x, a, n);
@@ -1446,14 +1446,13 @@
 }

 static void
-factor_using_pollard_rho2 (uintmax_t n1, uintmax_t n0, unsigned long a,
+factor_using_pollard_rho2 (uintmax_t n1, uintmax_t n0, unsigned long int a,
 			   struct factors *factors)
 {
   uintmax_t x1, x0, z1, z0, y1, y0, P1, P0, t1, t0, ni, g1, g0, r1m;
-  unsigned long k, l;

-  k = 1;
-  l = 1;
+  unsigned long int k = 1;
+  unsigned long int l = 1;

   redcify2 (P1, P0, 1, n1, n0);
   addmod2 (x1, x0, P1, P0, P1, P0, n1, n0); /* i.e., redcify(2) */
@@ -1489,7 +1488,7 @@
 	  z1 = x1; z0 = x0;
 	  k = l;
 	  l = 2 * l;
-	  for (unsigned long i = 0; i < k; i++)
+	  for (unsigned long int i = 0; i < k; i++)
 	    {
 	      x0 = mulredc2 (&r1m, x1, x0, x1, x0, n1, n0, ni);
 	      x1 = r1m;
@@ -1562,11 +1561,12 @@

 #if HAVE_GMP
 static void
-mp_factor_using_pollard_rho (mpz_t n, unsigned long a, struct mp_factors *factors)
+mp_factor_using_pollard_rho (mpz_t n, unsigned long int a,
+			     struct mp_factors *factors)
 {
   mpz_t x, z, y, P;
   mpz_t t, t2;
-  unsigned long long k, l;
+  unsigned long long int k, l;

   if (flag_verbose > 0)
     {
@@ -1608,7 +1608,7 @@
 	  mpz_set (z, x);
 	  k = l;
 	  l = 2 * l;
-	  for (unsigned long long i = 0; i < k; i++)
+	  for (unsigned long long int i = 0; i < k; i++)
 	    {
 	      mpz_mul (t, x, x);
 	      mpz_mod (x, t, n);

changeset:   120:92ea4621a776
user:        Jim Meyering <[email-masked]>
date:        Sat Sep 15 22:33:36 2012 +0200
files:       factor.c
description:
mp_prime_p: widen type of index to match the type of upper bound

In case we operate on a number with more than INT_MAX factors ;-)

 factor.c |  2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/factor.c b/factor.c
--- a/factor.c
+++ b/factor.c
@@ -1328,7 +1328,7 @@
       if (flag_prove_primality)
 	{
 	  is_prime = true;
-	  for (unsigned int i = 0; i < factors.nfactors && is_prime; i++)
+	  for (unsigned long int i = 0; i < factors.nfactors && is_prime; i++)
 	    {
 	      mpz_divexact (tmp, nm1, factors.p[i]);
 	      mpz_powm (tmp, a, tmp, n);

changeset:   119:c1b592ac3449
user:        Jim Meyering <[email-masked]>
date:        Sat Sep 15 22:22:40 2012 +0200
files:       factor.c
description:
mp_prime_p: use "unsigned long int" not "int" for result of mpz_scan1

 factor.c |  2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/factor.c b/factor.c
--- a/factor.c
+++ b/factor.c
@@ -1302,7 +1302,7 @@
   mpz_sub_ui (nm1, n, 1);

   /* Find q and k, where q is odd and n = 1 + 2**k * q.  */
-  int k = mpz_scan1 (nm1, 0);
+  unsigned long int k = mpz_scan1 (nm1, 0);
   mpz_tdiv_q_2exp (q, nm1, k);

   mpz_set_ui (a, 2);

changeset:   118:12940edfecc6
user:        Jim Meyering <[email-masked]>
date:        Sat Sep 15 22:21:02 2012 +0200
files:       factor.c
description:
reduce scope of functions and variables, favor unsigned types, use "bool"

 factor.c |  210 ++++++++++++++++++++++++++++++---------------------------------
 1 files changed, 99 insertions(+), 111 deletions(-)

diff --git a/factor.c b/factor.c
--- a/factor.c
+++ b/factor.c
@@ -89,6 +89,7 @@
 #include <ctype.h>
 #include <string.h>		/* for memmove */
 #include <unistd.h>		/* for getopt */
+#include <stdbool.h>

 #if HAVE_GMP
 #include <gmp.h>
@@ -160,7 +161,7 @@

 enum alg_type { ALG_POLLARD_RHO = 1, ALG_SQUFOF = 2 };

-enum alg_type alg;
+static enum alg_type alg;

 /* 2*3*5*7*11...*101 is 128 bits, and has 26 prime factors */
 #define MAX_NFACTS 26
@@ -182,7 +183,7 @@
 };
 #endif

-void factor (uintmax_t, uintmax_t, struct factors *);
+static void factor (uintmax_t, uintmax_t, struct factors *);

 #ifndef umul_ppmm
 #define umul_ppmm(w1, w0, u, v)						\
@@ -309,7 +310,7 @@
     uintmax_t _rh, _rl, _nh, _nl;					\
     umul_ppmm (_rh, _rl, (a), (b));					\
     _nh = n; _nl = 0;							\
-    for (int _i = W_TYPE_SIZE; _i != 0; _i--)				\
+    for (unsigned int _i = W_TYPE_SIZE; _i != 0; _i--)			\
       {									\
 	rsh2 (_nh, _nl, _nh, _nl, 1);					\
 	if (ge2 (_rh, _rl, _nh, _nl))					\
@@ -352,10 +353,10 @@

 /* Compute r = a mod d, where r = <*t1,retval>, a = <a1,a0>, d = <d1,d0>.
    Requires that d1 != 0.  */
-uintmax_t
+static uintmax_t
 mod2 (uintmax_t *r1, uintmax_t a1, uintmax_t a0, uintmax_t d1, uintmax_t d0)
 {
-  int cntd, cnta, cnt;
+  int cntd, cnta;

   assert (d1 != 0);

@@ -367,7 +368,7 @@

   count_leading_zeros (cntd, d1);
   count_leading_zeros (cnta, a1);
-  cnt = cntd - cnta;
+  int cnt = cntd - cnta;
   lsh2 (d1, d0, d1, d0, cnt);
   for (int i = 0; i < cnt; i++)
     {
@@ -380,7 +381,7 @@
   return a0;
 }

-uintmax_t
+static uintmax_t
 gcd_odd (uintmax_t a, uintmax_t b)
 {
   if ( (b & 1) == 0)
@@ -418,7 +419,7 @@
     }
 }

-uintmax_t
+static uintmax_t
 gcd2_odd (uintmax_t *r1, uintmax_t a1, uintmax_t a0, uintmax_t b1, uintmax_t b0)
 {
   while ((a0 & 1) == 0)
@@ -456,16 +457,16 @@
   return a0;
 }

-void
+static void
 factor_insert_multiplicity (struct factors *factors,
 			    uintmax_t prime, unsigned int m)
 {
-  int nfactors = factors->nfactors;
+  unsigned int nfactors = factors->nfactors;
   uintmax_t *p = factors->p;
   unsigned char *e = factors->e;
-  int i;

   /* Locate position for insert new or increment e.  */
+  int i;
   for (i = nfactors - 1; i >= 0; i--)
     {
       if (p[i] <= prime)
@@ -491,7 +492,7 @@

 #define factor_insert(f, p) factor_insert_multiplicity(f, p, 1)

-void
+static void
 factor_insert_large (struct factors *factors,
 		     uintmax_t p1, uintmax_t p0)
 {
@@ -506,9 +507,9 @@
 }

 #if HAVE_GMP
-void mp_factor (mpz_t, struct mp_factors *);
+static void mp_factor (mpz_t, struct mp_factors *);

-void
+static void
 mp_factor_init (struct mp_factors *factors)
 {
   factors->p = malloc (1);
@@ -516,7 +517,7 @@
   factors->nfactors = 0;
 }

-void
+static void
 mp_factor_clear (struct mp_factors *factors)
 {
   for (unsigned int i = 0; i < factors->nfactors; i++)
@@ -526,10 +527,10 @@
   free (factors->e);
 }

-void
+static void
 mp_factor_insert (struct mp_factors *factors, mpz_t prime)
 {
-  long    nfactors  = factors->nfactors;
+  unsigned long nfactors = factors->nfactors;
   mpz_t         *p  = factors->p;
   unsigned long *e  = factors->e;
   long i;
@@ -565,7 +566,7 @@
     }
 }

-void
+static void
 mp_factor_insert_ui (struct mp_factors *factors, unsigned long prime)
 {
   mpz_t pz;
@@ -606,10 +607,10 @@
 #undef P

 /* This flag is honoured just in the GMP code. */
-int flag_verbose = 0;
+static int flag_verbose = 0;

 /* Prove primality or run probabilistic tests.  */
-int flag_prove_primality = 1;
+static int flag_prove_primality = 1;

 /* Number of Miller-Rabin tests to run when not proving primality. */
 #define MR_REPS 25
@@ -617,7 +618,7 @@
 #define LIKELY(cond)    __builtin_expect ((cond) != 0, 1)
 #define UNLIKELY(cond)  __builtin_expect ((cond) != 0, 0)

-void
+static void
 factor_insert_refind (struct factors *factors, uintmax_t p, unsigned int i,
 		      unsigned int off)
 {
@@ -659,16 +660,13 @@
    order, and the non-multiples of p onto the range lim < q < B.
  */

-uintmax_t
+static uintmax_t
 factor_using_division (uintmax_t *t1p, uintmax_t t1, uintmax_t t0,
 		       struct factors *factors)
 {
-  unsigned int i;
-  uintmax_t p;
-
   if (t0 % 2 == 0)
     {
-      int cnt;
+      unsigned int cnt;

       if (t0 == 0)
 	{
@@ -686,7 +684,8 @@
       factor_insert_multiplicity (factors, 2, cnt);
     }

-  p = 3;
+  uintmax_t p = 3;
+  unsigned int i;
   for (i = 0; t1 > 0 && i < PRIMES_PTAB_ENTRIES; i++)
     {
       for (;;)
@@ -724,9 +723,7 @@
   for (; i < PRIMES_PTAB_ENTRIES; i += 8)
     {
       uintmax_t q;
-      const struct primes_dtab *pd;
-
-      pd = &primes_dtab[i];
+      const struct primes_dtab *pd = &primes_dtab[i];
       DIVBLOCK(0);
       DIVBLOCK(1);
       DIVBLOCK(2);
@@ -745,7 +742,7 @@
 }

 #if HAVE_GMP
-void
+static void
 mp_factor_using_division (mpz_t t, struct mp_factors *factors)
 {
   mpz_t q;
@@ -882,7 +879,7 @@
   } while (0)

 /* Modular two-word multiplication, r = a * b mod m, with mi = m^(-1) mod B.
-   Both a and b has to be in redc form, the result will be in redc form too. */
+   Both a and b must be in redc form, the result will be in redc form too. */
 inline uintmax_t
 mulredc (uintmax_t a, uintmax_t b, uintmax_t m, uintmax_t mi)
 {
@@ -899,9 +896,9 @@
 }

 /* Modular two-word multiplication, r = a * b mod m, with mi = m^(-1) mod B.
-   Both a and b has to be in redc form, the result will be in redc form too.
+   Both a and b must be in redc form, the result will be in redc form too.
    For performance reasons, the most significant bit of m must be clear. */
-uintmax_t
+static uintmax_t
 mulredc2 (uintmax_t *r1p,
 	  uintmax_t a1, uintmax_t a0, uintmax_t b1, uintmax_t b0,
 	  uintmax_t m1, uintmax_t m0, uintmax_t mi)
@@ -969,12 +966,10 @@
   return r0;
 }

-uintmax_t
+static uintmax_t
 powm (uintmax_t b, uintmax_t e, uintmax_t n, uintmax_t ni, uintmax_t one)
 {
-  uintmax_t y;
-
-  y = one;
+  uintmax_t y = one;

   if (e & 1)
     y = b;
@@ -991,7 +986,7 @@
   return y;
 }

-uintmax_t
+static uintmax_t
 powm2 (uintmax_t *r1m,
        const uintmax_t *bp, const uintmax_t *ep, const uintmax_t *np,
        uintmax_t ni, const uintmax_t *one)
@@ -1032,32 +1027,30 @@
   return r0;
 }

-int
+static bool
 millerrabin (uintmax_t n, uintmax_t ni, uintmax_t b, uintmax_t q,
 	     unsigned int k, uintmax_t one)
 {
-  uintmax_t y, nm1;
+  uintmax_t y = powm (b, q, n, ni, one);

-  y = powm (b, q, n, ni, one);
-
-  nm1 = n - one;	/* -1, but in redc representation. */
+  uintmax_t nm1 = n - one;	/* -1, but in redc representation. */

   if (y == one || y == nm1)
-    return 1;
+    return true;

   for (unsigned int i = 1; i < k; i++)
     {
       y = mulredc (y, y, n, ni);

       if (y == nm1)
-	return 1;
+	return true;
       if (y == one)
-	return 0;
+	return false;
     }
-  return 0;
+  return false;
 }

-int
+static bool
 millerrabin2 (const uintmax_t *np, uintmax_t ni, const uintmax_t *bp,
 	      const uintmax_t *qp, unsigned int k, const uintmax_t *one)
 {
@@ -1067,12 +1060,12 @@
   y1 = r1m;

   if (y0 == one[0] && y1 == one[1])
-    return 1;
+    return true;

   sub_ddmmss (nm1_1, nm1_0, np[1], np[0], one[1], one[0]);

   if (y0 == nm1_0 && y1 == nm1_1)
-    return 1;
+    return true;

   for (unsigned int i = 1; i < k; i++)
     {
@@ -1080,66 +1073,65 @@
       y1 = r1m;

       if (y0 == nm1_0 && y1 == nm1_1)
-	return 1;
+	return true;
       if (y0 == one[0] && y1 == one[1])
-	return 0;
+	return false;
     }
-  return 0;
+  return false;
 }

 #if HAVE_GMP
-static int
+static bool
 mp_millerrabin (mpz_srcptr n, mpz_srcptr nm1, mpz_ptr x, mpz_ptr y,
 		mpz_srcptr q, unsigned long int k)
 {
-  unsigned long int i;
-
   mpz_powm (y, x, q, n);

   if (mpz_cmp_ui (y, 1) == 0 || mpz_cmp (y, nm1) == 0)
-    return 1;
+    return true;

-  for (i = 1; i < k; i++)
+  for (unsigned long int i = 1; i < k; i++)
     {
       mpz_powm_ui (y, y, 2, n);
       if (mpz_cmp (y, nm1) == 0)
-	return 1;
+	return true;
       if (mpz_cmp_ui (y, 1) == 0)
-	return 0;
+	return false;
     }
-  return 0;
+  return false;
 }
 #endif

 /* Lucas' prime test.  The number of iterations vary greatly, up to a few dozen
    have been observed.  The average seem to be about 2.  */
-int
+static bool
 prime_p (uintmax_t n)
 {
-  int k, is_prime;
-  uintmax_t q, a, a_prim, one, ni;
+  int k;
+  bool is_prime;
+  uintmax_t a_prim, one, ni;
   struct factors factors;

   if (n <= 1)
-    return 0;
+    return false;

   /* We have already casted out small primes. */
   if (n < (uintmax_t) FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME)
-    return 1;
+    return true;

   /* Precomputation for Miller-Rabin.  */
-  q = n - 1;
+  uintmax_t q = n - 1;
   for (k = 0; (q & 1) == 0; k++)
     q >>= 1;

-  a = 2;
+  uintmax_t a = 2;
   binv (ni, n);			/* ni <- 1/n mod B */
   redcify (one, 1, n);
   addmod (a_prim, one, one, n);	/* i.e., redcify a = 2 */

   /* Perform a Miller-Rabin test, finds most composites quickly.  */
   if (!millerrabin (n, ni, a_prim, q, k, one))
-    return 0;
+    return false;

   if (flag_prove_primality)
     {
@@ -1151,12 +1143,10 @@
      number composite.  */
   for (unsigned int r = 0; r < PRIMES_PTAB_ENTRIES; r++)
     {
-      int i;
-
       if (flag_prove_primality)
 	{
-	  is_prime = 1;
-	  for (i = 0; i < factors.nfactors && is_prime; i++)
+	  is_prime = true;
+	  for (unsigned int i = 0; i < factors.nfactors && is_prime; i++)
 	    {
 	      is_prime = powm (a_prim, (n - 1) / factors.p[i], n, ni, one) != one;
 	    }
@@ -1168,7 +1158,7 @@
 	}

       if (is_prime)
-	return 1;
+	return true;

       a += primes_diff[r];	/* Establish new base.  */

@@ -1185,18 +1175,17 @@
       }

       if (!millerrabin (n, ni, a_prim, q, k, one))
-	return 0;
+	return false;
     }

   fprintf (stderr, "Lucas prime test failure.  This should not happen\n");
   abort ();
 }

-int
+static bool
 prime2_p (uintmax_t n1, uintmax_t n0)
 {
   uintmax_t q[2], nm1[2];
-  uintmax_t a;
   uintmax_t a_prim[2];
   uintmax_t one[2];
   uintmax_t na[2];
@@ -1223,7 +1212,7 @@
       rsh2 (q[1], q[0], nm1[1], nm1[0], k);
     }

-  a = 2;
+  uintmax_t a = 2;
   binv (ni, n0);
   redcify2 (one[1], one[0], 1, n1, n0);
   addmod2 (a_prim[1], a_prim[0], one[1], one[0], one[1], one[0], n1, n0);
@@ -1233,7 +1222,7 @@
   na[1] = n1;

   if (!millerrabin2 (na, ni, a_prim, q, k, one))
-    return 0;
+    return false;

   if (flag_prove_primality)
     {
@@ -1245,12 +1234,12 @@
      number composite.  */
   for (unsigned int r = 0; r < PRIMES_PTAB_ENTRIES; r++)
     {
-      int i, is_prime;
+      bool is_prime;
       uintmax_t e[2], y[2];

       if (flag_prove_primality)
 	{
-	  is_prime = 1;
+	  is_prime = true;
 	  if (factors.plarge[1])
 	    {
 	      uintmax_t pi;
@@ -1260,7 +1249,7 @@
 	      y[0] = powm2 (&y[1], a_prim, e, na, ni, one);
 	      is_prime = (y[0] != one[0] || y[1] != one[1]);
 	    }
-	  for (i = 0; i < factors.nfactors && is_prime; i++)
+	  for (unsigned int i = 0; i < factors.nfactors && is_prime; i++)
 	    {
 	      /* FIXME: We always have the factor 2. Do we really need to handle it
 		 here? We have done the same powering as part of millerrabin. */
@@ -1279,13 +1268,13 @@
 	}

       if (is_prime)
-	return 1;
+	return true;

       a += primes_diff[r];	/* Establish new base.  */
       redcify2 (a_prim[1], a_prim[0], a, n1, n0);

       if (!millerrabin2 (na, ni, a_prim, q, k, one))
-	return 0;
+	return false;
     }

   fprintf (stderr, "Lucas prime test failure.  This should not happen\n");
@@ -1293,19 +1282,19 @@
 }

 #if HAVE_GMP
-int
+static bool
 mp_prime_p (mpz_t n)
 {
-  int k, is_prime;
+  bool is_prime;
   mpz_t q, a, nm1, tmp;
   struct mp_factors factors;

   if (mpz_cmp_ui (n, 1) <= 0)
-    return 0;
+    return false;

   /* We have already casted out small primes. */
   if (mpz_cmp_ui (n, (long) FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME) < 0)
-    return 1;
+    return true;

   mpz_inits (q, a, nm1, tmp, NULL);

@@ -1313,7 +1302,7 @@
   mpz_sub_ui (nm1, n, 1);

   /* Find q and k, where q is odd and n = 1 + 2**k * q.  */
-  k = mpz_scan1 (nm1, 0);
+  int k = mpz_scan1 (nm1, 0);
   mpz_tdiv_q_2exp (q, nm1, k);

   mpz_set_ui (a, 2);
@@ -1321,7 +1310,7 @@
   /* Perform a Miller-Rabin test, finds most composites quickly.  */
   if (!mp_millerrabin (n, nm1, a, tmp, q, k))
     {
-      is_prime = 0;
+      is_prime = false;
       goto ret2;
     }

@@ -1338,7 +1327,7 @@
     {
       if (flag_prove_primality)
 	{
-	  is_prime = 1;
+	  is_prime = true;
 	  for (unsigned int i = 0; i < factors.nfactors && is_prime; i++)
 	    {
 	      mpz_divexact (tmp, nm1, factors.p[i]);
@@ -1359,7 +1348,7 @@

       if (!mp_millerrabin (n, nm1, a, tmp, q, k))
 	{
-	  is_prime = 0;
+	  is_prime = false;
 	  goto ret1;
 	}
     }
@@ -1377,11 +1366,11 @@
 }
 #endif

-void
+static void
 factor_using_pollard_rho (uintmax_t n, unsigned long a, struct factors *factors)
 {
   uintmax_t x, z, y, P, t, ni, g;
-  unsigned long k, l, i;
+  unsigned long k, l;

   k = 1;
   l = 1;
@@ -1418,7 +1407,7 @@
 	  z = x;
 	  k = l;
 	  l = 2 * l;
-	  for (i = 0; i < k; i++)
+	  for (unsigned long i = 0; i < k; i++)
 	    {
 	      x = mulredc (x, x, n, ni);
 	      addmod (x, x, a, n);
@@ -1456,12 +1445,12 @@
     }
 }

-void
+static void
 factor_using_pollard_rho2 (uintmax_t n1, uintmax_t n0, unsigned long a,
 			   struct factors *factors)
 {
   uintmax_t x1, x0, z1, z0, y1, y0, P1, P0, t1, t0, ni, g1, g0, r1m;
-  unsigned long k, l, i;
+  unsigned long k, l;

   k = 1;
   l = 1;
@@ -1500,7 +1489,7 @@
 	  z1 = x1; z0 = x0;
 	  k = l;
 	  l = 2 * l;
-	  for (i = 0; i < k; i++)
+	  for (unsigned long i = 0; i < k; i++)
 	    {
 	      x0 = mulredc2 (&r1m, x1, x0, x1, x0, n1, n0, ni);
 	      x1 = r1m;
@@ -1572,12 +1561,12 @@
 }

 #if HAVE_GMP
-void
+static void
 mp_factor_using_pollard_rho (mpz_t n, unsigned long a, struct mp_factors *factors)
 {
   mpz_t x, z, y, P;
   mpz_t t, t2;
-  unsigned long long k, l, i;
+  unsigned long long k, l;

   if (flag_verbose > 0)
     {
@@ -1619,7 +1608,7 @@
 	  mpz_set (z, x);
 	  k = l;
 	  l = 2 * l;
-	  for (i = 0; i < k; i++)
+	  for (unsigned long long i = 0; i < k; i++)
 	    {
 	      mpz_mul (t, x, x);
 	      mpz_mod (x, t, n);
@@ -1859,7 +1848,7 @@
 #endif

-void
+static void
 factor_using_squfof (uintmax_t n1, uintmax_t n0, struct factors *factors)
 {
   /* Uses algorithm and notation from
@@ -2114,7 +2103,7 @@
   exit (EXIT_FAILURE);
 }

-void
+static void
 factor (uintmax_t t1, uintmax_t t0, struct factors *factors)
 {
   factors->nfactors = 0;
@@ -2149,7 +2138,7 @@
 }

 #if HAVE_GMP
-void
+static void
 mp_factor (mpz_t t, struct mp_factors *factors)
 {
   mp_factor_init (factors);
@@ -2173,7 +2162,7 @@
 }
 #endif

-int
+static int
 strto2uintmax (uintmax_t *hip, uintmax_t *lop, const char *s)
 {
   int errcode;
@@ -2226,7 +2215,7 @@
   return errcode;
 }

-void
+static void
 print_uintmaxes (uintmax_t t1, uintmax_t t0)
 {
   uintmax_t q, r;
@@ -2245,7 +2234,7 @@
     }
 }

-void
+static void
 factor_one (const char *input)
 {
   uintmax_t t1, t0;
@@ -2353,7 +2342,6 @@
 int
 main (int argc, char *argv[])
 {
-  int i;
   int c;

   alg = ALG_POLLARD_RHO;	/* Default to Pollard rho */
@@ -2380,7 +2368,7 @@
 #endif

   if (optind < argc)
-    for (i = optind; i < argc; i++)
+    for (int i = optind; i < argc; i++)
       factor_one (argv[i]);
   else
     {
@@ -2396,7 +2384,7 @@
     {
       double acc_f;
       printf ("q  freq.  cum. freq.(total: %d)\n", q_freq[0]);
-      for (i = 1, acc_f = 0.0; i <= Q_FREQ_SIZE; i++)
+      for (unsigned int i = 1, acc_f = 0.0; i <= Q_FREQ_SIZE; i++)
 	{
 	  double f = (double) q_freq[i] / q_freq[0];
 	  acc_f += f;