Uprating of the passphrase pixie.

[u/mdw/catacomb] / pgen-safe.c

diff --git a/pgen-safe.c b/pgen-safe.c
index 32b91e3..115f7b4 100644 (file)
--- 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.5 2004/04/08 01:36:15 mdw Exp $
  *
  * Safe prime generation
  *
@@ -27,14 +27,6 @@
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: pgen-safe.c,v $
- * Revision 1.1  1999/12/22 16:01:34  mdw
- * Find `safe' primes (i.e., %$p = 2q + 1$%).
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include "mp.h"
@@ -52,37 +44,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, p, 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@ --- *