3 * Finding primitive elements
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 #ifndef CATACOMB_PRIM_H
29 #define CATACOMB_PRIM_H
35 /*----- Header files ------------------------------------------------------*/
43 #ifndef CATACOMB_MPMONT_H
47 #ifndef CATACOMB_PGEN_H
51 /*----- Data structures ---------------------------------------------------*/
53 /* --- @prim_ctx@ --- *
55 * All fields must be configured by the client. Set @n@ to zero to discover
56 * generators of the subgroup of order %$m / f$%.
58 * Let %$p = \prod q_i + 1$% be a prime number. In order to find an element
59 * %$g$% with order %$o$%, we choose elements %$h_j$% from %$\gf{p}^*$%,
60 * compute $%g_j = h_j^{p/o}$%, rejecting %$h_j$% where %$g_j = 1$%, and then
61 * for each proper prime factor %$q_i$% of %$p/o$% we check that
62 * %$g^{f_i} \ne 1$%, where the %$f_i$% are cofactors of the %$q_i$%
63 * (%$f_i q_i = p/o$%).
66 typedef struct prim_ctx {
67 mpmont mm; /* Montgomery context for modulus */
68 mp *exp; /* Exponent (%$p/o$%; may be zero) */
69 size_t n; /* Number of cofactors */
70 mp **f; /* Array of cofactors */
73 /*----- Functions provided ------------------------------------------------*/
75 /* --- @prim_test@ --- */
77 extern pgen_proc prim_test;
79 /* --- @prim_step@ --- */
81 extern pgen_proc prim_step;
83 /*----- That's all, folks -------------------------------------------------*/