X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/b0ab12e6a6cb035df2b6312df7ad1736af0a6128..b817bfc642225b8c3c0b6a7e42d1fb949b61a606:/field.h diff --git a/field.h b/field.h index 35e9df0..5790284 100644 --- a/field.h +++ b/field.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: field.h,v 1.1 2001/04/29 18:12:33 mdw Exp $ + * $Id: field.h,v 1.11 2004/04/08 01:36:15 mdw Exp $ * * Definitions for field arithmetic * @@ -27,14 +27,6 @@ * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* - * - * $Log: field.h,v $ - * Revision 1.1 2001/04/29 18:12:33 mdw - * Prototype version. - * - */ - #ifndef CATACOMB_FIELD_H #define CATACOMB_FIELD_H @@ -44,55 +36,139 @@ /*----- 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*/); 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_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)) #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*/); + +/* --- @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 ---------------------------------------------------*/ @@ -108,6 +184,18 @@ typedef struct field_ops { 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}$% @@ -120,19 +208,35 @@ extern field *field_prime(mp */*p*/); extern field *field_binpoly(mp */*p*/); -/* --- @field_binsparsepoly@ --- * +/* --- @field_binnorm@ --- * * - * Arguments: @unsigned deg@ = the degree of the field polynomial - * @const unsigned *c@ = degrees of nonzero coefficients + * 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 taking advantage - * of the sparseness of the given polynomial to improve - * reduction performance. + * 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_binsparsepoly(unsigned /*deg*/, const unsigned */*c*/); +extern field *field_parse(qd_parse */*qd*/); /*----- That's all, folks -------------------------------------------------*/