fcdaa180 |
1 | /* -*-c-*- |
fcdaa180 |
2 | * |
3 | * Finding primitive elements |
4 | * |
5 | * (c) 1999 Straylight/Edgeware |
6 | */ |
7 | |
45c0fd36 |
8 | /*----- Licensing notice --------------------------------------------------* |
fcdaa180 |
9 | * |
10 | * This file is part of Catacomb. |
11 | * |
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. |
45c0fd36 |
16 | * |
fcdaa180 |
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. |
45c0fd36 |
21 | * |
fcdaa180 |
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, |
25 | * MA 02111-1307, USA. |
26 | */ |
27 | |
fcdaa180 |
28 | #ifndef CATACOMB_PRIM_H |
29 | #define CATACOMB_PRIM_H |
30 | |
31 | #ifdef __cplusplus |
32 | extern "C" { |
33 | #endif |
34 | |
35 | /*----- Header files ------------------------------------------------------*/ |
36 | |
37 | #include <stddef.h> |
38 | |
39 | #ifndef CATACOMB_MP_H |
40 | # include "mp.h" |
41 | #endif |
42 | |
43 | #ifndef CATACOMB_MPMONT_H |
44 | # include "mpmont.h" |
45 | #endif |
46 | |
47 | #ifndef CATACOMB_PGEN_H |
48 | # include "pgen.h" |
49 | #endif |
50 | |
51 | /*----- Data structures ---------------------------------------------------*/ |
52 | |
53 | /* --- @prim_ctx@ --- * |
54 | * |
55 | * All fields must be configured by the client. Set @n@ to zero to discover |
56 | * generators of the subgroup of order %$m / f$%. |
6f80d39f |
57 | * |
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$%). |
fcdaa180 |
64 | */ |
65 | |
66 | typedef struct prim_ctx { |
67 | mpmont mm; /* Montgomery context for modulus */ |
6f80d39f |
68 | mp *exp; /* Exponent (%$p/o$%; may be zero) */ |
69 | size_t n; /* Number of cofactors */ |
70 | mp **f; /* Array of cofactors */ |
fcdaa180 |
71 | } prim_ctx; |
72 | |
73 | /*----- Functions provided ------------------------------------------------*/ |
74 | |
75 | /* --- @prim_test@ --- */ |
76 | |
ab6ce636 |
77 | extern pgen_proc prim_test; |
fcdaa180 |
78 | |
79 | /* --- @prim_step@ --- */ |
80 | |
ab6ce636 |
81 | extern pgen_proc prim_step; |
fcdaa180 |
82 | |
83 | /*----- That's all, folks -------------------------------------------------*/ |
84 | |
85 | #ifdef __cplusplus |
86 | } |
87 | #endif |
88 | |
89 | #endif |