Find `safe' primes (i.e., %$p = 2q + 1$%).

diff --git a/pgen-safe.c b/pgen-safe.c
new file mode 100644 (file)
index 0000000..32b91e3
--- /dev/null
+++ b/pgen-safe.c
@@ -0,0 +1,119 @@
+/* -*-c-*-
+ *
+ * $Id: pgen-safe.c,v 1.1 1999/12/22 16:01:34 mdw Exp $
+ *
+ * Safe prime generation
+ *
+ * (c) 1999 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------* 
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ * 
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Library General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * 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"
+#include "mprand.h"
+#include "pgen.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @pgen_safestep@ --- *
+ *
+ * Steps two numbers, %$q$% and %$p = 2q + 1$%, such that neither has any
+ * small factors.  %$p$% is put in the event block.
+ */
+
+int pgen_safestep(int rq, pgen_event *ev, void *p)
+{
+  pgen_safestepctx *c = p;
+  int prc = PGEN_ABORT, qrc;
+
+  switch (rq) {
+    case PGEN_BEGIN: {
+      mp *p = mp_split(MP_COPY(ev->m));
+      mp *q;
+      p->v[0] |= 3;
+      q = mp_lsr(MP_NEW, p, 1);
+      qrc = pfilt_create(&c->q, q);
+      prc = pfilt_create(&c->p, p);
+      mp_drop(p);
+      mp_drop(q);
+    } goto step;
+    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;
+      break;
+    case PGEN_DONE:
+      pfilt_destroy(&c->q);
+      pfilt_destroy(&c->p);
+      break;
+  }
+  return (prc);
+}
+
+/* --- @pgen_safetest@ --- *
+ *
+ * Applies Rabin-Miller tests to %$p$% and %$q$%.
+ */
+
+int pgen_safetest(int rq, pgen_event *ev, void *p)
+{
+  pgen_safetestctx *c = p;
+  int rc = PGEN_ABORT;
+
+  switch (rq) {
+    case PGEN_BEGIN:
+      rabin_create(&c->q, c->c.q.m);
+      rabin_create(&c->p, c->c.p.m);
+      rc = PGEN_TRY;
+      break;
+    case PGEN_TRY: {
+      mp *m = mprand_range(MP_NEW, c->c.q.m, ev->r, 0);
+      rc = rabin_test(&c->p, m);
+      if (rc == PGEN_PASS)
+       rc = rabin_test(&c->q, m);
+      mp_drop(m);
+    } break;
+    case PGEN_DONE:
+      rabin_destroy(&c->q);
+      rabin_destroy(&c->p);
+      break;
+  }
+  return (rc);
+}
+
+/*----- That's all, folks -------------------------------------------------*/