From fcdaa1806c38c703a6e72b87e189396a05d165e4 Mon Sep 17 00:00:00 2001 From: mdw Date: Wed, 22 Dec 1999 15:58:59 +0000 Subject: [PATCH] Search for primitive elements using prime-search equipment. --- prim.c | 107 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ prim.h | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 198 insertions(+) create mode 100644 prim.c create mode 100644 prim.h diff --git a/prim.c b/prim.c new file mode 100644 index 0000000..bdad98b --- /dev/null +++ b/prim.c @@ -0,0 +1,107 @@ +/* -*-c-*- + * + * $Id: prim.c,v 1.1 1999/12/22 15:58:59 mdw Exp $ + * + * Finding primitive elements + * + * (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: prim.c,v $ + * Revision 1.1 1999/12/22 15:58:59 mdw + * Search for primitive elements using prime-search equipment. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "mp.h" +#include "mpint.h" +#include "mpmont.h" +#include "mprand.h" +#include "pgen.h" +#include "prim.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @prim_test@ --- */ + +int prim_test(int rq, pgen_event *ev, void *p) +{ + prim_ctx *c = p; + int rc = rq; + + switch (rq) { + case PGEN_BEGIN: + return (PGEN_TRY); + case PGEN_TRY: { + mp *x = MP_NEW; + mp *f = c->f; + rc = PGEN_FAIL; + + x = mpmont_exp(&c->mm, x, ev->m, f); + if (MP_CMP(x, ==, MP_ONE)) + goto done; + if (c->n == 0) { + mp_drop(ev->m); + ev->m = MP_COPY(x); + } else { + size_t n = c->n - 1; + f++; + while (n) { + x = mpmont_exp(&c->mm, x, ev->m, f); + if (MP_CMP(x, ==, MP_ONE)) + goto done; + n--; f++; + } + } + rc = PGEN_DONE; + done: + mp_drop(x); + } break; + } + + return (rc); +} + +/* --- Trivial stepping functions -----------------------------------------*/ + +/* --- @prim_step@ --- */ + +int prim_step(int rq, pgen_event *ev, void *p) +{ + unsigned *i = p; + switch (rq) { + case PGEN_BEGIN: + case PGEN_TRY: + if (*i >= NPRIME) + return PGEN_FAIL; + ev->m = mp_fromint(ev->m, primetab[(*i)++]); + return (PGEN_TRY); + } + return (0); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/prim.h b/prim.h new file mode 100644 index 0000000..30392cd --- /dev/null +++ b/prim.h @@ -0,0 +1,91 @@ +/* -*-c-*- + * + * $Id: prim.h,v 1.1 1999/12/22 15:58:59 mdw Exp $ + * + * Finding primitive elements + * + * (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: prim.h,v $ + * Revision 1.1 1999/12/22 15:58:59 mdw + * Search for primitive elements using prime-search equipment. + * + */ + +#ifndef CATACOMB_PRIM_H +#define CATACOMB_PRIM_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include + +#ifndef CATACOMB_MP_H +# include "mp.h" +#endif + +#ifndef CATACOMB_MPMONT_H +# include "mpmont.h" +#endif + +#ifndef CATACOMB_PGEN_H +# include "pgen.h" +#endif + +/*----- Data structures ---------------------------------------------------*/ + +/* --- @prim_ctx@ --- * + * + * All fields must be configured by the client. Set @n@ to zero to discover + * generators of the subgroup of order %$m / f$%. + */ + +typedef struct prim_ctx { + mpmont mm; /* Montgomery context for modulus */ + mp *f; /* Array of factors */ + size_t n; /* Number of factors */ +} prim_ctx; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @prim_test@ --- */ + +extern int prim_test(int /*rq*/, pgen_event */*ev*/, void */*p*/); + +/* --- @prim_step@ --- */ + +extern int prim_step(int /*rq*/, pgen_event */*ev*/, void */*p*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif -- 2.11.0