diff options
Diffstat (limited to 'moon-abe/pbc-0.5.14/include/pbc_field.h')
| -rw-r--r-- | moon-abe/pbc-0.5.14/include/pbc_field.h | 694 |
1 files changed, 694 insertions, 0 deletions
diff --git a/moon-abe/pbc-0.5.14/include/pbc_field.h b/moon-abe/pbc-0.5.14/include/pbc_field.h new file mode 100644 index 00000000..5bcb8c83 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_field.h @@ -0,0 +1,694 @@ +/* + * field_t: represents fields, rings and groups. + * element_t: represents an element of a field_t. + */ + +// Requires: +// * stdarg.h +// * stdio.h +// * gmp.h +// * utils.h +#ifndef __PBC_FIELD_H__ +#define __PBC_FIELD_H__ + +struct field_s; + +struct element_s { + struct field_s *field; + void *data; +}; +typedef struct element_s *element_ptr; +typedef struct element_s element_t[1]; + +struct element_pp_s { + struct field_s *field; + void *data; +}; +typedef struct element_pp_s element_pp_t[1]; +typedef struct element_pp_s *element_pp_ptr; + +void pbc_assert(int expr, char *msg, const char *func); +void pbc_assert_match2(element_ptr a, element_ptr b, const char *func); +void pbc_assert_match3(element_ptr a, element_ptr b, element_ptr c, + const char *func); + +struct multiz_s; +typedef struct multiz_s *multiz; + +struct pairing_s; +struct field_s { + void (*field_clear)(struct field_s *f); + void (*init)(element_ptr); + void (*clear)(element_ptr); + + void (*set_mpz)(element_ptr, mpz_ptr); + void (*set_multiz)(element_ptr, multiz); + void (*set)(element_ptr, element_ptr); + void (*set0)(element_ptr); + void (*set1)(element_ptr); + int (*set_str)(element_ptr e, const char *s, int base); + size_t(*out_str)(FILE *stream, int base, element_ptr); + void (*add)(element_ptr, element_ptr, element_ptr); + void (*sub)(element_ptr, element_ptr, element_ptr); + void (*mul)(element_ptr, element_ptr, element_ptr); + + int (*is_sqr)(element_ptr); + void (*sqrt)(element_ptr, element_ptr); + + // Defaults exist for these functions. + int (*item_count)(element_ptr); + element_ptr (*item)(element_ptr, int); + element_ptr (*get_x)(element_ptr); + element_ptr (*get_y)(element_ptr); + void (*set_si)(element_ptr, signed long int); + void (*add_ui)(element_ptr, element_ptr, unsigned long int); + void (*mul_mpz)(element_ptr, element_ptr, mpz_ptr); + void (*mul_si)(element_ptr, element_ptr, signed long int); + void (*div)(element_ptr, element_ptr, element_ptr); + void (*doub)(element_ptr, element_ptr); // Can't call it "double"! + void (*multi_doub)(element_ptr*, element_ptr*, int n); + void (*multi_add)(element_ptr*, element_ptr*, element_ptr*, int n); + void (*halve)(element_ptr, element_ptr); + void (*square)(element_ptr, element_ptr); + + void (*cubic) (element_ptr, element_ptr); + void (*pow_mpz)(element_ptr, element_ptr, mpz_ptr); + void (*invert)(element_ptr, element_ptr); + void (*neg)(element_ptr, element_ptr); + void (*random)(element_ptr); + void (*from_hash)(element_ptr, void *data, int len); + int (*is1)(element_ptr); + int (*is0)(element_ptr); + int (*sign)(element_ptr); // satisfies sign(x) = -sign(-x) + int (*cmp)(element_ptr, element_ptr); + int (*to_bytes)(unsigned char *data, element_ptr); + int (*from_bytes)(element_ptr, unsigned char *data); + int (*length_in_bytes)(element_ptr); + int fixed_length_in_bytes; // length of an element in bytes; -1 for variable + int (*snprint)(char *s, size_t n, element_ptr e); + void (*to_mpz)(mpz_ptr, element_ptr); + void (*out_info)(FILE *, struct field_s *); + void (*pp_init)(element_pp_t p, element_t in); + void (*pp_clear)(element_pp_t p); + void (*pp_pow)(element_t out, mpz_ptr power, element_pp_t p); + + struct pairing_s *pairing; + + mpz_t order; // 0 for infinite order + element_ptr nqr; // nonquadratic residue + + char *name; + void *data; +}; +typedef struct field_s *field_ptr; +typedef struct field_s field_t[1]; + +typedef void (*fieldmap) (element_t dst, element_t src); + +void field_out_info(FILE* out, field_ptr f); + +/*@manual internal +Initialize 'e' to be an element of the algebraic structure 'f' +and set it to be the zero element. +*/ +static inline void element_init(element_t e, field_ptr f) { + e->field = f; + f->init(e); +} + +element_ptr element_new(field_ptr f); +void element_free(element_ptr e); + +/*@manual einit +Initialize 'e' to be an element of the algebraic structure that 'e2' +lies in. +*/ +static inline void element_init_same_as(element_t e, element_t e2) { + element_init(e, e2->field); +} + +/*@manual einit +Free the space occupied by 'e'. Call this when +the variable 'e' is no longer needed. +*/ +static inline void element_clear(element_t e) { + e->field->clear(e); +} + +/*@manual eio +Output 'e' on 'stream' in base 'base'. The base must be between +2 and 36. +*/ +static inline size_t element_out_str(FILE * stream, int base, element_t e) { + return e->field->out_str(stream, base, e); +} + +/*@manual eio +*/ +int element_printf(const char *format, ...); + +/*@manual eio +*/ +int element_fprintf(FILE * stream, const char *format, ...); + +/*@manual eio +*/ +int element_snprintf(char *buf, size_t size, const char *fmt, ...); + +/*@manual eio +Same as printf family +except also has the 'B' conversion specifier for types +of *element_t*, and 'Y', 'Z' conversion specifiers for ++mpz_t+. For example if 'e' is of type ++element_t+ then + + element_printf("%B\n", e); + +will print the value of 'e' in a human-readable form on standard output. +*/ +int element_vsnprintf(char *buf, size_t size, const char *fmt, va_list ap); + +/*@manual eio +Convert an element to a human-friendly string. +Behaves as *snprintf* but only on one element at a time. +*/ +static inline int element_snprint(char *s, size_t n, element_t e) { + return e->field->snprint(s, n, e); +} + +static inline void element_set_multiz(element_t e, multiz m) { + e->field->set_multiz(e, m); +} + +/*@manual eio +Set the element 'e' from 's', a null-terminated C string in base 'base'. +Whitespace is ignored. Points have the form "['x,y']" or "'O'", +while polynomials have the form "['a0,...,an']". +Returns number of characters read (unlike GMP's mpz_set_str). +A return code of zero means PBC could not find a well-formed string +describing an element. +*/ +static inline int element_set_str(element_t e, const char *s, int base) { + return e->field->set_str(e, s, base); +} + +/*@manual eassign +Set 'e' to zero. +*/ +static inline void element_set0(element_t e) { + e->field->set0(e); +} + +/*@manual eassign +Set 'e' to one. +*/ +static inline void element_set1(element_t e) { + e->field->set1(e); +} + +/*@manual eassign +Set 'e' to 'i'. +*/ +static inline void element_set_si(element_t e, signed long int i) { + e->field->set_si(e, i); +} + +/*@manual eassign +Set 'e' to 'z'. +*/ +static inline void element_set_mpz(element_t e, mpz_t z) { + e->field->set_mpz(e, z); +} + +/*@manual eassign +Set 'e' to 'a'. +*/ +static inline void element_set(element_t e, element_t a) { + PBC_ASSERT_MATCH2(e, a); + e->field->set(e, a); +} + +static inline void element_add_ui(element_t n, element_t a, + unsigned long int b) { + n->field->add_ui(n, a, b); +} + +/*@manual econvert +Converts 'e' to a GMP integer 'z' +if such an operation makes sense +*/ +static inline void element_to_mpz(mpz_t z, element_t e) { + e->field->to_mpz(z, e); +} + +static inline long element_to_si(element_t e) { + mpz_t z; + mpz_init(z); + e->field->to_mpz(z, e); + long res = mpz_get_si(z); + mpz_clear(z); + return res; +} + +/*@manual econvert +Generate an element 'e' deterministically from +the 'len' bytes stored in the buffer 'data'. +*/ +static inline void element_from_hash(element_t e, void *data, int len) { + e->field->from_hash(e, data, len); +} + +/*@manual earith +Set 'n' to 'a' + 'b'. +*/ +static inline void element_add(element_t n, element_t a, element_t b) { + PBC_ASSERT_MATCH3(n, a, b); + n->field->add(n, a, b); +} + +/*@manual earith +Set 'n' to 'a' - 'b'. +*/ +static inline void element_sub(element_t n, element_t a, element_t b) { + PBC_ASSERT_MATCH3(n, a, b); + n->field->sub(n, a, b); +} + +/*@manual earith +Set 'n' = 'a' 'b'. +*/ +static inline void element_mul(element_t n, element_t a, element_t b) { + PBC_ASSERT_MATCH3(n, a, b); + n->field->mul(n, a, b); +} + +static inline void element_cubic(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->cubic(n, a); +} + +/*@manual earith +*/ +static inline void element_mul_mpz(element_t n, element_t a, mpz_t z) { + PBC_ASSERT_MATCH2(n, a); + n->field->mul_mpz(n, a, z); +} + +/*@manual earith +Set 'n' = 'a' 'z', that is 'a' + 'a' + ... + 'a' where there are 'z' 'a'#'s#. +*/ +static inline void element_mul_si(element_t n, element_t a, + signed long int z) { + PBC_ASSERT_MATCH2(n, a); + n->field->mul_si(n, a, z); +} + +/*@manual earith +'z' must be an element of a integer mod ring (i.e. *Z*~n~ for some n). +Set 'c' = 'a' 'z', that is 'a' + 'a' + ... + 'a' +where there are 'z' 'a''s. +*/ +static inline void element_mul_zn(element_t c, element_t a, element_t z) { + mpz_t z0; + PBC_ASSERT_MATCH2(c, a); + //TODO: check z->field is Zn + mpz_init(z0); + element_to_mpz(z0, z); + element_mul_mpz(c, a, z0); + mpz_clear(z0); +} + +/*@manual earith +Set 'n' = 'a' / 'b'. +*/ +static inline void element_div(element_t n, element_t a, element_t b) { + PBC_ASSERT_MATCH3(n, a, b); + n->field->div(n, a, b); +} + +/*@manual earith +Set 'n' = 'a' + 'a'. +*/ +static inline void element_double(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->doub(n, a); +} + +// Set n_i = a_i + a_i for all i at one time. +// Uses multi_doub(), which only elliptic curves have at the moment. +void element_multi_double(element_t n[], element_t a[], int m); + +// Set n_i =a_i + b_i for all i at one time. +// Uses multi_add(), which only elliptic curves have at the moment. +void element_multi_add(element_t n[], element_t a[],element_t b[], int m); + +/*@manual earith +Set 'n' = 'a/2' +*/ +static inline void element_halve(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->halve(n, a); +} + +/*@manual earith +Set 'n' = 'a'^2^ +*/ +static inline void element_square(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->square(n, a); +} + +/*@manual epow +Set 'x' = 'a'^'n'^, that is +'a' times 'a' times ... times 'a' where there are 'n' 'a'#'s#. +*/ +static inline void element_pow_mpz(element_t x, element_t a, mpz_t n) { + PBC_ASSERT_MATCH2(x, a); + x->field->pow_mpz(x, a, n); +} + +/*@manual epow +Set 'x' = 'a'^'n'^, where 'n' is an element of a ring *Z*~N~ +for some 'N' (typically the order of the algebraic structure 'x' lies in). +*/ +static inline void element_pow_zn(element_t x, element_t a, element_t n) { + mpz_t z; + PBC_ASSERT_MATCH2(x, a); + mpz_init(z); + element_to_mpz(z, n); + element_pow_mpz(x, a, z); + mpz_clear(z); +} + +/*@manual earith +Set 'n' = -'a'. +*/ +static inline void element_neg(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->neg(n, a); +} + +/*@manual earith +Set 'n' to the inverse of 'a'. +*/ +static inline void element_invert(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->invert(n, a); +} + +/*@manual erandom +If the 'e' lies in a finite algebraic structure, +assigns a uniformly random element to 'e'. +*/ +static inline void element_random(element_t e) { + e->field->random(e); +} + +/*@manual ecmp +Returns true if 'n' is 1. +*/ +static inline int element_is1(element_t n) { + return n->field->is1(n); +} + +/*@manual ecmp +Returns true if 'n' is 0. +*/ +static inline int element_is0(element_t n) { + return n->field->is0(n); +} + +/*@manual ecmp +Returns 0 if 'a' and 'b' are the same, nonzero otherwise. +*/ +static inline int element_cmp(element_t a, element_t b) { + PBC_ASSERT_MATCH2(a, b); + return a->field->cmp(a, b); +} + +/*@manual ecmp +Returns nonzero if 'a' is a perfect square (quadratic residue), +zero otherwise. +*/ +static inline int element_is_sqr(element_t a) { + return a->field->is_sqr(a); +} + +/*@manual ecmp +*/ +static inline int element_sgn(element_t a) { + return a->field->sign(a); +} + +/*@manual ecmp +If 'a' is zero, returns 0. For nozero 'a' the behaviour depends on +the algebraic structure, but has the property that +element_sgn('a') = -element_sgn(-'a') +and +element_sgn('a') = 0 implies 'a' = 0 with overwhelming probability. +*/ +static inline int element_sign(element_t a) { + return a->field->sign(a); +} + +static inline void element_sqrt(element_t a, element_t b) { + PBC_ASSERT_MATCH2(a, b); + a->field->sqrt(a, b); +} + +/*@manual etrade +Returns the length in bytes the element 'e' will take to represent +*/ +static inline int element_length_in_bytes(element_t e) { + if (e->field->fixed_length_in_bytes < 0) { + return e->field->length_in_bytes(e); + } else { + return e->field->fixed_length_in_bytes; + } +} + +/*@manual etrade +Converts 'e' to byte, writing the result in the buffer 'data'. +The number of bytes it will write can be determined from calling +*element_length_in_bytes()*. Returns number of bytes written. +*/ +static inline int element_to_bytes(unsigned char *data, element_t e) { + return e->field->to_bytes(data, e); +} + +/*@manual etrade +Reads 'e' from the buffer 'data', and returns the number of bytes read. +*/ +static inline int element_from_bytes(element_t e, unsigned char *data) { + return e->field->from_bytes(e, data); +} + +/*@manual epow +Sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^, and is generally faster than +performing two separate exponentiations. +*/ +void element_pow2_mpz(element_t x, element_t a1, mpz_t n1, element_t a2, + mpz_t n2); +/*@manual epow +Also sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^, +but 'n1', 'n2' must be elements of a ring *Z*~n~ for some integer n. +*/ +static inline void element_pow2_zn(element_t x, element_t a1, element_t n1, + element_t a2, element_t n2) { + mpz_t z1, z2; + mpz_init(z1); + mpz_init(z2); + element_to_mpz(z1, n1); + element_to_mpz(z2, n2); + element_pow2_mpz(x, a1, z1, a2, z2); + mpz_clear(z1); + mpz_clear(z2); +} + +/*@manual epow +Sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^ 'a3'^'n3'^, +generally faster than performing three separate exponentiations. +*/ +void element_pow3_mpz(element_t x, element_t a1, mpz_t n1, + element_t a2, mpz_t n2, element_t a3, mpz_t n3); + +/*@manual epow +Also sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^ 'a3'^'n3'^, +but 'n1', 'n2', 'n3' must be elements of a ring *Z*~n~ for some integer n. +*/ +static inline void element_pow3_zn(element_t x, element_t a1, element_t n1, + element_t a2, element_t n2, + element_t a3, element_t n3) { + mpz_t z1, z2, z3; + mpz_init(z1); + mpz_init(z2); + mpz_init(z3); + element_to_mpz(z1, n1); + element_to_mpz(z2, n2); + element_to_mpz(z3, n3); + element_pow3_mpz(x, a1, z1, a2, z2, a3, z3); + mpz_clear(z1); + mpz_clear(z2); + mpz_clear(z3); +} + +void field_clear(field_ptr f); + +element_ptr field_get_nqr(field_ptr f); +void field_set_nqr(field_ptr f, element_t nqr); +void field_gen_nqr(field_ptr f); + +void field_init(field_ptr f); + +static inline int mpz_is0(mpz_t z) { + return !mpz_sgn(z); + //return !mpz_cmp_ui(z, 0); +} + +/*@manual etrade +Assumes 'e' is a point on an elliptic curve. +Writes the x-coordinate of 'e' to the buffer 'data' +*/ +int element_to_bytes_x_only(unsigned char *data, element_t e); +/*@manual etrade +Assumes 'e' is a point on an elliptic curve. +Sets 'e' to a point with +x-coordinate represented by the buffer 'data'. This is not unique. +For each 'x'-coordinate, there exist two different points, at least +for the elliptic curves in PBC. (They are inverses of each other.) +*/ +int element_from_bytes_x_only(element_t e, unsigned char *data); +/*@manual etrade +Assumes 'e' is a point on an elliptic curve. +Returns the length in bytes needed to hold the x-coordinate of 'e'. +*/ +int element_length_in_bytes_x_only(element_t e); + +/*@manual etrade +If possible, outputs a compressed form of the element 'e' to +the buffer of bytes 'data'. +Currently only implemented for points on an elliptic curve. +*/ +int element_to_bytes_compressed(unsigned char *data, element_t e); + +/*@manual etrade +Sets element 'e' to the element in compressed form in the buffer of bytes +'data'. +Currently only implemented for points on an elliptic curve. +*/ +int element_from_bytes_compressed(element_t e, unsigned char *data); + +/*@manual etrade +Returns the number of bytes needed to hold 'e' in compressed form. +Currently only implemented for points on an elliptic curve. +*/ +int element_length_in_bytes_compressed(element_t e); + +/*@manual epow +Prepare to exponentiate an element 'in', and store preprocessing information +in 'p'. +*/ +static inline void element_pp_init(element_pp_t p, element_t in) { + p->field = in->field; + in->field->pp_init(p, in); +} + +/*@manual epow +Clear 'p'. Should be called after 'p' is no longer needed. +*/ +static inline void element_pp_clear(element_pp_t p) { + p->field->pp_clear(p); +} + +/*@manual epow +Raise 'in' to 'power' and store the result in 'out', where 'in' +is a previously preprocessed element, that is, the second argument +passed to a previous *element_pp_init* call. +*/ +static inline void element_pp_pow(element_t out, mpz_ptr power, + element_pp_t p) { + p->field->pp_pow(out, power, p); +} + +/*@manual epow +Same except 'power' is an element of *Z*~n~ for some integer n. +*/ +static inline void element_pp_pow_zn(element_t out, element_t power, + element_pp_t p) { + mpz_t z; + mpz_init(z); + element_to_mpz(z, power); + element_pp_pow(out, z, p); + mpz_clear(z); +} + +void pbc_mpz_out_raw_n(unsigned char *data, int n, mpz_t z); +void pbc_mpz_from_hash(mpz_t z, mpz_t limit, + unsigned char *data, unsigned int len); + +/*@manual etrade +For points, returns the number of coordinates. +For polynomials, returns the number of coefficients. +Otherwise returns zero. +*/ +static inline int element_item_count(element_t e) { + return e->field->item_count(e); +} + +/*@manual etrade +For points, returns 'n'#th# coordinate. +For polynomials, returns coefficient of 'x^n^'. +Otherwise returns NULL. +The element the return value points to may be modified. +*/ +static inline element_ptr element_item(element_t e, int i) { + // TODO: Document the following: + // For polynomials, never zero the leading coefficient, e.g. never write: + // element_set0(element_item(f, poly_degree(f))); + // Use poly_set_coeff0() to zero the leading coefficient. + return e->field->item(e, i); +} + +// Returns the field containing the items. +// Returns NULL if there are no items. +static inline field_ptr element_item_field(element_t e) { + if (!element_item_count(e)) return NULL; + return element_item(e, 0)->field; +} + +/*@manual etrade +Equivalent to `element_item(a, 0)`. +*/ +static inline element_ptr element_x(element_ptr a) { + return a->field->get_x(a); +} +/*@manual etrade +Equivalent to `element_item(a, 1)`. +*/ +static inline element_ptr element_y(element_ptr a) { + return a->field->get_y(a); +} + +/*@manual epow +Computes 'x' such that 'g^x^ = h' by brute force, where +'x' lies in a field where `element_set_mpz()` makes sense. +*/ +void element_dlog_brute_force(element_t x, element_t g, element_t h); + +/*@manual epow +Computes 'x' such that 'g^x^ = h' using Pollard rho method, where +'x' lies in a field where `element_set_mpz()` makes sense. +*/ +void element_dlog_pollard_rho(element_t x, element_t g, element_t h); + +// Trial division up to a given limit. If limit == NULL, then there is no limit. +// Call the callback for each factor found, abort and return 1 if the callback +// returns nonzero, otherwise return 0. +int pbc_trial_divide(int (*fun)(mpz_t factor, + unsigned int multiplicity, + void *scope_ptr), + void *scope_ptr, + mpz_t n, + mpz_ptr limit); + +#endif // __PBC_FIELD_H__ |