math/pfilt.c (pfilt_jump): Fix off-by-one error in reduction.

Oh, dear.  This is quite a bad one.  The loop added the residues for the
jump to the candidate, and reduced each if the result was strictly
higher than the modulus.  It then reports failure (or immediate success)
if any residue is zero, otherwise reporting a candidate for subsequent
testing.  Obviously, this is a stupid bug, with the result that,
effectively, every step reports a candidate for further testing.

This bug has two bad consequences.

  * Candidates with small factors aren't weeded out, so prime searching
    takes an unnecessarily long time.  I'd spotted this, but didn't have
    a way in to investigate the problem.

  * Candidates which actually have small factors, but are in fact below
    the `smallenough' threshold, are reported as being verified as
    prime, so the overall procedure erroneously returns known
    composites.

diff --git a/math/pfilt.c b/math/pfilt.c
index de049cbe02f36c872a4189a0bc637bb6e34e37a7..a4c9856b420224a0a17824afd9478e8f8b8fcadb 100644 (file)
--- a/math/pfilt.c
+++ b/math/pfilt.c
@@ -304,7 +304,7 @@ int pfilt_jump(pfilt *p, const pfilt *j)
 
   for (i = 0; i < NPRIME; i++) {
     p->r[i] = p->r[i] + j->r[i];
-    if (p->r[i] > primetab[i])
+    if (p->r[i] >= primetab[i])
       p->r[i] -= primetab[i];
     if (!p->r[i] && rc == PGEN_TRY) {
       if (MP_LEN(p->m) == 1 && p->m->v[0] == primetab[i])