/* -*-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
*
* 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"
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@ --- *