From 581c854ebf69254c5ae527a789994a0fc70368e7 Mon Sep 17 00:00:00 2001 From: mdw Date: Wed, 22 Dec 1999 16:01:11 +0000 Subject: [PATCH] Same file, completely different code. Main interface for new prime- search system. --- pgen.c | 470 +++++++++++++++++++++++++++++++++-------------------------------- pgen.h | 248 +++++++++++++++++++++++----------- 2 files changed, 412 insertions(+), 306 deletions(-) diff --git a/pgen.c b/pgen.c index e9a5e75..5b9fd9e 100644 --- a/pgen.c +++ b/pgen.c @@ -1,8 +1,8 @@ /* -*-c-*- * - * $Id: pgen.c,v 1.3 1999/12/10 23:28:35 mdw Exp $ + * $Id: pgen.c,v 1.4 1999/12/22 16:01:11 mdw Exp $ * - * Finding and testing prime numbers + * Prime generation glue * * (c) 1999 Straylight/Edgeware */ @@ -30,249 +30,287 @@ /*----- Revision history --------------------------------------------------* * * $Log: pgen.c,v $ - * Revision 1.3 1999/12/10 23:28:35 mdw - * Track suggested destination changes. - * - * Revision 1.2 1999/11/20 22:23:05 mdw - * Add multiply-and-add function for Diffie-Hellman safe prime generation. - * - * Revision 1.1 1999/11/19 13:17:57 mdw - * Prime number generator and tester. + * Revision 1.4 1999/12/22 16:01:11 mdw + * Same file, completely different code. Main interface for new prime- + * search system. * */ /*----- Header files ------------------------------------------------------*/ +#include +#include +#include +#include + +#include "fibrand.h" +#include "grand.h" #include "mp.h" -#include "mpmont.h" +#include "mprand.h" #include "pgen.h" -#include "ptab.h" +#include "pfilt.h" #include "rabin.h" -/*----- Main code ---------------------------------------------------------*/ +/*----- Standard prime filter ---------------------------------------------*/ -/* --- @pgen_create@ --- * - * - * Arguments: @pgen *p@ = pointer to prime generation context - * @mp *m@ = pointer to initial number to test - * - * Returns: One of the @PGEN@ constants above. - * - * Use: Tests an initial number for primality by computing its - * residue modulo various small prime numbers. This is fairly - * quick, but not particularly certain. If a @PGEN_MAYBE@ - * result is returned, perform Rabin-Miller tests to confirm. - */ +/* --- @pgen_filter@ --- */ -int pgen_create(pgen *p, mp *m) +int pgen_filter(int rq, pgen_event *ev, void *p) { - int rc = PGEN_MAYBE; - int i; - mp *r = MP_NEW; - mpw qw; - mp q; - - /* --- Take a copy of the number --- */ - - mp_shrink(m); - p->m = MP_COPY(m); - - /* --- Fill in the residues --- */ - - mp_build(&q, &qw, &qw + 1); - for (i = 0; i < NPRIME; i++) { - qw = ptab[i]; - mp_div(0, &r, m, &q); - p->r[i] = r->v[0]; - if (!p->r[i] && rc == PGEN_MAYBE) { - if (MP_LEN(m) == 1 && m->v[0] == ptab[i]) - rc = PGEN_PRIME; + pgen_filterctx *f = p; + int rc = PGEN_ABORT; + + switch (rq) { + case PGEN_BEGIN: + rc = pfilt_create(&f->f, ev->m); + mp_drop(ev->m); + break; + case PGEN_TRY: + mp_drop(ev->m); + if (!((f->step | f->f.m->v[0]) & 1)) + rc = pfilt_step(&f->f, 1); else - rc = PGEN_COMPOSITE; - } + rc = pfilt_step(&f->f, f->step); + break; + case PGEN_DONE: + pfilt_destroy(&f->f); + return (PGEN_DONE); } - - /* --- Done --- */ - - mp_drop(r); + + while (rc == PGEN_FAIL) + rc = pfilt_step(&f->f, f->step); + ev->m = MP_COPY(f->f.m); return (rc); } -/* --- @pgen_destroy@ --- * - * - * Arguments: @pgen *p@ = pointer to prime generation context - * - * Returns: --- +/* --- @pgen_jump@ --- * * - * Use: Discards a context and all the resources it holds. + * Similar to the standard @pgen_filter@, but jumps in large steps rather + * than small ones. */ -void pgen_destroy(pgen *p) +int pgen_jump(int rq, pgen_event *ev, void *p) { - mp_drop(p->m); -} + pgen_jumpctx *f = p; + int rc = PGEN_ABORT; -/* --- @pgen_step@ --- * - * - * Arguments: @pgen *p@ = pointer to prime generation context - * @mpw step@ = how much to step the number - * - * Returns: One of the @PGEN@ constants above. - * - * Use: Steps a number by a small amount. Stepping is much faster - * than initializing with a new number. The test performed is - * the same simple one used by @ptab_create@, so @PGEN_MAYBE@ - * results should be followed up by a Rabin-Miller test. - */ - -int pgen_step(pgen *p, mpw step) -{ - int rc = PGEN_MAYBE; - int i; + switch (rq) { + case PGEN_BEGIN: + rc = pfilt_create(&f->f, ev->m); + mp_drop(ev->m); + break; + case PGEN_TRY: + mp_drop(ev->m); + rc = pfilt_jump(&f->f, f->j); + break; + case PGEN_DONE: + pfilt_destroy(&f->f); + return (PGEN_DONE); + } + + while (rc == PGEN_FAIL) + rc = pfilt_jump(&f->f, f->j); + ev->m = MP_COPY(f->f.m); + return (rc); +} - /* --- Add the step on to the number --- */ +/*----- Standard prime test -----------------------------------------------*/ - p->m = mp_split(p->m); - mp_ensure(p->m, MP_LEN(p->m) + 1); - mpx_uaddn(p->m->v, p->m->vl, step); - mp_shrink(p->m); +/* --- @pgen_test@ --- */ - /* --- Update the residue table --- */ +int pgen_test(int rq, pgen_event *ev, void *p) +{ + rabin *r = p; + int rc = PGEN_ABORT; - for (i = 0; i < NPRIME; i++) { - p->r[i] = (p->r[i] + step) % ptab[i]; - if (!p->r[i] && rc == PGEN_MAYBE) { - if (MP_LEN(p->m) == 1 && p->m->v[0] == ptab[i]) - rc = PGEN_PRIME; - else - rc = PGEN_COMPOSITE; - } + switch (rq) { + case PGEN_BEGIN: + rabin_create(r, ev->m); + rc = PGEN_TRY; + break; + case PGEN_TRY: { + mp *a = mprand_range(MP_NEW, ev->m, ev->r, 0); + rc = rabin_test(r, a); + mp_drop(a); + } break; + case PGEN_DONE: + rabin_destroy(r); + rc = PGEN_DONE; + break; } - /* --- Small numbers must be prime --- */ - - if (rc == PGEN_MAYBE && MP_LEN(p->m) == 1 && - p->m->v[0] < MAXPRIME * MAXPRIME) - rc = PGEN_PRIME; - - /* --- Done --- */ - return (rc); } -/* --- @pgen_muladd@ --- * - * - * Arguments: @pgen *p@ = destination prime generation context - * @const pgen *q@ = source prime generation context - * @mpw m@ = number to multiply by - * @mpw a@ = number to add +/*----- The main driver ---------------------------------------------------*/ + +/* --- @pgen@ --- * * - * Returns: One of the @PGEN@ constants above. + * Arguments: @const char *name@ = name of the value being searched for + * @mp *d@ = destination for the result integer + * @mp *m@ = start value to pass to stepper + * @pgen_proc *event@ = event handler function + * @void *ectx@ = context argument for event andler + * @unsigned steps@ = number of steps to take in search + * @pgen_proc *step@ = stepper function to use + * @void *sctx@ = context argument for stepper + * @unsigned tests@ = number of tests to make + * @pgen_proc *test@ = tester function to use + * @void *tctx@ = context argument for tester * - * Use: Multiplies the number in a prime generation context by a - * small value and then adds a small value. The destination - * should either be uninitialized or the same as the source. + * Returns: Pointer to final result, or null. * - * Common things to do include multiplying by 2 and adding 0 to - * turn a prime into a jump for finding other primes with @q@ as - * a factor of @p - 1@, or multiplying by 2 and adding 1. + * Use: A generalized prime-number search skeleton. Yes, that's a + * scary number of arguments. */ -int pgen_muladd(pgen *p, const pgen *q, mpw m, mpw a) +mp *pgen(const char *name, mp *d, mp *m, pgen_proc *event, void *ectx, + unsigned steps, pgen_proc *step, void *sctx, + unsigned tests, pgen_proc *test, void *tctx) { - int rc = PGEN_MAYBE; - int i; - - /* --- Multiply the big number --- */ - - { - mp *d = mp_create(MP_LEN(q->m) + 2); - mpx_umuln(d->v, d->vl, q->m->v, q->m->vl, m); - mpx_uaddn(d->v, d->vl, a); - d->f = q->m->f; - if (p == q) - mp_drop(p->m); - mp_shrink(d); - p->m = d; - } - - /* --- Gallivant through the residue table --- */ - - for (i = 0; i < NPRIME; i++) { - p->r[i] = (q->r[i] * m + a) % ptab[i]; - if (!p->r[i] && rc == PGEN_MAYBE) { - if (MP_LEN(p->m) == 1 && p->m->v[0] == ptab[i]) - rc = PGEN_PRIME; - else - rc = PGEN_COMPOSITE; - } - } + pgen_event ev; + int rq, rc; + pgen_proc *proc; + void *ctx; - /* --- Small numbers must be prime --- */ + /* --- Set up the initial event block --- */ - if (rc == PGEN_MAYBE && MP_LEN(p->m) == 1 && - p->m->v[0] < MAXPRIME * MAXPRIME) - rc = PGEN_PRIME; + ev.name = name; + if (m) + ev.m = MP_COPY(m); + else + ev.m = 0; + ev.steps = steps; + ev.tests = tests; + ev.r = fibrand_create(0); - /* --- Finished --- */ + /* --- Tell the event handler we're under way --- */ - return (rc); -} + if (event && event(PGEN_BEGIN, &ev, ectx) == PGEN_ABORT) + return (0); + /* --- Set up for the initial call --- */ -/* --- @pgen_jump@ --- * - * - * Arguments: @pgen *p@ = pointer to prime generation context - * @pgen *j@ = pointer to another generation context - * - * Returns: One of the @PGEN@ constants above. - * - * Use: Steps a number by a large amount. Even so, jumping is much - * faster than initializing a new number. The test peformed is - * the same simple one used by @ptab_create@, so @PGEN_MAYBE@ - * results should be followed up by a Rabin-Miller test. - * - * Note that the number stored in the @j@ context is probably - * better off being even than prime. The important thing is - * that all of the residues for the number have already been - * computed. - */ + proc = step; ctx = sctx; rq = PGEN_BEGIN; -int pgen_jump(pgen *p, pgen *j) -{ - int rc = PGEN_MAYBE; - int i; + /* --- Enter the great maelstrom of state transitions --- */ - /* --- Add the step on --- */ + for (;;) { + unsigned act = 0; + + enum { + A_STEP = 1u, + A_TEST = 2u, + A_EVENT = 4u, + A_ENDTEST = 8u, + A_ENDSTEP = 16u, + A_DONE = 32u + }; + + /* --- Call the procedure and decide what to do next --- */ + + rc = proc(rq, &ev, ctx); + switch (rc) { + case PGEN_TRY: + if (proc == test) + rq = PGEN_TRY; + else { + act |= A_EVENT; + proc = test; ctx = tctx; + rq = PGEN_BEGIN; + } + break; + case PGEN_PASS: + act |= A_TEST | A_EVENT; + if (proc == test) + rq = PGEN_TRY; + else { + proc = test; ctx = tctx; + rq = PGEN_BEGIN; + } + break; + case PGEN_FAIL: + act |= A_STEP; + if (proc == test) { + act |= A_ENDTEST | A_EVENT; + proc = step; ctx = sctx; + } + rq = PGEN_TRY; + break; + case PGEN_DONE: + act |= A_EVENT | A_DONE | A_ENDSTEP; + if (proc == test) + act |= A_ENDTEST; + break; + case PGEN_ABORT: + act |= A_EVENT | A_DONE; + if (proc == test || rq == PGEN_TRY) + act |= A_ENDSTEP; + if (proc == test && rq == PGEN_BEGIN) + act |= A_ENDTEST; + break; + default: + assert(((void)"Invalid response from function", 0)); + break; + } - p->m = mp_add(p->m, p->m, j->m); + /* --- If decrementing counters is requested, do that --- */ - /* --- Update the residue table --- */ + if ((act & A_STEP) && steps) { + ev.steps--; + if (!ev.steps) { + act |= A_EVENT | A_ENDSTEP | A_DONE; + rc = PGEN_ABORT; + } + ev.tests = tests; + } - for (i = 0; i < NPRIME; i++) { - p->r[i] = p->r[i] + j->r[i]; - if (p->r[i] > ptab[i]) - p->r[i] -= ptab[i]; - if (!p->r[i] && rc == PGEN_MAYBE) { - if (MP_LEN(p->m) == 1 && p->m->v[0] == ptab[i]) - rc = PGEN_PRIME; - else - rc = PGEN_COMPOSITE; + if ((act & A_TEST) && tests) { + ev.tests--; + if (!ev.tests) { + act |= A_ENDTEST | A_ENDSTEP | A_DONE; + rc = PGEN_DONE; + } } - } - /* --- Small numbers must be prime --- */ + /* --- Report an event if so directed --- */ - if (rc == PGEN_MAYBE && MP_LEN(p->m) == 1 && - p->m->v[0] < MAXPRIME * MAXPRIME) - rc = PGEN_PRIME; + if ((act & A_EVENT) && event && event(rc, &ev, ectx) == PGEN_ABORT) { + rc = PGEN_ABORT; + if (!(act & A_DONE)) { + act |= A_ENDSTEP | A_DONE; + if (proc == test) + act |= A_ENDTEST; + } + } - /* --- Done --- */ + /* --- Close down tester and stepper functions --- */ - return (rc); + if (act & A_ENDTEST) + test(PGEN_DONE, &ev, tctx); + if (act & A_ENDSTEP) + step(PGEN_DONE, &ev, sctx); + + /* --- Stop the entire test if necessary --- */ + + if (act & A_DONE) + break; + } + + /* --- Tidy up and return --- */ + + if (rc == PGEN_ABORT) { + mp_drop(ev.m); + ev.m = 0; + } + ev.r->ops->destroy(ev.r); + if (d != MP_NEW) + mp_drop(d); + + return (ev.m); } -/*----- Test code ---------------------------------------------------------*/ +/*----- Test rig ----------------------------------------------------------*/ #ifdef TEST_RIG @@ -281,52 +319,29 @@ int pgen_jump(pgen *p, pgen *j) static int verify(dstr *v) { mp *m = *(mp **)v[0].buf; - mp *r = *(mp **)v[1].buf; - pgen p; - mpw gw; - mp g; - int rc; - static char baton[] = "/-\\|"; - char *b = baton; + mp *q = *(mp **)v[1].buf; + mp *p; int ok = 1; - mp_build(&g, &gw, &gw + 1); - rc = pgen_create(&p, m); - for (;;) { - if (rc == PGEN_PRIME) - break; - if (rc == PGEN_MAYBE) { - int i; - rabin r; - rabin_create(&r, p.m); - for (i = 0; i < 5; i++) { - gw = rand(); - if (rabin_test(&r, &g) == PGEN_COMPOSITE) - break; - } - rabin_destroy(&r); - if (i == 5) - break; - putc(*b++, stderr); - putc('\b', stderr); - if (!*b) - b = baton; - } - rc = pgen_step(&p, 2); - } + pgen_filterctx pf; + rabin r; - if (MP_CMP(p.m, !=, r)) { - fputs("\n*** failed.", stderr); + pf.step = 2; + p = pgen("p", MP_NEW, m, pgen_evspin, 0, 0, pgen_filter, &pf, + rabin_iters(mp_bits(m)), pgen_test, &r); + if (!p || MP_CMP(p, !=, q)) { + fputs("\n*** pgen failed", stderr); fputs("\nm = ", stderr); mp_writefile(m, stderr, 10); - fputs("\np = ", stderr); mp_writefile(p.m, stderr, 10); - fputs("\nr = ", stderr); mp_writefile(r, stderr, 10); + fputs("\np = ", stderr); mp_writefile(p, stderr, 10); + fputs("\nq = ", stderr); mp_writefile(q, stderr, 10); fputc('\n', stderr); ok = 0; } mp_drop(m); - mp_drop(r); - pgen_destroy(&p); + mp_drop(q); + if (p) + mp_drop(p); assert(mparena_count(MPARENA_GLOBAL) == 0); return (ok); } @@ -342,7 +357,6 @@ int main(int argc, char *argv[]) test_run(argc, argv, tests, SRCDIR "/tests/pgen"); return (0); } - #endif /*----- That's all, folks -------------------------------------------------*/ diff --git a/pgen.h b/pgen.h index 6d180c3..9ce4e86 100644 --- a/pgen.h +++ b/pgen.h @@ -1,8 +1,8 @@ /* -*-c-*- * - * $Id: pgen.h,v 1.3 1999/12/10 23:29:48 mdw Exp $ + * $Id: pgen.h,v 1.4 1999/12/22 16:01:11 mdw Exp $ * - * Finding and testing prime numbers + * Prime generation glue * * (c) 1999 Straylight/Edgeware */ @@ -30,14 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: pgen.h,v $ - * Revision 1.3 1999/12/10 23:29:48 mdw - * Change header file guard names. - * - * Revision 1.2 1999/11/20 22:23:05 mdw - * Add multiply-and-add function for Diffie-Hellman safe prime generation. - * - * Revision 1.1 1999/11/19 13:17:57 mdw - * Prime number generator and tester. + * Revision 1.4 1999/12/22 16:01:11 mdw + * Same file, completely different code. Main interface for new prime- + * search system. * */ @@ -50,109 +45,206 @@ /*----- Header files ------------------------------------------------------*/ +#ifndef CATACOMB_GRAND_H +# include "grand.h" +#endif + #ifndef CATACOMB_MP_H # include "mp.h" #endif -#ifndef CATACOMB_PTAB_H -# include "ptab.h" +#ifndef CATACOMB_PFILT_H +# include "pfilt.h" #endif -/*----- Constants ---------------------------------------------------------*/ - -#define PGEN_COMPOSITE (-1) /* Number is definitely composite */ -#define PGEN_MAYBE (0) /* Number may be prime */ -#define PGEN_PRIME (1) /* Number is definitely prime */ - -/*----- Data structures ---------------------------------------------------*/ - -typedef struct pgen { - mp *m; - unsigned char r[NPRIME]; -} pgen; - -/*----- Functions provided ------------------------------------------------*/ +#ifndef CATACOMB_RABIN_H +# include "rabin.h" +#endif -/* --- @pgen_create@ --- * +/*----- Event handling ----------------------------------------------------* * - * Arguments: @pgen *p@ = pointer to prime generation context - * @mp *m@ = pointer to initial number to test + * Different programs and architectures will want to show progress of prime + * searches and similar processes in different ways. Of course, for simple + * searches, it's possible to use the @pfilt@ and @rabin@ functions and + * maintain control over the general control flow throughout the search. * - * Returns: One of the @PGEN@ constants above. + * For more complex cases, this sort of control is undesirable. It's + * possible to specify an event handler which is informed in abstract about + * the search. The event handler can also request the search be aborted. + */ + +/* --- Event code constants --- * * - * Use: Tests an initial number for primality by computing its - * residue modulo various small prime numbers. This is fairly - * quick, but not particularly certain. If a @PGEN_MAYBE@ - * result is returned, perform Rabin-Miller tests to confirm. + * You're allowed to rely on the values of @PGEN_DONE@ and @PGEN_ABORT@. */ -extern int pgen_create(pgen */*p*/, mp */*m*/); +enum { + PGEN_BEGIN = 1, /* Search for value begins */ + PGEN_TRY, /* A new candidate has appeared */ + PGEN_FAIL, /* The candidate failed the test */ + PGEN_PASS, /* The candidate passed a test */ + PGEN_DONE = 0, /* A good value has been found */ + PGEN_ABORT = -1 /* The search has been aborted */ +}; -/* --- @pgen_destroy@ --- * +/* --- Event information --- * * - * Arguments: @pgen *p@ = pointer to prime generation context - * - * Returns: --- - * - * Use: Discards a context and all the resources it holds. + * Note that the pseudorandom number generator supplied is not + * cryptographically strong. */ -extern void pgen_destroy(pgen */*p*/); +typedef struct pgen_event { + const char *name; /* Which quantity is being found */ + mp *m; /* Current value under test */ + unsigned steps; /* Number of candidates left */ + unsigned tests; /* Tests left before passing */ + grand *r; /* Source of random numbers */ +} pgen_event; + +/*----- Prime search parameters -------------------------------------------* + * + * The prime search is parameterized in a large number of ways, although this + * isn't so much of a surprise given the different sorts of properties + * required from prime numbers in cryptographic applications. + * + * There are two main things which need to be configured: stepping, and + * testing. (Filtering is done as part of stepping.) + * + * The functions here provide a toolkit for constructing stepping and testing + * routines. In a lot of cases, the functions can be used directly; in + * others, simple bits of glue need be written. + * + * Two types of functions are defined: steppers and testers, but their + * interfaces are substantially similar. Each is given a request code, a + * context block and an event block. It is meant to update its context and + * the event block and return an event code. + * + * A call with a request of @PGEN_BEGIN@ asks the stepper or tester to + * initialize itself using the information in its event block and context. A + * return of @PGEN_FAIL@ reports an immediate failure; @PGEN_ABORT@ reports a + * fatal problem; @PGEN_DONE@ reports immediate success. @PGEN_TRY@ reports + * successful initialization and requests test iterations. + * + * A call to a stepper with a request of @PGEN_TRY@ asks it to step to the + * next possible candidate, replacing the value @m@ in the event block with + * the new candidate. A call to a tester with a request of @PGEN_TRY@ + * runs one pass of the test. It should return @PGEN_FAIL@ to report a + * failure, @PGEN_PASS@ to report a success and request another iteration, + * @PGEN_DONE@ to report final acceptance and @PGEN_ABORT@ to terminate the + * search unsuccessfully. Note that even if the search is aborted, a + * shutdown request is still made. + * + * A call with a request of @PGEN_DONE@ closes down the stepper or tester. + * After a successful initialization (i.e., a return of something other than + * @PGEN_ABORT@), a shutdown call is guaranteed. The return code is ignored. + */ -/* --- @pgen_step@ --- * - * - * Arguments: @pgen *p@ = pointer to prime generation context - * @mpw step@ = how much to step the number +typedef int pgen_proc(int /*rq*/, pgen_event */*ev*/, void */*p*/); + +/*----- Simple handler functions ------------------------------------------*/ + +/* --- @pgen_filter@ --- * * - * Returns: One of the @PGEN@ constants above. + * A prime generation context contains the information required for the + * simple prime filter and tester presented here. + */ + +typedef struct pgen_filterctx { + unsigned step; /* Step size (set by client) */ + pfilt f; /* The rapid prime filter */ +} pgen_filterctx; + +extern int pgen_filter(int /*rq*/, pgen_event */*ev*/, void */*p*/); + +/* --- @pgen_jump@ --- * * - * Use: Steps a number by a small amount. Stepping is much faster - * than initializing with a new number. The test performed is - * the same simple one used by @ptab_create@, so @PGEN_MAYBE@ - * results should be followed up by a Rabin-Miller test. + * Similar to the standard @pgen_filter@, but jumps in large steps rather + * than small ones. */ -extern int pgen_step(pgen */*p*/, mpw /*step*/); +typedef struct pgen_jumpctx { + const pfilt *j; + pfilt f; +} pgen_jumpctx; + +extern int pgen_jump(int /*rq*/, pgen_event */*ev*/, void */*p*/); -/* --- @pgen_muladd@ --- * +/* --- @pgen_test@ --- * * - * Arguments: @pgen *p@ = destination prime generation context - * @const pgen *q@ = source prime generation context - * @mpw m@ = number to multiply by - * @mpw a@ = number to add + * Runs the Rabin-Miller primality test. The context block is simply a + * @rabin@ context. + */ + +extern int pgen_test(int /*rq*/, pgen_event */*ev*/, void */*p*/); + +/*----- Safe prime functions ----------------------------------------------*/ + +/* --- @pgen_safestep@ --- * * - * Returns: One of the @PGEN@ constants above. + * Steps two numbers, %$q$% and %$p = 2q + 1$%, such that neither has any + * small factors. %$p$% is put in the event block. + */ + +typedef struct pgen_safestepctx { + pfilt q, p; +} pgen_safestepctx; + +extern int pgen_safestep(int /*rq*/, pgen_event */*ev*/, void */*p*/); + +/* --- @pgen_safetest@ --- * * - * Use: Multiplies the number in a prime generation context by a - * small value and then adds a small value. The destination - * should either be uninitialized or the same as the source. + * Applies Rabin-Miller tests to %$p$% and %$(p - 1)/2$%. + */ + +typedef struct pgen_safetestctx { + pgen_safestepctx c; + rabin q, p; +} pgen_safetestctx; + +extern int pgen_safetest(int /*rq*/, pgen_event */*ev*/, void */*p*/); + +/*----- Standard event handlers -------------------------------------------*/ + +/* --- @pgen_evspin@ --- * * - * Common things to do include multiplying by 2 and adding 0 to - * turn a prime into a jump for finding other primes with @q@ as - * a factor of @p - 1@, or multiplying by 2 and adding 1. + * Displays a spinning baton to show progress. */ -extern int pgen_muladd(pgen */*p*/, const pgen */*q*/, mpw /*m*/, mpw /*a*/); +extern int pgen_evspin(int /*rq*/, pgen_event */*ev*/, void */*p*/); -/* --- @pgen_jump@ --- * +/* --- @pgen_ev@ --- * * - * Arguments: @pgen *p@ = pointer to prime generation context - * @pgen *j@ = pointer to another generation context + * Traditional event handler, shows dots for each test. + */ + +extern int pgen_ev(int /*rq*/, pgen_event */*ev*/, void */*p*/); + +/*----- The main driver ---------------------------------------------------*/ + +/* --- @pgen@ --- * * - * Returns: One of the @PGEN@ constants above. + * Arguments: @const char *name@ = name of the value being searched for + * @mp *d@ = destination for resulting integer + * @mp *m@ = start value to pass to stepper + * @pgen_proc *event@ = event handler function + * @void *ectx@ = context argument for event andler + * @unsigned steps@ = number of steps to take in search + * @pgen_proc *step@ = stepper function to use + * @void *sctx@ = context argument for stepper + * @unsigned tests@ = number of tests to make + * @pgen_proc *test@ = tester function to use + * @void *tctx@ = context argument for tester * - * Use: Steps a number by a large amount. Even so, jumping is much - * faster than initializing a new number. The test peformed is - * the same simple one used by @ptab_create@, so @PGEN_MAYBE@ - * results should be followed up by a Rabin-Miller test. + * Returns: If successful, @PGEN_DONE@; otherwise @PGEN_ABORT@. * - * Note that the number stored in the @j@ context is probably - * better off being even than prime. The important thing is - * that all of the residues for the number have already been - * computed. + * Use: A generalized prime-number search skeleton. Yes, that's a + * scary number of arguments. */ -extern int pgen_jump(pgen */*p*/, pgen */*j*/); +extern mp *pgen(const char */*name*/, mp */*d*/, mp */*m*/, + pgen_proc */*event*/, void */*ectx*/, + unsigned /*steps*/, pgen_proc */*step*/, void */*sctx*/, + unsigned /*tests*/, pgen_proc */*test*/, void */*tctx*/); /*----- That's all, folks -------------------------------------------------*/ -- 2.11.0