5 * Definitions for field arithmetic
7 * (c) 2000 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 #ifndef CATACOMB_FIELD_H
31 #define CATACOMB_FIELD_H
37 /*----- Header files ------------------------------------------------------*/
39 #ifndef CATACOMB_GRAND_H
47 #ifndef CATACOMB_QDPARSE_H
51 /*----- Data structures ---------------------------------------------------*/
53 typedef struct field
{
54 const struct field_ops
*ops
; /* Field operations */
55 mp
*zero
, *one
; /* Identities in the field */
56 mp
*m
; /* Modulus (prime and binary) */
57 unsigned long nbits
; /* Length of field element in bits */
58 size_t noctets
; /* Length of element in octets */
59 mp
*q
; /* Number of elements in field */
67 typedef struct field_ops
{
69 /* --- General information --- */
71 unsigned ty
; /* What kind of field this is */
72 const char *name
; /* Human-readable name string */
74 /* --- Universal operations --- */
76 void (*destroy
)(field */
*f*/
);
77 mp
*(*rand
)(field */
*f*/
, mp */
*d*/
, grand */
*r*/
);
78 int (*samep
)(field */
*f*/
, field */
*g*/
);
80 mp
*(*in
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
81 mp
*(*out
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
83 int (*zerop
)(field */
*f*/
, mp */
*x*/
);
84 mp
*(*neg
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
85 mp
*(*add
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
, mp */
*y*/
);
86 mp
*(*sub
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
, mp */
*y*/
);
87 mp
*(*mul
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
, mp */
*y*/
);
88 mp
*(*sqr
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
89 mp
*(*inv
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
90 mp
*(*reduce
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
91 mp
*(*sqrt
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
93 /* --- Operations for binary fields only --- */
95 mp
*(*quadsolve
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
97 /* --- Operations for prime fields only --- */
99 mp
*(*dbl
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
100 mp
*(*tpl
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
101 mp
*(*qdl
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
102 mp
*(*hlv
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
106 #define F_TYPE(f) (f)->ops->ty
107 #define F_NAME(f) (f)->ops->name
109 #define F_DESTROY(f) (f)->ops->destroy((f))
110 #define F_RAND(f, d, r) (f)->ops->rand((f), (d), (r))
111 #define F_SAMEP(f, g) (f)->ops->samep((f), (g))
113 #define F_IN(f, d, x) (f)->ops->in((f), (d), (x))
114 #define F_OUT(f, d, x) (f)->ops->out((f), (d), (x))
116 #define F_ZEROP(f, x) (f)->ops->zerop((f), (x))
117 #define F_NEG(f, d, x) (f)->ops->neg((f), (d), (x))
118 #define F_ADD(f, d, x, y) (f)->ops->add((f), (d), (x), (y))
119 #define F_SUB(f, d, x, y) (f)->ops->sub((f), (d), (x), (y))
120 #define F_MUL(f, d, x, y) (f)->ops->mul((f), (d), (x), (y))
121 #define F_SQR(f, d, x) (f)->ops->sqr((f), (d), (x))
122 #define F_INV(f, d, x) (f)->ops->inv((f), (d), (x))
123 #define F_REDUCE(f, d, x) (f)->ops->reduce((f), (d), (x))
124 #define F_SQRT(f, d, x) (f)->ops->sqrt((f), (d), (x))
126 #define F_QUADSOLVE(f, d, x) (f)->ops->quadsolve((f), (d), (x))
128 #define F_DBL(f, d, x) (f)->ops->dbl((f), (d), (x))
129 #define F_TPL(f, d, x) (f)->ops->tpl((f), (d), (x))
130 #define F_QDL(f, d, x) (f)->ops->qdl((f), (d), (x))
131 #define F_HLV(f, d, x) (f)->ops->hlv((f), (d), (x))
133 /*----- Helpful field operations ------------------------------------------*/
135 /* --- @field_id@ --- *
137 * Arguments: @field *f@ = pointer to a field
138 * @mp *d@ = a destination element
139 * @mp *x@ = a source element
141 * Returns: The result element.
143 * Use: An identity operation which can be used if your field has no
144 * internal representation.
147 extern mp
*field_id(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
149 /* --- @field_samep@ --- *
151 * Arguments: @field *f, *g@ = two fields
153 * Returns: Nonzero if the fields are identical (not just isomorphic).
155 * Use: Checks for sameness of fields. This function does the full
156 * check, not just the field-type-specific check done by the
157 * @sampep@ field operation.
160 extern int field_samep(field */
*f*/
, field */
*g*/
);
162 /* --- @field_stdsamep@ --- *
164 * Arguments: @field *f, *g@ = two fields
166 * Returns: Nonzero if the fields are identical (not just isomorphic).
168 * Use: Standard sameness check, based on equality of the @m@
172 extern int field_stdsamep(field */
*f*/
, field */
*g*/
);
174 /*----- Arithmetic --------------------------------------------------------*/
176 /* --- @field_exp@ --- *
178 * Arguments: @field *f@ = pointer to field
179 * @mp *d@ = fake destination
183 * Returns: Result, %$a^e$%.
185 * Use: Exponentiation in a finite field. Note that all quantities
186 * are in internal format. This is a generic implementation
187 * suitable for use with all fields and is not intended to be
191 extern mp
*field_exp(field */
*f*/
, mp */
*d*/
, mp */
*a*/
, mp */
*e*/
);
193 /*----- Creating fields ---------------------------------------------------*/
195 /* --- @field_prime@ --- *
197 * Arguments: @mp *p@ = the characteristic of the field
199 * Returns: A pointer to the field.
201 * Use: Creates a field structure for a prime field of size %$p$%,
202 * using Montgomery reduction for arithmetic.
205 extern field
*field_prime(mp */
*p*/
);
207 /* --- @field_niceprime@ --- *
209 * Arguments: @mp *p@ = the characteristic of the field
211 * Returns: A pointer to the field, or null.
213 * Use: Creates a field structure for a prime field of size %$p$%,
214 * using efficient reduction for nice primes.
217 extern field
*field_niceprime(mp */
*p*/
);
219 /* --- @field_binpoly@ --- *
221 * Arguments: @mp *p@ = an irreducible polynomial over %$\gf{2}$%
223 * Returns: A pointer to the field.
225 * Use: Creates a field structure for a binary field using naive
229 extern field
*field_binpoly(mp */
*p*/
);
231 /* --- @field_binnorm@ --- *
233 * Arguments: @mp *p@ = the reduction polynomial
234 * @mp *beta@ = representation of normal point
236 * Returns: A pointer to the field.
238 * Use: Creates a field structure for a binary field mod @p@ which
239 * uses a normal basis representation externally. Computations
240 * are still done on a polynomial-basis representation.
243 extern field
*field_binnorm(mp */
*p*/
, mp */
*beta*/
);
245 /* --- @field_parse@ --- *
247 * Arguments: @qd_parse *qd@ = parser context
249 * Returns: Field pointer if OK, or null.
251 * Use: Parses a field description, which has the form
253 * * `prime', `niceprime', `binpoly', or `binnorm'
255 * * the field modulus
256 * * for `binnorm', an optional `,' and the beta value
259 extern field
*field_parse(qd_parse */
*qd*/
);
261 /*----- That's all, folks -------------------------------------------------*/