[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#12350: Composites identified as primes in factor.c (when HAVE_GMP)
|
From: |
Jim Meyering |
|
Subject: |
bug#12350: Composites identified as primes in factor.c (when HAVE_GMP) |
|
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 <address@hidden>
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 <address@hidden>
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 <address@hidden>
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 <address@hidden>
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;
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), (continued)
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/06
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/06
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/13
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/13
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/13
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/13
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/13
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP),
Jim Meyering <=
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/16
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/16
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/18
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/18
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/18