/* -*-c-*-
*
- * $Id: field.h,v 1.5 2004/03/23 12:08:26 mdw Exp $
+ * $Id: field.h,v 1.10 2004/04/01 21:28:41 mdw Exp $
*
* Definitions for field arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: field.h,v $
+ * Revision 1.10 2004/04/01 21:28:41 mdw
+ * Normal basis support (translates to poly basis internally). Rewrite
+ * EC and prime group table generators in awk, so that they can reuse data
+ * for repeated constants.
+ *
+ * Revision 1.9 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ * 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.
*
# 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*/);
+ int (*samep)(field */*f*/, field */*g*/);
mp *(*in)(field */*f*/, mp */*d*/, mp */*x*/);
mp *(*out)(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_SAMEP(f, g) (f)->ops->samep((f), (g))
#define F_IN(f, d, x) (f)->ops->in((f), (d), (x))
#define F_OUT(f, d, x) (f)->ops->out((f), (d), (x))
extern mp *field_id(field */*f*/, mp */*d*/, mp */*x*/);
+/* --- @field_samep@ --- *
+ *
+ * Arguments: @field *f, *g@ = two fields
+ *
+ * Returns: Nonzero if the fields are identical (not just isomorphic).
+ *
+ * Use: Checks for sameness of fields. This function does the full
+ * check, not just the field-type-specific check done by the
+ * @sampep@ field operation.
+ */
+
+extern int field_samep(field */*f*/, field */*g*/);
+
+/* --- @field_stdsamep@ --- *
+ *
+ * Arguments: @field *f, *g@ = two fields
+ *
+ * Returns: Nonzero if the fields are identical (not just isomorphic).
+ *
+ * Use: Standard sameness check, based on equality of the @m@
+ * member.
+ */
+
+extern int field_stdsamep(field */*f*/, field */*g*/);
+
/*----- Creating fields ---------------------------------------------------*/
/* --- @field_prime@ --- *
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_binnorm@ --- *
+ *
+ * Arguments: @mp *p@ = the reduction polynomial
+ * @mp *beta@ = representation of normal point
+ *
+ * Returns: A pointer to the field.
+ *
+ * Use: Creates a field structure for a binary field mod @p@ which
+ * uses a normal basis representation externally. Computations
+ * are still done on a polynomial-basis representation.
+ */
+
+extern field *field_binnorm(mp */*p*/, mp */*beta*/);
+
+/* --- @field_parse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = parser context
+ *
+ * Returns: Field pointer if OK, or null.
+ *
+ * Use: Parses a field description, which has the form
+ *
+ * * `prime', `niceprime', `binpoly', or `binnorm'
+ * * an optional `:'
+ * * the field modulus
+ * * for `binnorm', an optional `,' and the beta value
+ */
+
+extern field *field_parse(qd_parse */*qd*/);
+
/*----- That's all, folks -------------------------------------------------*/
#ifdef __cplusplus