X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/b085fd9162fa3ff5b16788ced6d11a71ffe5a5fe..34e4f738bcba58e6d8c4cabbb0b3232a65b42a9d:/field.h diff --git a/field.h b/field.h index 5a70649..bf0428a 100644 --- a/field.h +++ b/field.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: field.h,v 1.3 2002/01/13 13:48:44 mdw Exp $ + * $Id: field.h,v 1.9 2004/04/01 12:50:09 mdw Exp $ * * Definitions for field arithmetic * @@ -30,6 +30,34 @@ /*----- Revision history --------------------------------------------------* * * $Log: field.h,v $ + * 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. + * + * 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. * @@ -50,26 +78,50 @@ /*----- 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*/); + int (*samep)(field */*f*/, field */*g*/); 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*/); @@ -77,19 +129,32 @@ typedef struct field_ops { 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_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)) + +#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)) @@ -97,10 +162,14 @@ typedef struct field_ops { #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 ------------------------------------------*/ @@ -118,6 +187,31 @@ typedef struct field_ops { 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@ --- * @@ -132,6 +226,18 @@ extern mp *field_id(field */*f*/, mp */*d*/, mp */*x*/); 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}$% @@ -144,19 +250,20 @@ extern field *field_prime(mp */*p*/); 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 -------------------------------------------------*/