chiark / gitweb /
math/limlee.c: Handle an abort from `pgen' correctly.
[catacomb] / math / gfreduce.h
1 /* -*-c-*-
2  *
3  * Reduction modulo sparse binary polynomials
4  *
5  * (c) 2004 Straylight/Edgeware
6  */
7
8 /*----- Licensing notice --------------------------------------------------*
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.
16  *
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.
21  *
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
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 #include <stdio.h>
38
39 #ifndef CATACOMB_GF_H
40 #  include "gf.h"
41 #endif
42
43 /*----- Data structures ---------------------------------------------------*/
44
45 typedef struct gfreduce_instr {
46   unsigned op;                          /* Instruction opcode */
47   size_t arg;                           /* Immediate argument */
48 } gfreduce_instr;
49
50 enum {
51   GFRI_LOAD,                            /* Load @p[arg]@ */
52   GFRI_LSL,                             /* XOR with @w << arg@ */
53   GFRI_LSR,                             /* XOR with @w >> arg@ */
54   GFRI_STORE,                           /* Store @p[arg]@ */
55   GFRI_MAX
56 };
57
58 typedef struct gfreduce {
59   size_t lim;                           /* Word of degree bit */
60   mpw mask;                             /* Mask for degree word */
61   mp *p;                                /* Copy of the polynomial */
62   size_t in;                            /* Number of instruction words */
63   gfreduce_instr *iv;                   /* Vector of instructions */
64   gfreduce_instr *fiv;                  /* Final-pass instruction suffix */
65 } gfreduce;
66
67 /*----- Functions provided ------------------------------------------------*/
68
69 /* --- @gfreduce_create@ --- *
70  *
71  * Arguments:   @gfreduce *r@ = structure to fill in
72  *              @mp *x@ = a (hopefully sparse) polynomial
73  *
74  * Returns:     ---
75  *
76  * Use:         Initializes a context structure for reduction.
77  */
78
79 extern void gfreduce_create(gfreduce */*r*/, mp */*p*/);
80
81 /* --- @gfreduce_destroy@ --- *
82  *
83  * Arguments:   @gfreduce *r@ = structure to free
84  *
85  * Returns:     ---
86  *
87  * Use:         Reclaims the resources from a reduction context.
88  */
89
90 extern void gfreduce_destroy(gfreduce */*r*/);
91
92 /* --- @gfreduce_dump@ --- *
93  *
94  * Arguments:   @const gfreduce *r@ = structure to dump
95  *              @FILE *fp@ = file to dump on
96  *
97  * Returns:     ---
98  *
99  * Use:         Dumps a reduction context.
100  */
101
102 extern void gfreduce_dump(const gfreduce */*r*/, FILE */*fp*/);
103
104 /* --- @gfreduce_do@ --- *
105  *
106  * Arguments:   @const gfreduce *r@ = reduction context
107  *              @mp *d@ = destination
108  *              @mp *x@ = source
109  *
110  * Returns:     Destination, @x@ reduced modulo the reduction poly.
111  */
112
113 extern mp *gfreduce_do(const gfreduce */*r*/, mp */*d*/, mp */*x*/);
114
115 /* --- @gfreduce_sqrt@ --- *
116  *
117  * Arguments:   @const gfreduce *r@ = pointer to reduction context
118  *              @mp *d@ = destination
119  *              @mp *x@ = some polynomial
120  *
121  * Returns:     The square root of @x@ modulo @r->p@, or null.
122  */
123
124 extern mp *gfreduce_sqrt(const gfreduce */*r*/, mp */*d*/, mp */*x*/);
125
126 /* --- @gfreduce_trace@ --- *
127  *
128  * Arguments:   @const gfreduce *r@ = pointer to reduction context
129  *              @mp *x@ = some polynomial
130  *
131  * Returns:     The trace of @x@. (%$\Tr(x)=x + x^2 + \cdots + x^{2^{m-1}}$%
132  *              if %$x \in \gf{2^m}$%).  Since the trace is invariant under
133  *              the Frobenius automorphism (i.e., %$\Tr(x)^2 = \Tr(x)$%), it
134  *              must be an element of the base field, i.e., %$\gf{2}$%, and
135  *              we only need a single bit to represent it.
136  */
137
138 extern int gfreduce_trace(const gfreduce */*r*/, mp */*x*/);
139
140 /* --- @gfreduce_halftrace@ --- *
141  *
142  * Arguments:   @const gfreduce *r@ = pointer to reduction context
143  *              @mp *d@ = destination
144  *              @mp *x@ = some polynomial
145  *
146  * Returns:     The half-trace of @x@.
147  *              (%$\HfTr(x)= x + x^{2^2} + \cdots + x^{2^{m-1}}$%
148  *              if %$x \in \gf{2^m}$% with %$m$% odd).
149  */
150
151 extern mp *gfreduce_halftrace(const gfreduce */*r*/, mp */*d*/, mp */*x*/);
152
153 /* --- @gfreduce_quadsolve@ --- *
154  *
155  * Arguments:   @const gfreduce *r@ = pointer to reduction context
156  *              @mp *d@ = destination
157  *              @mp *x@ = some polynomial
158  *
159  * Returns:     A polynomial @y@ such that %$y^2 + y = x$%, or null.
160  *
161  * Use:         Solves quadratic equations in a field with characteristic 2.
162  *              Suppose we have an equation %$y^2 + A y + B = 0$% where
163  *              %$A \ne 0$%.  (If %$A = 0$% then %$y = \sqrt{B}$% and you
164  *              want @gfreduce_sqrt@ instead.)  Use this function to solve
165  *              %$z^2 + z = B/A^2$%; then set %$y = A z$%, since
166  *              %$y^2 + y = A^2 z^2 + A^2 z = A^2 (z^2 + z) = B$% as
167  *              required.
168  *
169  *              The two roots are %$z$% and %$z + 1$%; this function always
170  *              returns the one with zero scalar coefficient.
171  */
172
173 extern mp *gfreduce_quadsolve(const gfreduce */*r*/, mp */*d*/, mp */*x*/);
174
175 /* --- @gfreduce_exp@ --- *
176  *
177  * Arguments:   @const gfreduce *gr@ = pointer to reduction context
178  *              @mp *d@ = fake destination
179  *              @mp *a@ = base
180  *              @mp *e@ = exponent
181  *
182  * Returns:     Result, %$a^e \bmod m$%.
183  */
184
185 extern mp *gfreduce_exp(const gfreduce */*gr*/, mp */*d*/,
186                         mp */*a*/, mp */*e*/);
187
188 /*----- That's all, folks -------------------------------------------------*/
189
190 #ifdef __cplusplus
191   }
192 #endif
193
194 #endif