math/mpreduce.h: Missing include files.
[u/mdw/catacomb] / math / gfreduce.h
CommitLineData
ceb3f0c0 1/* -*-c-*-
2 *
ceb3f0c0 3 * Reduction modulo sparse binary polynomials
4 *
5 * (c) 2004 Straylight/Edgeware
6 */
7
45c0fd36 8/*----- Licensing notice --------------------------------------------------*
ceb3f0c0 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 *
ceb3f0c0 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 *
ceb3f0c0 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
ceb3f0c0 28#ifndef CATACOMB_GFREDUCE_H
29#define CATACOMB_GFREDUCE_H
30
31#ifdef __cplusplus
32 extern "C" {
33#endif
34
35/*----- Header files ------------------------------------------------------*/
36
37#ifndef CATACOMB_GF_H
38# include "gf.h"
39#endif
40
41/*----- Data structures ---------------------------------------------------*/
42
43typedef struct gfreduce_instr {
44 unsigned op; /* Instruction opcode */
45 size_t arg; /* Immediate argument */
46} gfreduce_instr;
47
48enum {
49 GFRI_LOAD, /* Load @p[arg]@ */
50 GFRI_LSL, /* XOR with @w << arg@ */
51 GFRI_LSR, /* XOR with @w >> arg@ */
52 GFRI_STORE, /* Store @p[arg]@ */
53 GFRI_MAX
54};
55
56typedef struct gfreduce {
57 size_t lim; /* Word of degree bit */
58 mpw mask; /* Mask for degree word */
59 mp *p; /* Copy of the polynomial */
60 size_t in; /* Number of instruction words */
61 gfreduce_instr *iv, *liv; /* Vector of instructions */
62} gfreduce;
63
64/*----- Functions provided ------------------------------------------------*/
65
66/* --- @gfreduce_create@ --- *
67 *
68 * Arguments: @gfreduce *r@ = structure to fill in
69 * @mp *x@ = a (hopefully sparse) polynomial
70 *
71 * Returns: ---
72 *
73 * Use: Initializes a context structure for reduction.
74 */
75
76extern void gfreduce_create(gfreduce */*r*/, mp */*p*/);
77
78/* --- @gfreduce_destroy@ --- *
79 *
80 * Arguments: @gfreduce *r@ = structure to free
81 *
82 * Returns: ---
83 *
84 * Use: Reclaims the resources from a reduction context.
85 */
86
87extern void gfreduce_destroy(gfreduce */*r*/);
88
89/* --- @gfreduce_dump@ --- *
90 *
91 * Arguments: @gfreduce *r@ = structure to dump
92 * @FILE *fp@ = file to dump on
93 *
94 * Returns: ---
95 *
96 * Use: Dumps a reduction context.
97 */
98
99extern void gfreduce_dump(gfreduce */*r*/, FILE */*fp*/);
100
101/* --- @gfreduce_do@ --- *
102 *
103 * Arguments: @gfreduce *r@ = reduction context
104 * @mp *d@ = destination
105 * @mp *x@ = source
106 *
107 * Returns: Destination, @x@ reduced modulo the reduction poly.
108 */
109
110extern mp *gfreduce_do(gfreduce */*r*/, mp */*d*/, mp */*x*/);
111
112/* --- @gfreduce_sqrt@ --- *
113 *
114 * Arguments: @gfreduce *r@ = pointer to reduction context
115 * @mp *d@ = destination
116 * @mp *x@ = some polynomial
117 *
118 * Returns: The square root of @x@ modulo @r->p@, or null.
119 */
120
121extern mp *gfreduce_sqrt(gfreduce */*r*/, mp */*d*/, mp */*x*/);
122
123/* --- @gfreduce_trace@ --- *
124 *
125 * Arguments: @gfreduce *r@ = pointer to reduction context
126 * @mp *x@ = some polynomial
127 *
128 * Returns: The trace of @x@. (%$\Tr(x)=x + x^2 + \cdots + x^{2^{m-1}}$%
129 * if %$x \in \gf{2^m}$%).
130 */
131
132extern int gfreduce_trace(gfreduce */*r*/, mp */*x*/);
133
134/* --- @gfreduce_halftrace@ --- *
135 *
136 * Arguments: @gfreduce *r@ = pointer to reduction context
137 * @mp *d@ = destination
138 * @mp *x@ = some polynomial
139 *
140 * Returns: The half-trace of @x@.
141 * (%$\HfTr(x)= x + x^{2^2} + \cdots + x^{2^{m-1}}$%
142 * if %$x \in \gf{2^m}$% with %$m$% odd).
143 */
144
145extern mp *gfreduce_halftrace(gfreduce */*r*/, mp */*d*/, mp */*x*/);
146
147/* --- @gfreduce_quadsolve@ --- *
148 *
149 * Arguments: @gfreduce *r@ = pointer to reduction context
150 * @mp *d@ = destination
151 * @mp *x@ = some polynomial
152 *
153 * Returns: A polynomial @y@ such that %$y^2 + y = x$%, or null.
154 */
155
156extern mp *gfreduce_quadsolve(gfreduce */*r*/, mp */*d*/, mp */*x*/);
157
158/* --- @gfreduce_exp@ --- *
159 *
160 * Arguments: @gfreduce *gr@ = pointer to reduction context
45c0fd36
MW
161 * @mp *d@ = fake destination
162 * @mp *a@ = base
163 * @mp *e@ = exponent
ceb3f0c0 164 *
45c0fd36 165 * Returns: Result, %$a^e \bmod m$%.
ceb3f0c0 166 */
167
168extern mp *gfreduce_exp(gfreduce */*gr*/, mp */*d*/, mp */*a*/, mp */*e*/);
169
170/*----- That's all, folks -------------------------------------------------*/
171
172#ifdef __cplusplus
173 }
174#endif
175
176#endif