1 /*
2 * field_t: represents fields, rings and groups.
3 * element_t: represents an element of a field_t.
4 */
5
6 // Requires:
7 // * stdarg.h
8 // * stdio.h
9 // * gmp.h
10 // * utils.h
11 #ifndef __PBC_FIELD_H__
12 #define __PBC_FIELD_H__
13
14 struct field_s;
15
16 struct element_s {
17 struct field_s *field;
18 void *data;
19 };
20 typedef struct element_s *element_ptr;
21 typedef struct element_s element_t[1];
22
23 struct element_pp_s {
24 struct field_s *field;
25 void *data;
26 };
27 typedef struct element_pp_s element_pp_t[1];
28 typedef struct element_pp_s *element_pp_ptr;
29
30 void pbc_assert(int expr, char *msg, const char *func);
31 void pbc_assert_match2(element_ptr a, element_ptr b, const char *func);
32 void pbc_assert_match3(element_ptr a, element_ptr b, element_ptr c,
33 const char *func);
34
35 struct multiz_s;
36 typedef struct multiz_s *multiz;
37
38 struct pairing_s;
39 struct field_s {
40 void (*field_clear)(struct field_s *f);
41 void (*init)(element_ptr);
42 void (*clear)(element_ptr);
43
44 void (*set_mpz)(element_ptr, mpz_ptr);
45 void (*set_multiz)(element_ptr, multiz);
46 void (*set)(element_ptr, element_ptr);
47 void (*set0)(element_ptr);
48 void (*set1)(element_ptr);
49 int (*set_str)(element_ptr e, const char *s, int base);
50 size_t(*out_str)(FILE *stream, int base, element_ptr);
51 void (*add)(element_ptr, element_ptr, element_ptr);
52 void (*sub)(element_ptr, element_ptr, element_ptr);
53 void (*mul)(element_ptr, element_ptr, element_ptr);
54
55 int (*is_sqr)(element_ptr);
56 void (*sqrt)(element_ptr, element_ptr);
57
58 // Defaults exist for these functions.
59 int (*item_count)(element_ptr);
60 element_ptr (*item)(element_ptr, int);
61 element_ptr (*get_x)(element_ptr);
62 element_ptr (*get_y)(element_ptr);
63 void (*set_si)(element_ptr, signed long int);
64 void (*add_ui)(element_ptr, element_ptr, unsigned long int);
65 void (*mul_mpz)(element_ptr, element_ptr, mpz_ptr);
66 void (*mul_si)(element_ptr, element_ptr, signed long int);
67 void (*div)(element_ptr, element_ptr, element_ptr);
68 void (*doub)(element_ptr, element_ptr); // Can't call it "double"!
69 void (*multi_doub)(element_ptr*, element_ptr*, int n);
70 void (*multi_add)(element_ptr*, element_ptr*, element_ptr*, int n);
71 void (*halve)(element_ptr, element_ptr);
72 void (*square)(element_ptr, element_ptr);
73
74 void (*cubic) (element_ptr, element_ptr);
75 void (*pow_mpz)(element_ptr, element_ptr, mpz_ptr);
76 void (*invert)(element_ptr, element_ptr);
77 void (*neg)(element_ptr, element_ptr);
78 void (*random)(element_ptr);
79 void (*from_hash)(element_ptr, void *data, int len);
80 int (*is1)(element_ptr);
81 int (*is0)(element_ptr);
82 int (*sign)(element_ptr); // satisfies sign(x) = -sign(-x)
83 int (*cmp)(element_ptr, element_ptr);
84 int (*to_bytes)(unsigned char *data, element_ptr);
85 int (*from_bytes)(element_ptr, unsigned char *data);
86 int (*length_in_bytes)(element_ptr);
87 int fixed_length_in_bytes; // length of an element in bytes; -1 for variable
88 int (*snprint)(char *s, size_t n, element_ptr e);
89 void (*to_mpz)(mpz_ptr, element_ptr);
90 void (*out_info)(FILE *, struct field_s *);
91 void (*pp_init)(element_pp_t p, element_t in);
92 void (*pp_clear)(element_pp_t p);
93 void (*pp_pow)(element_t out, mpz_ptr power, element_pp_t p);
94
95 struct pairing_s *pairing;
96
97 mpz_t order; // 0 for infinite order
98 element_ptr nqr; // nonquadratic residue
99
100 char *name;
101 void *data;
102 };
103 typedef struct field_s *field_ptr;
104 typedef struct field_s field_t[1];
105
106 typedef void (*fieldmap) (element_t dst, element_t src);
107
108 void field_out_info(FILE* out, field_ptr f);
109
110 /*@manual internal
111 Initialize 'e' to be an element of the algebraic structure 'f'
112 and set it to be the zero element.
113 */
element_init(element_t e,field_ptr f)114 static inline void element_init(element_t e, field_ptr f) {
115 e->field = f;
116 f->init(e);
117 }
118
119 element_ptr element_new(field_ptr f);
120 void element_free(element_ptr e);
121
122 /*@manual einit
123 Initialize 'e' to be an element of the algebraic structure that 'e2'
124 lies in.
125 */
element_init_same_as(element_t e,element_t e2)126 static inline void element_init_same_as(element_t e, element_t e2) {
127 element_init(e, e2->field);
128 }
129
130 /*@manual einit
131 Free the space occupied by 'e'. Call this when
132 the variable 'e' is no longer needed.
133 */
element_clear(element_t e)134 static inline void element_clear(element_t e) {
135 e->field->clear(e);
136 }
137
138 /*@manual eio
139 Output 'e' on 'stream' in base 'base'. The base must be between
140 2 and 36.
141 */
element_out_str(FILE * stream,int base,element_t e)142 static inline size_t element_out_str(FILE * stream, int base, element_t e) {
143 return e->field->out_str(stream, base, e);
144 }
145
146 /*@manual eio
147 */
148 int element_printf(const char *format, ...);
149
150 /*@manual eio
151 */
152 int element_fprintf(FILE * stream, const char *format, ...);
153
154 /*@manual eio
155 */
156 int element_snprintf(char *buf, size_t size, const char *fmt, ...);
157
158 /*@manual eio
159 Same as printf family
160 except also has the 'B' conversion specifier for types
161 of *element_t*, and 'Y', 'Z' conversion specifiers for
162 +mpz_t+. For example if 'e' is of type
163 +element_t+ then
164
165 element_printf("%B\n", e);
166
167 will print the value of 'e' in a human-readable form on standard output.
168 */
169 int element_vsnprintf(char *buf, size_t size, const char *fmt, va_list ap);
170
171 /*@manual eio
172 Convert an element to a human-friendly string.
173 Behaves as *snprintf* but only on one element at a time.
174 */
element_snprint(char * s,size_t n,element_t e)175 static inline int element_snprint(char *s, size_t n, element_t e) {
176 return e->field->snprint(s, n, e);
177 }
178
element_set_multiz(element_t e,multiz m)179 static inline void element_set_multiz(element_t e, multiz m) {
180 e->field->set_multiz(e, m);
181 }
182
183 /*@manual eio
184 Set the element 'e' from 's', a null-terminated C string in base 'base'.
185 Whitespace is ignored. Points have the form "['x,y']" or "'O'",
186 while polynomials have the form "['a0,...,an']".
187 Returns number of characters read (unlike GMP's mpz_set_str).
188 A return code of zero means PBC could not find a well-formed string
189 describing an element.
190 */
element_set_str(element_t e,const char * s,int base)191 static inline int element_set_str(element_t e, const char *s, int base) {
192 return e->field->set_str(e, s, base);
193 }
194
195 /*@manual eassign
196 Set 'e' to zero.
197 */
element_set0(element_t e)198 static inline void element_set0(element_t e) {
199 e->field->set0(e);
200 }
201
202 /*@manual eassign
203 Set 'e' to one.
204 */
element_set1(element_t e)205 static inline void element_set1(element_t e) {
206 e->field->set1(e);
207 }
208
209 /*@manual eassign
210 Set 'e' to 'i'.
211 */
element_set_si(element_t e,signed long int i)212 static inline void element_set_si(element_t e, signed long int i) {
213 e->field->set_si(e, i);
214 }
215
216 /*@manual eassign
217 Set 'e' to 'z'.
218 */
element_set_mpz(element_t e,mpz_t z)219 static inline void element_set_mpz(element_t e, mpz_t z) {
220 e->field->set_mpz(e, z);
221 }
222
223 /*@manual eassign
224 Set 'e' to 'a'.
225 */
element_set(element_t e,element_t a)226 static inline void element_set(element_t e, element_t a) {
227 PBC_ASSERT_MATCH2(e, a);
228 e->field->set(e, a);
229 }
230
element_add_ui(element_t n,element_t a,unsigned long int b)231 static inline void element_add_ui(element_t n, element_t a,
232 unsigned long int b) {
233 n->field->add_ui(n, a, b);
234 }
235
236 /*@manual econvert
237 Converts 'e' to a GMP integer 'z'
238 if such an operation makes sense
239 */
element_to_mpz(mpz_t z,element_t e)240 static inline void element_to_mpz(mpz_t z, element_t e) {
241 e->field->to_mpz(z, e);
242 }
243
element_to_si(element_t e)244 static inline long element_to_si(element_t e) {
245 mpz_t z;
246 mpz_init(z);
247 e->field->to_mpz(z, e);
248 long res = mpz_get_si(z);
249 mpz_clear(z);
250 return res;
251 }
252
253 /*@manual econvert
254 Generate an element 'e' deterministically from
255 the 'len' bytes stored in the buffer 'data'.
256 */
element_from_hash(element_t e,void * data,int len)257 static inline void element_from_hash(element_t e, void *data, int len) {
258 e->field->from_hash(e, data, len);
259 }
260
261 /*@manual earith
262 Set 'n' to 'a' + 'b'.
263 */
element_add(element_t n,element_t a,element_t b)264 static inline void element_add(element_t n, element_t a, element_t b) {
265 PBC_ASSERT_MATCH3(n, a, b);
266 n->field->add(n, a, b);
267 }
268
269 /*@manual earith
270 Set 'n' to 'a' - 'b'.
271 */
element_sub(element_t n,element_t a,element_t b)272 static inline void element_sub(element_t n, element_t a, element_t b) {
273 PBC_ASSERT_MATCH3(n, a, b);
274 n->field->sub(n, a, b);
275 }
276
277 /*@manual earith
278 Set 'n' = 'a' 'b'.
279 */
element_mul(element_t n,element_t a,element_t b)280 static inline void element_mul(element_t n, element_t a, element_t b) {
281 PBC_ASSERT_MATCH3(n, a, b);
282 n->field->mul(n, a, b);
283 }
284
element_cubic(element_t n,element_t a)285 static inline void element_cubic(element_t n, element_t a) {
286 PBC_ASSERT_MATCH2(n, a);
287 n->field->cubic(n, a);
288 }
289
290 /*@manual earith
291 */
element_mul_mpz(element_t n,element_t a,mpz_t z)292 static inline void element_mul_mpz(element_t n, element_t a, mpz_t z) {
293 PBC_ASSERT_MATCH2(n, a);
294 n->field->mul_mpz(n, a, z);
295 }
296
297 /*@manual earith
298 Set 'n' = 'a' 'z', that is 'a' + 'a' + ... + 'a' where there are 'z' 'a'#'s#.
299 */
element_mul_si(element_t n,element_t a,signed long int z)300 static inline void element_mul_si(element_t n, element_t a,
301 signed long int z) {
302 PBC_ASSERT_MATCH2(n, a);
303 n->field->mul_si(n, a, z);
304 }
305
306 /*@manual earith
307 'z' must be an element of a integer mod ring (i.e. *Z*~n~ for some n).
308 Set 'c' = 'a' 'z', that is 'a' + 'a' + ... + 'a'
309 where there are 'z' 'a''s.
310 */
element_mul_zn(element_t c,element_t a,element_t z)311 static inline void element_mul_zn(element_t c, element_t a, element_t z) {
312 mpz_t z0;
313 PBC_ASSERT_MATCH2(c, a);
314 //TODO: check z->field is Zn
315 mpz_init(z0);
316 element_to_mpz(z0, z);
317 element_mul_mpz(c, a, z0);
318 mpz_clear(z0);
319 }
320
321 /*@manual earith
322 Set 'n' = 'a' / 'b'.
323 */
element_div(element_t n,element_t a,element_t b)324 static inline void element_div(element_t n, element_t a, element_t b) {
325 PBC_ASSERT_MATCH3(n, a, b);
326 n->field->div(n, a, b);
327 }
328
329 /*@manual earith
330 Set 'n' = 'a' + 'a'.
331 */
element_double(element_t n,element_t a)332 static inline void element_double(element_t n, element_t a) {
333 PBC_ASSERT_MATCH2(n, a);
334 n->field->doub(n, a);
335 }
336
337 // Set n_i = a_i + a_i for all i at one time.
338 // Uses multi_doub(), which only elliptic curves have at the moment.
339 void element_multi_double(element_t n[], element_t a[], int m);
340
341 // Set n_i =a_i + b_i for all i at one time.
342 // Uses multi_add(), which only elliptic curves have at the moment.
343 void element_multi_add(element_t n[], element_t a[],element_t b[], int m);
344
345 /*@manual earith
346 Set 'n' = 'a/2'
347 */
element_halve(element_t n,element_t a)348 static inline void element_halve(element_t n, element_t a) {
349 PBC_ASSERT_MATCH2(n, a);
350 n->field->halve(n, a);
351 }
352
353 /*@manual earith
354 Set 'n' = 'a'^2^
355 */
element_square(element_t n,element_t a)356 static inline void element_square(element_t n, element_t a) {
357 PBC_ASSERT_MATCH2(n, a);
358 n->field->square(n, a);
359 }
360
361 /*@manual epow
362 Set 'x' = 'a'^'n'^, that is
363 'a' times 'a' times ... times 'a' where there are 'n' 'a'#'s#.
364 */
element_pow_mpz(element_t x,element_t a,mpz_t n)365 static inline void element_pow_mpz(element_t x, element_t a, mpz_t n) {
366 PBC_ASSERT_MATCH2(x, a);
367 x->field->pow_mpz(x, a, n);
368 }
369
370 /*@manual epow
371 Set 'x' = 'a'^'n'^, where 'n' is an element of a ring *Z*~N~
372 for some 'N' (typically the order of the algebraic structure 'x' lies in).
373 */
element_pow_zn(element_t x,element_t a,element_t n)374 static inline void element_pow_zn(element_t x, element_t a, element_t n) {
375 mpz_t z;
376 PBC_ASSERT_MATCH2(x, a);
377 mpz_init(z);
378 element_to_mpz(z, n);
379 element_pow_mpz(x, a, z);
380 mpz_clear(z);
381 }
382
383 /*@manual earith
384 Set 'n' = -'a'.
385 */
element_neg(element_t n,element_t a)386 static inline void element_neg(element_t n, element_t a) {
387 PBC_ASSERT_MATCH2(n, a);
388 n->field->neg(n, a);
389 }
390
391 /*@manual earith
392 Set 'n' to the inverse of 'a'.
393 */
element_invert(element_t n,element_t a)394 static inline void element_invert(element_t n, element_t a) {
395 PBC_ASSERT_MATCH2(n, a);
396 n->field->invert(n, a);
397 }
398
399 /*@manual erandom
400 If the 'e' lies in a finite algebraic structure,
401 assigns a uniformly random element to 'e'.
402 */
element_random(element_t e)403 static inline void element_random(element_t e) {
404 e->field->random(e);
405 }
406
407 /*@manual ecmp
408 Returns true if 'n' is 1.
409 */
element_is1(element_t n)410 static inline int element_is1(element_t n) {
411 return n->field->is1(n);
412 }
413
414 /*@manual ecmp
415 Returns true if 'n' is 0.
416 */
element_is0(element_t n)417 static inline int element_is0(element_t n) {
418 return n->field->is0(n);
419 }
420
421 /*@manual ecmp
422 Returns 0 if 'a' and 'b' are the same, nonzero otherwise.
423 */
element_cmp(element_t a,element_t b)424 static inline int element_cmp(element_t a, element_t b) {
425 PBC_ASSERT_MATCH2(a, b);
426 return a->field->cmp(a, b);
427 }
428
429 /*@manual ecmp
430 Returns nonzero if 'a' is a perfect square (quadratic residue),
431 zero otherwise.
432 */
element_is_sqr(element_t a)433 static inline int element_is_sqr(element_t a) {
434 return a->field->is_sqr(a);
435 }
436
437 /*@manual ecmp
438 */
element_sgn(element_t a)439 static inline int element_sgn(element_t a) {
440 return a->field->sign(a);
441 }
442
443 /*@manual ecmp
444 If 'a' is zero, returns 0. For nozero 'a' the behaviour depends on
445 the algebraic structure, but has the property that
446 element_sgn('a') = -element_sgn(-'a')
447 and
448 element_sgn('a') = 0 implies 'a' = 0 with overwhelming probability.
449 */
element_sign(element_t a)450 static inline int element_sign(element_t a) {
451 return a->field->sign(a);
452 }
453
element_sqrt(element_t a,element_t b)454 static inline void element_sqrt(element_t a, element_t b) {
455 PBC_ASSERT_MATCH2(a, b);
456 a->field->sqrt(a, b);
457 }
458
459 /*@manual etrade
460 Returns the length in bytes the element 'e' will take to represent
461 */
element_length_in_bytes(element_t e)462 static inline int element_length_in_bytes(element_t e) {
463 if (e->field->fixed_length_in_bytes < 0) {
464 return e->field->length_in_bytes(e);
465 } else {
466 return e->field->fixed_length_in_bytes;
467 }
468 }
469
470 /*@manual etrade
471 Converts 'e' to byte, writing the result in the buffer 'data'.
472 The number of bytes it will write can be determined from calling
473 *element_length_in_bytes()*. Returns number of bytes written.
474 */
element_to_bytes(unsigned char * data,element_t e)475 static inline int element_to_bytes(unsigned char *data, element_t e) {
476 return e->field->to_bytes(data, e);
477 }
478
479 /*@manual etrade
480 Reads 'e' from the buffer 'data', and returns the number of bytes read.
481 */
element_from_bytes(element_t e,unsigned char * data)482 static inline int element_from_bytes(element_t e, unsigned char *data) {
483 return e->field->from_bytes(e, data);
484 }
485
486 /*@manual epow
487 Sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^, and is generally faster than
488 performing two separate exponentiations.
489 */
490 void element_pow2_mpz(element_t x, element_t a1, mpz_t n1, element_t a2,
491 mpz_t n2);
492 /*@manual epow
493 Also sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^,
494 but 'n1', 'n2' must be elements of a ring *Z*~n~ for some integer n.
495 */
element_pow2_zn(element_t x,element_t a1,element_t n1,element_t a2,element_t n2)496 static inline void element_pow2_zn(element_t x, element_t a1, element_t n1,
497 element_t a2, element_t n2) {
498 mpz_t z1, z2;
499 mpz_init(z1);
500 mpz_init(z2);
501 element_to_mpz(z1, n1);
502 element_to_mpz(z2, n2);
503 element_pow2_mpz(x, a1, z1, a2, z2);
504 mpz_clear(z1);
505 mpz_clear(z2);
506 }
507
508 /*@manual epow
509 Sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^ 'a3'^'n3'^,
510 generally faster than performing three separate exponentiations.
511 */
512 void element_pow3_mpz(element_t x, element_t a1, mpz_t n1,
513 element_t a2, mpz_t n2, element_t a3, mpz_t n3);
514
515 /*@manual epow
516 Also sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^ 'a3'^'n3'^,
517 but 'n1', 'n2', 'n3' must be elements of a ring *Z*~n~ for some integer n.
518 */
element_pow3_zn(element_t x,element_t a1,element_t n1,element_t a2,element_t n2,element_t a3,element_t n3)519 static inline void element_pow3_zn(element_t x, element_t a1, element_t n1,
520 element_t a2, element_t n2,
521 element_t a3, element_t n3) {
522 mpz_t z1, z2, z3;
523 mpz_init(z1);
524 mpz_init(z2);
525 mpz_init(z3);
526 element_to_mpz(z1, n1);
527 element_to_mpz(z2, n2);
528 element_to_mpz(z3, n3);
529 element_pow3_mpz(x, a1, z1, a2, z2, a3, z3);
530 mpz_clear(z1);
531 mpz_clear(z2);
532 mpz_clear(z3);
533 }
534
535 void field_clear(field_ptr f);
536
537 element_ptr field_get_nqr(field_ptr f);
538 void field_set_nqr(field_ptr f, element_t nqr);
539 void field_gen_nqr(field_ptr f);
540
541 void field_init(field_ptr f);
542
mpz_is0(mpz_t z)543 static inline int mpz_is0(mpz_t z) {
544 return !mpz_sgn(z);
545 //return !mpz_cmp_ui(z, 0);
546 }
547
548 /*@manual etrade
549 Assumes 'e' is a point on an elliptic curve.
550 Writes the x-coordinate of 'e' to the buffer 'data'
551 */
552 int element_to_bytes_x_only(unsigned char *data, element_t e);
553 /*@manual etrade
554 Assumes 'e' is a point on an elliptic curve.
555 Sets 'e' to a point with
556 x-coordinate represented by the buffer 'data'. This is not unique.
557 For each 'x'-coordinate, there exist two different points, at least
558 for the elliptic curves in PBC. (They are inverses of each other.)
559 */
560 int element_from_bytes_x_only(element_t e, unsigned char *data);
561 /*@manual etrade
562 Assumes 'e' is a point on an elliptic curve.
563 Returns the length in bytes needed to hold the x-coordinate of 'e'.
564 */
565 int element_length_in_bytes_x_only(element_t e);
566
567 /*@manual etrade
568 If possible, outputs a compressed form of the element 'e' to
569 the buffer of bytes 'data'.
570 Currently only implemented for points on an elliptic curve.
571 */
572 int element_to_bytes_compressed(unsigned char *data, element_t e);
573
574 /*@manual etrade
575 Sets element 'e' to the element in compressed form in the buffer of bytes
576 'data'.
577 Currently only implemented for points on an elliptic curve.
578 */
579 int element_from_bytes_compressed(element_t e, unsigned char *data);
580
581 /*@manual etrade
582 Returns the number of bytes needed to hold 'e' in compressed form.
583 Currently only implemented for points on an elliptic curve.
584 */
585 int element_length_in_bytes_compressed(element_t e);
586
587 /*@manual epow
588 Prepare to exponentiate an element 'in', and store preprocessing information
589 in 'p'.
590 */
element_pp_init(element_pp_t p,element_t in)591 static inline void element_pp_init(element_pp_t p, element_t in) {
592 p->field = in->field;
593 in->field->pp_init(p, in);
594 }
595
596 /*@manual epow
597 Clear 'p'. Should be called after 'p' is no longer needed.
598 */
element_pp_clear(element_pp_t p)599 static inline void element_pp_clear(element_pp_t p) {
600 p->field->pp_clear(p);
601 }
602
603 /*@manual epow
604 Raise 'in' to 'power' and store the result in 'out', where 'in'
605 is a previously preprocessed element, that is, the second argument
606 passed to a previous *element_pp_init* call.
607 */
element_pp_pow(element_t out,mpz_ptr power,element_pp_t p)608 static inline void element_pp_pow(element_t out, mpz_ptr power,
609 element_pp_t p) {
610 p->field->pp_pow(out, power, p);
611 }
612
613 /*@manual epow
614 Same except 'power' is an element of *Z*~n~ for some integer n.
615 */
element_pp_pow_zn(element_t out,element_t power,element_pp_t p)616 static inline void element_pp_pow_zn(element_t out, element_t power,
617 element_pp_t p) {
618 mpz_t z;
619 mpz_init(z);
620 element_to_mpz(z, power);
621 element_pp_pow(out, z, p);
622 mpz_clear(z);
623 }
624
625 void pbc_mpz_out_raw_n(unsigned char *data, int n, mpz_t z);
626 void pbc_mpz_from_hash(mpz_t z, mpz_t limit,
627 unsigned char *data, unsigned int len);
628
629 /*@manual etrade
630 For points, returns the number of coordinates.
631 For polynomials, returns the number of coefficients.
632 Otherwise returns zero.
633 */
element_item_count(element_t e)634 static inline int element_item_count(element_t e) {
635 return e->field->item_count(e);
636 }
637
638 /*@manual etrade
639 For points, returns 'n'#th# coordinate.
640 For polynomials, returns coefficient of 'x^n^'.
641 Otherwise returns NULL.
642 The element the return value points to may be modified.
643 */
element_item(element_t e,int i)644 static inline element_ptr element_item(element_t e, int i) {
645 // TODO: Document the following:
646 // For polynomials, never zero the leading coefficient, e.g. never write:
647 // element_set0(element_item(f, poly_degree(f)));
648 // Use poly_set_coeff0() to zero the leading coefficient.
649 return e->field->item(e, i);
650 }
651
652 // Returns the field containing the items.
653 // Returns NULL if there are no items.
element_item_field(element_t e)654 static inline field_ptr element_item_field(element_t e) {
655 if (!element_item_count(e)) return NULL;
656 return element_item(e, 0)->field;
657 }
658
659 /*@manual etrade
660 Equivalent to `element_item(a, 0)`.
661 */
element_x(element_ptr a)662 static inline element_ptr element_x(element_ptr a) {
663 return a->field->get_x(a);
664 }
665 /*@manual etrade
666 Equivalent to `element_item(a, 1)`.
667 */
element_y(element_ptr a)668 static inline element_ptr element_y(element_ptr a) {
669 return a->field->get_y(a);
670 }
671
672 /*@manual epow
673 Computes 'x' such that 'g^x^ = h' by brute force, where
674 'x' lies in a field where `element_set_mpz()` makes sense.
675 */
676 void element_dlog_brute_force(element_t x, element_t g, element_t h);
677
678 /*@manual epow
679 Computes 'x' such that 'g^x^ = h' using Pollard rho method, where
680 'x' lies in a field where `element_set_mpz()` makes sense.
681 */
682 void element_dlog_pollard_rho(element_t x, element_t g, element_t h);
683
684 // Trial division up to a given limit. If limit == NULL, then there is no limit.
685 // Call the callback for each factor found, abort and return 1 if the callback
686 // returns nonzero, otherwise return 0.
687 int pbc_trial_divide(int (*fun)(mpz_t factor,
688 unsigned int multiplicity,
689 void *scope_ptr),
690 void *scope_ptr,
691 mpz_t n,
692 mpz_ptr limit);
693
694 #endif // __PBC_FIELD_H__
695