chiark / gitweb /
math/mpx-mul4-x86-sse2.S: Use `SHUF' instead of hardwired constants.
[catacomb] / math / prim.h
CommitLineData
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
66typedef 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 77extern pgen_proc prim_test;
fcdaa180 78
79/* --- @prim_step@ --- */
80
ab6ce636 81extern pgen_proc prim_step;
fcdaa180 82
83/*----- That's all, folks -------------------------------------------------*/
84
85#ifdef __cplusplus
86 }
87#endif
88
89#endif