/* -*-c-*-
*
- * $Id: field.h,v 1.1 2001/04/29 18:12:33 mdw Exp $
+ * $Id: field.h,v 1.8 2004/03/27 17:54:11 mdw Exp $
*
* Definitions for field arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: field.h,v $
+ * Revision 1.8 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
+ * Revision 1.7 2004/03/27 00:04:46 mdw
+ * Implement efficient reduction for pleasant-looking primes.
+ *
+ * Revision 1.6 2004/03/23 15:19:32 mdw
+ * Test elliptic curves more thoroughly.
+ *
+ * Revision 1.5 2004/03/23 12:08:26 mdw
+ * Random field-element selection.
+ *
+ * Revision 1.4 2004/03/21 22:52:06 mdw
+ * Merge and close elliptic curve branch.
+ *
+ * Revision 1.3.4.2 2004/03/21 22:39:46 mdw
+ * Elliptic curves on binary fields work.
+ *
+ * Revision 1.3.4.1 2004/03/20 00:13:31 mdw
+ * Projective coordinates for prime curves
+ *
+ * Revision 1.3 2002/01/13 13:48:44 mdw
+ * Further progress.
+ *
+ * Revision 1.2 2001/05/07 17:30:13 mdw
+ * Add an internal-representation no-op function.
+ *
* Revision 1.1 2001/04/29 18:12:33 mdw
* Prototype version.
*
/*----- Header files ------------------------------------------------------*/
+#ifndef CATACOMB_GRAND_H
+# include "grand.h"
+#endif
+
#ifndef CATACOMB_MP_H
# include "mp.h"
#endif
+#ifndef CATACOMB_QDPARSE_H
+# include "qdparse.h"
+#endif
+
/*----- Data structures ---------------------------------------------------*/
typedef struct field {
const struct field_ops *ops; /* Field operations */
mp *zero, *one; /* Identities in the field */
+ mp *m; /* Modulus (prime and binary) */
+ unsigned long nbits; /* Length of field element in bits */
+ size_t noctets; /* Length of element in octets */
} field;
+enum {
+ FTY_PRIME,
+ FTY_BINARY
+};
+
typedef struct field_ops {
+ /* --- General information --- */
+
+ unsigned ty; /* What kind of field this is */
+ const char *name; /* Human-readable name string */
+
/* --- Universal operations --- */
void (*destroy)(field */*f*/);
+ mp *(*rand)(field */*f*/, mp */*d*/, grand */*r*/);
mp *(*in)(field */*f*/, mp */*d*/, mp */*x*/);
mp *(*out)(field */*f*/, mp */*d*/, mp */*x*/);
+ int (*zerop)(field */*f*/, mp */*x*/);
+ mp *(*neg)(field */*f*/, mp */*d*/, mp */*x*/);
mp *(*add)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
mp *(*sub)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
mp *(*mul)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
mp *(*sqr)(field */*f*/, mp */*d*/, mp */*x*/);
mp *(*inv)(field */*f*/, mp */*d*/, mp */*x*/);
mp *(*reduce)(field */*f*/, mp */*d*/, mp */*x*/);
+ mp *(*sqrt)(field */*f*/, mp */*d*/, mp */*x*/);
+
+ /* --- Operations for binary fields only --- */
+
+ mp *(*quadsolve)(field */*f*/, mp */*d*/, mp */*x*/);
/* --- Operations for prime fields only --- */
mp *(*dbl)(field */*f*/, mp */*d*/, mp */*x*/);
mp *(*tpl)(field */*f*/, mp */*d*/, mp */*x*/);
- mp *(*sqrt)(field */*f*/, mp */*d*/, mp */*x*/);
+ mp *(*qdl)(field */*f*/, mp */*d*/, mp */*x*/);
+ mp *(*hlv)(field */*f*/, mp */*d*/, mp */*x*/);
} field_ops;
+#define F_TYPE(f) (f)->ops->ty
+#define F_NAME(f) (f)->ops->name
+
#define F_DESTROY(f) (f)->ops->destroy((f))
+#define F_RAND(f, d, r) (f)->ops->rand((f), (d), (r))
#define F_IN(f, d, x) (f)->ops->in((f), (d), (x))
#define F_OUT(f, d, x) (f)->ops->out((f), (d), (x))
+
+#define F_ZEROP(f, x) (f)->ops->zerop((f), (x))
+#define F_NEG(f, d, x) (f)->ops->neg((f), (d), (x))
#define F_ADD(f, d, x, y) (f)->ops->add((f), (d), (x), (y))
#define F_SUB(f, d, x, y) (f)->ops->sub((f), (d), (x), (y))
#define F_MUL(f, d, x, y) (f)->ops->mul((f), (d), (x), (y))
#define F_SQR(f, d, x) (f)->ops->sqr((f), (d), (x))
#define F_INV(f, d, x) (f)->ops->inv((f), (d), (x))
#define F_REDUCE(f, d, x) (f)->ops->reduce((f), (d), (x))
+#define F_SQRT(f, d, x) (f)->ops->sqrt((f), (d), (x))
+
+#define F_QUADSOLVE(f, d, x) (f)->ops->quadsolve((f), (d), (x))
#define F_DBL(f, d, x) (f)->ops->dbl((f), (d), (x))
#define F_TPL(f, d, x) (f)->ops->tpl((f), (d), (x))
-#define F_SQRT(f, d, x) (f)->ops->sqrt((f), (d), (x))
+#define F_QDL(f, d, x) (f)->ops->qdl((f), (d), (x))
+#define F_HLV(f, d, x) (f)->ops->hlv((f), (d), (x))
+
+/*----- Helpful field operations ------------------------------------------*/
+
+/* --- @field_id@ --- *
+ *
+ * Arguments: @field *f@ = pointer to a field
+ * @mp *d@ = a destination element
+ * @mp *x@ = a source element
+ *
+ * Returns: The result element.
+ *
+ * Use: An identity operation which can be used if your field has no
+ * internal representation.
+ */
+
+extern mp *field_id(field */*f*/, mp */*d*/, mp */*x*/);
/*----- Creating fields ---------------------------------------------------*/
extern field *field_prime(mp */*p*/);
+/* --- @field_niceprime@ --- *
+ *
+ * Arguments: @mp *p@ = the characteristic of the field
+ *
+ * Returns: A pointer to the field.
+ *
+ * Use: Creates a field structure for a prime field of size %$p$%,
+ * using efficient reduction for nice primes.
+ */
+
+extern field *field_niceprime(mp */*p*/);
+
/* --- @field_binpoly@ --- *
*
* Arguments: @mp *p@ = an irreducible polynomial over %$\gf{2}$%
extern field *field_binpoly(mp */*p*/);
-/* --- @field_binsparsepoly@ --- *
+/* --- @field_parse@ --- *
*
- * Arguments: @unsigned deg@ = the degree of the field polynomial
- * @const unsigned *c@ = degrees of nonzero coefficients
+ * Arguments: @qd_parse *qd@ = parser context
*
- * Returns: A pointer to the field.
+ * Returns: Field pointer if OK, or null.
+ *
+ * Use: Parses a field description, which has the form
*
- * Use: Creates a field structure for a binary field taking advantage
- * of the sparseness of the given polynomial to improve
- * reduction performance.
+ * * `prime', `niceprime' or `binpoly'
+ * * an optional `:'
+ * * the field modulus
*/
-extern field *field_binsparsepoly(unsigned /*deg*/, const unsigned */*c*/);
+extern field *field_parse(qd_parse */*qd*/);
/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff