- pgen_gcdstepctx g;
- mp *phi = MP_NEW;
-
- /* --- Bits of initialization --- */
-
- rp->e = mp_fromulong(MP_NEW, 0x10001);
- rp->d = MP_NEW;
-
- /* --- Generate strong primes %$p$% and %$q$% --- *
- *
- * Constrain the GCD of @q@ to ensure that overly small private exponents
- * are impossible. Current results suggest that if %$d < n^{0.29}$% then
- * it can be guessed fairly easily. This implementation is rather more
- * conservative about that sort of thing.
- */
-
-again:
- if ((rp->p = strongprime("p", MP_NEWSEC, nbits/2, r, n, event, ectx)) == 0)
- goto fail_p;
-
- /* --- Do painful fiddling with GCD steppers --- *
- *
- * Also, arrange that %$q \ge \lceil 2^{N-1}/p \rceil$%, so that %$p q$%
- * has the right length.
- */
-
- {
- mp *q;
- mp *t = MP_NEW, *u = MP_NEW;
- rabin rb;
-
- if ((q = strongprime_setup("q", MP_NEWSEC, &g.jp, nbits / 2,
- r, n, event, ectx)) == 0)
- goto fail_q;
- t = mp_lsl(t, MP_ONE, nbits - 1);
- mp_div(&t, &u, t, rp->p);
- if (!MP_ZEROP(u)) t = mp_add(t, t, MP_ONE);
- if (MP_CMP(q, <, t)) q = mp_leastcongruent(q, t, q, g.jp.m);
- mp_drop(t);
-
- g.r = mp_lsr(MP_NEW, rp->p, 1);
- g.g = MP_NEW;
- g.max = MP_256;
- q = pgen("q", q, q, event, ectx, n, pgen_gcdstep, &g,
- rabin_iters(nbits/2), pgen_test, &rb);
- pfilt_destroy(&g.jp);
- mp_drop(g.r);
- if (!q) {
- mp_drop(g.g);
- if (n)
- goto fail_q;
- mp_drop(rp->p);
- goto again;
- }
- rp->q = q;
+ pgen_jumpctx jctx; pfilt j;
+ mp *p = MP_NEWSEC, *t = MP_NEW, *u = MP_NEW;
+ rabin rb;
+ mpw p3, j3, a;
+ int rc = -1;
+
+ j.m = MP_NEW;
+
+ /* Find a start position for the search. */
+ p = strongprime_setup(name, p, &j, nbits, r, nsteps, event, ectx);
+ if (!p) goto end;
+
+ /* Special handling for e = 3. */
+ if (MP_EQ(e, MP_THREE)) {
+ /* We must have p == 2 (mod 3): if p == 0 (mod 3) then p is not prime; if
+ * p == 1 (mod 3) then e|(p - 1). So fiddle the start position and jump
+ * context to allow for this.
+ */
+
+ /* Figure out the residues of the start position and jump. */
+ mp_div(0, &t, p, MP_THREE); p3 = t->v[0];
+ mp_div(0, &u, j.m, MP_THREE); j3 = u->v[0];
+
+ /* If the jump is a multiple of three already, then we're stuffed unless
+ * the start position is 2 (mod 3). This shouldn't happen, since the
+ * jump should be twice a multiple of two large primes, which will be
+ * nonzero (mod 3).
+ *
+ * Set a = (2 - p) j mod 3. Then p' = p + a j == p (mod j), and p' ==
+ * p + (2 - p) j^2 == 2 (mod 3).
+ */
+ assert(j3 != 0);
+ a = ((2 - p3)*j3)%3;
+ if (a == 1) p = mp_add(p, p, j.m);
+ else if (a == 2) { t = mp_lsl(t, j.m, 1); p = mp_add(p, p, t); }
+
+ /* Finally, multiply j by three to make sure it preserves this
+ * congruence.
+ */
+ pfilt_muladd(&j, &j, 3, 0);