3 * $Id: field.h,v 1.9 2004/04/01 12:50:09 mdw Exp $
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 /*----- Revision history --------------------------------------------------*
33 * Revision 1.9 2004/04/01 12:50:09 mdw
34 * Add cyclic group abstraction, with test code. Separate off exponentation
35 * functions for better static linking. Fix a buttload of bugs on the way.
36 * Generally ensure that negative exponents do inversion correctly. Add
37 * table of standard prime-field subgroups. (Binary field subgroups are
38 * currently unimplemented but easy to add if anyone ever finds a good one.)
40 * Revision 1.8 2004/03/27 17:54:11 mdw
41 * Standard curves and curve checking.
43 * Revision 1.7 2004/03/27 00:04:46 mdw
44 * Implement efficient reduction for pleasant-looking primes.
46 * Revision 1.6 2004/03/23 15:19:32 mdw
47 * Test elliptic curves more thoroughly.
49 * Revision 1.5 2004/03/23 12:08:26 mdw
50 * Random field-element selection.
52 * Revision 1.4 2004/03/21 22:52:06 mdw
53 * Merge and close elliptic curve branch.
55 * Revision 1.3.4.2 2004/03/21 22:39:46 mdw
56 * Elliptic curves on binary fields work.
58 * Revision 1.3.4.1 2004/03/20 00:13:31 mdw
59 * Projective coordinates for prime curves
61 * Revision 1.3 2002/01/13 13:48:44 mdw
64 * Revision 1.2 2001/05/07 17:30:13 mdw
65 * Add an internal-representation no-op function.
67 * Revision 1.1 2001/04/29 18:12:33 mdw
72 #ifndef CATACOMB_FIELD_H
73 #define CATACOMB_FIELD_H
79 /*----- Header files ------------------------------------------------------*/
81 #ifndef CATACOMB_GRAND_H
89 #ifndef CATACOMB_QDPARSE_H
93 /*----- Data structures ---------------------------------------------------*/
95 typedef struct field
{
96 const struct field_ops
*ops
; /* Field operations */
97 mp
*zero
, *one
; /* Identities in the field */
98 mp
*m
; /* Modulus (prime and binary) */
99 unsigned long nbits
; /* Length of field element in bits */
100 size_t noctets
; /* Length of element in octets */
108 typedef struct field_ops
{
110 /* --- General information --- */
112 unsigned ty
; /* What kind of field this is */
113 const char *name
; /* Human-readable name string */
115 /* --- Universal operations --- */
117 void (*destroy
)(field */
*f*/
);
118 mp
*(*rand
)(field */
*f*/
, mp */
*d*/
, grand */
*r*/
);
119 int (*samep
)(field */
*f*/
, field */
*g*/
);
121 mp
*(*in
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
122 mp
*(*out
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
124 int (*zerop
)(field */
*f*/
, mp */
*x*/
);
125 mp
*(*neg
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
126 mp
*(*add
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
, mp */
*y*/
);
127 mp
*(*sub
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
, mp */
*y*/
);
128 mp
*(*mul
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
, mp */
*y*/
);
129 mp
*(*sqr
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
130 mp
*(*inv
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
131 mp
*(*reduce
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
132 mp
*(*sqrt
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
134 /* --- Operations for binary fields only --- */
136 mp
*(*quadsolve
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
138 /* --- Operations for prime fields only --- */
140 mp
*(*dbl
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
141 mp
*(*tpl
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
142 mp
*(*qdl
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
143 mp
*(*hlv
)(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
147 #define F_TYPE(f) (f)->ops->ty
148 #define F_NAME(f) (f)->ops->name
150 #define F_DESTROY(f) (f)->ops->destroy((f))
151 #define F_RAND(f, d, r) (f)->ops->rand((f), (d), (r))
152 #define F_SAMEP(f, g) (f)->ops->samep((f), (g))
154 #define F_IN(f, d, x) (f)->ops->in((f), (d), (x))
155 #define F_OUT(f, d, x) (f)->ops->out((f), (d), (x))
157 #define F_ZEROP(f, x) (f)->ops->zerop((f), (x))
158 #define F_NEG(f, d, x) (f)->ops->neg((f), (d), (x))
159 #define F_ADD(f, d, x, y) (f)->ops->add((f), (d), (x), (y))
160 #define F_SUB(f, d, x, y) (f)->ops->sub((f), (d), (x), (y))
161 #define F_MUL(f, d, x, y) (f)->ops->mul((f), (d), (x), (y))
162 #define F_SQR(f, d, x) (f)->ops->sqr((f), (d), (x))
163 #define F_INV(f, d, x) (f)->ops->inv((f), (d), (x))
164 #define F_REDUCE(f, d, x) (f)->ops->reduce((f), (d), (x))
165 #define F_SQRT(f, d, x) (f)->ops->sqrt((f), (d), (x))
167 #define F_QUADSOLVE(f, d, x) (f)->ops->quadsolve((f), (d), (x))
169 #define F_DBL(f, d, x) (f)->ops->dbl((f), (d), (x))
170 #define F_TPL(f, d, x) (f)->ops->tpl((f), (d), (x))
171 #define F_QDL(f, d, x) (f)->ops->qdl((f), (d), (x))
172 #define F_HLV(f, d, x) (f)->ops->hlv((f), (d), (x))
174 /*----- Helpful field operations ------------------------------------------*/
176 /* --- @field_id@ --- *
178 * Arguments: @field *f@ = pointer to a field
179 * @mp *d@ = a destination element
180 * @mp *x@ = a source element
182 * Returns: The result element.
184 * Use: An identity operation which can be used if your field has no
185 * internal representation.
188 extern mp
*field_id(field */
*f*/
, mp */
*d*/
, mp */
*x*/
);
190 /* --- @field_samep@ --- *
192 * Arguments: @field *f, *g@ = two fields
194 * Returns: Nonzero if the fields are identical (not just isomorphic).
196 * Use: Checks for sameness of fields. This function does the full
197 * check, not just the field-type-specific check done by the
198 * @sampep@ field operation.
201 extern int field_samep(field */
*f*/
, field */
*g*/
);
203 /* --- @field_stdsamep@ --- *
205 * Arguments: @field *f, *g@ = two fields
207 * Returns: Nonzero if the fields are identical (not just isomorphic).
209 * Use: Standard sameness check, based on equality of the @m@
213 extern int field_stdsamep(field */
*f*/
, field */
*g*/
);
215 /*----- Creating fields ---------------------------------------------------*/
217 /* --- @field_prime@ --- *
219 * Arguments: @mp *p@ = the characteristic of the field
221 * Returns: A pointer to the field.
223 * Use: Creates a field structure for a prime field of size %$p$%,
224 * using Montgomery reduction for arithmetic.
227 extern field
*field_prime(mp */
*p*/
);
229 /* --- @field_niceprime@ --- *
231 * Arguments: @mp *p@ = the characteristic of the field
233 * Returns: A pointer to the field.
235 * Use: Creates a field structure for a prime field of size %$p$%,
236 * using efficient reduction for nice primes.
239 extern field
*field_niceprime(mp */
*p*/
);
241 /* --- @field_binpoly@ --- *
243 * Arguments: @mp *p@ = an irreducible polynomial over %$\gf{2}$%
245 * Returns: A pointer to the field.
247 * Use: Creates a field structure for a binary field using naive
251 extern field
*field_binpoly(mp */
*p*/
);
253 /* --- @field_parse@ --- *
255 * Arguments: @qd_parse *qd@ = parser context
257 * Returns: Field pointer if OK, or null.
259 * Use: Parses a field description, which has the form
261 * * `prime', `niceprime' or `binpoly'
263 * * the field modulus
266 extern field
*field_parse(qd_parse */
*qd*/
);
268 /*----- That's all, folks -------------------------------------------------*/