chiark - git - mdw - catacomb/blob - prim.h

   1 /* -*-c-*-
   2  *
   3  * $Id: prim.h,v 1.3 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * Finding primitive elements
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 #ifndef CATACOMB_PRIM_H
  31 #define CATACOMB_PRIM_H
  32
  33 #ifdef __cplusplus
  34   extern "C" {
  35 #endif
  36
  37 /*----- Header files ------------------------------------------------------*/
  38
  39 #include <stddef.h>
  40
  41 #ifndef CATACOMB_MP_H
  42 #  include "mp.h"
  43 #endif
  44
  45 #ifndef CATACOMB_MPMONT_H
  46 #  include "mpmont.h"
  47 #endif
  48
  49 #ifndef CATACOMB_PGEN_H
  50 #  include "pgen.h"
  51 #endif
  52
  53 /*----- Data structures ---------------------------------------------------*/
  54
  55 /* --- @prim_ctx@ --- *
  56  *
  57  * All fields must be configured by the client.  Set @n@ to zero to discover
  58  * generators of the subgroup of order %$m / f$%.
  59  *
  60  * Let %$p = \prod q_i + 1$% be a prime number.  In order to find an element
  61  * %$g$% with order %$o$%, we choose elements %$h_j$% from %$\gf{p}^*$%,
  62  * compute $%g_j = h_j^{p/o}$%, rejecting %$h_j$% where %$g_j = 1$%, and then
  63  * for each proper prime factor %$q_i$% of %$p/o$% we check that
  64  * %$g^{f_i} \ne 1$%, where the %$f_i$% are cofactors of the %$q_i$%
  65  * (%$f_i q_i = p/o$%).
  66  */
  67
  68 typedef struct prim_ctx {
  69   mpmont mm;                            /* Montgomery context for modulus */
  70   mp *exp;                              /* Exponent (%$p/o$%; may be zero) */
  71   size_t n;                             /* Number of cofactors */
  72   mp **f;                               /* Array of cofactors */
  73 } prim_ctx;
  74
  75 /*----- Functions provided ------------------------------------------------*/
  76
  77 /* --- @prim_test@ --- */
  78
  79 extern pgen_proc prim_test;
  80
  81 /* --- @prim_step@ --- */
  82
  83 extern pgen_proc prim_step;
  84
  85 /*----- That's all, folks -------------------------------------------------*/
  86
  87 #ifdef __cplusplus
  88   }
  89 #endif
  90
  91 #endif