X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/1c42b46256f9cd956c7e7fe0fb98b47f7ac1d804..c760149fcb65296defd1af967fbfa098bd83143a:/pgen-safe.c

diff --git a/pgen-safe.c b/pgen-safe.c
index 32b91e3..b680ae4 100644
--- a/pgen-safe.c
+++ b/pgen-safe.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: pgen-safe.c,v 1.1 1999/12/22 16:01:34 mdw Exp $
+ * $Id: pgen-safe.c,v 1.3 2000/06/17 11:52:36 mdw Exp $
  *
  * Safe prime generation
  *
@@ -30,6 +30,12 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: pgen-safe.c,v $
+ * Revision 1.3  2000/06/17 11:52:36  mdw
+ * Signal a pgen abort if the jump and base share a common factor.
+ *
+ * Revision 1.2  2000/02/12 18:21:03  mdw
+ * Overhaul of key management (again).
+ *
  * Revision 1.1  1999/12/22 16:01:34  mdw
  * Find `safe' primes (i.e., %$p = 2q + 1$%).
  *
@@ -52,37 +58,123 @@
 int pgen_safestep(int rq, pgen_event *ev, void *p)
 {
   pgen_safestepctx *c = p;
-  int prc = PGEN_ABORT, qrc;
+  int rc = PGEN_ABORT, qrc = 0;
 
   switch (rq) {
+
+    /* --- Set up the contexts --- */
+
     case PGEN_BEGIN: {
       mp *p = mp_split(MP_COPY(ev->m));
       mp *q;
       p->v[0] |= 3;
       q = mp_lsr(MP_NEW, p, 1);
+      rc = pfilt_create(&c->p, p);
       qrc = pfilt_create(&c->q, q);
-      prc = pfilt_create(&c->p, p);
-      mp_drop(p);
-      mp_drop(q);
-    } goto step;
+      mp_drop(p); mp_drop(q);
+    } break;
+
+    /* --- Step along --- */
+
     case PGEN_TRY:
-    again:
-      qrc = pfilt_step(&c->q, 2);
-      prc = pfilt_step(&c->p, 4);
-    step:
-      if (qrc == PGEN_FAIL || prc == PGEN_FAIL)
-	goto again;
       mp_drop(ev->m);
-      ev->m = MP_COPY(c->p.m);
-      if (qrc == PGEN_TRY)
-	prc = PGEN_TRY;
+      rc = pfilt_step(&c->p, 4);
+      qrc = pfilt_step(&c->q, 2);
+      break;
+
       break;
+
+    /* --- Tidy the toys away --- */
+
     case PGEN_DONE:
       pfilt_destroy(&c->q);
       pfilt_destroy(&c->p);
+      return (PGEN_DONE);
+  }
+
+  /* --- Continue stepping if necessary --- */
+
+  while (rc == PGEN_FAIL || qrc == PGEN_FAIL) {
+    rc = pfilt_step(&c->p, 4);
+    qrc = pfilt_step(&c->q, 2);
+  }
+
+  ev->m = MP_COPY(c->p.m);
+  if (qrc == PGEN_TRY)
+    rc = PGEN_TRY;
+  return (rc);
+}
+
+/* --- @pgen_safejump@ --- *
+ *
+ * Jumps two numbers, %$q$% and %$p = 2q + 1$% such that neither has any
+ * small factors.
+ */
+
+int pgen_safejump(int rq, pgen_event *ev, void *p)
+{
+  pgen_safejumpctx *j = p;
+  int rc = PGEN_ABORT, qrc = 0;
+
+  switch (rq) {
+
+    /* --- Set up the jump contexts --- *
+     *
+     * The jump in @j.q@ is congruent to 2 (mod 4); see @strongprime_setup@.
+     * If @p@ is initially 1 (mod 4) then add @j.q@.  Then double @j.q@ to
+     * ensure that the step is 0 (mod 4).  Ensure that @jq@ and @q@ don't
+     * have any common factors.
+     */
+
+    case PGEN_BEGIN: {
+      mp *p = ev->m;
+      mp *q;
+      mp *g = MP_NEW;
+      if ((p->v[0] & 3) != 3)
+	p = mp_add(p, p, j->jq.m);
+      q = mp_lsr(MP_NEW, p, 1);
+      mp_gcd(&g, 0, 0, q, j->jq.m);
+      if (MP_CMP(g, >, MP_ONE)) {
+	ev->m = p;
+	mp_drop(q);
+	mp_drop(g);
+	return (PGEN_ABORT);
+      }
+      mp_drop(g);
+      rc = pfilt_create(&j->p, p);
+      pfilt_muladd(&j->jp, &j->jq, 2, 0);
+      qrc = pfilt_create(&j->q, q);
+      mp_drop(p);
+      mp_drop(q);
+    } break;
+
+    /* --- Step on one place --- */
+
+    case PGEN_TRY:
+      mp_drop(ev->m);
+      rc = pfilt_jump(&j->p, &j->jp);
+      qrc = pfilt_jump(&j->q, &j->jq);
       break;
+
+    /* --- Tidy everything up --- */
+
+    case PGEN_DONE:
+      pfilt_destroy(&j->jp);
+      pfilt_destroy(&j->p);
+      pfilt_destroy(&j->q);
+      return (PGEN_DONE);
+  }
+
+  /* --- Step on while @p@ or @q@ have small factors --- */
+
+  while (rc == PGEN_FAIL || qrc == PGEN_FAIL) {
+    rc = pfilt_jump(&j->p, &j->jp);
+    qrc = pfilt_jump(&j->q, &j->jq);
   }
-  return (prc);
+  ev->m = MP_COPY(j->p.m);
+  if (qrc == PGEN_TRY)
+    rc = PGEN_TRY;
+  return (rc);
 }
 
 /* --- @pgen_safetest@ --- *