Algebraic structures are represented in the `field_t`

data type, which mostly contains
pointers to functions written to perform operations such as
addition and multiplication in that particular group, ring or
field:

struct field_s { ... void (*init)(element_ptr); void (*clear)(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); ... }; typedef struct field_s *field_ptr; typedef struct field_s field_t[1];

The name `algebraic_structure_t`

is arguably more accurate, but far too cumbersome. It may help
if one views groups and rings as handicapped fields.

The last two lines of the above code excerpt show how GMP and PBC define data types: they are arrays of length one so that when a variable is declared, space is automatically allocated for it on the stack. Yet when used as a argument to a function, a pointer is passed, thus there is no need to explicitly allocate and deallocate memory, nor reference and dereference variables.

Each `element_t`

contains a field
named `field`

to such a `field_t`

variable. The only other field is
`data`

, which stores any data needed
for the implementation of the particular algebraic structure
the element resides in.

struct element_s { struct field_s *field; void *data; };

When an `element_t`

variable is
initialized, `field`

is set
appropriately, and then the initialization specific to that
field is called to complete the initialization. Here, a line of
code is worth a thousand words:

void element_init(element_t e, field_ptr f) { e->field = f; f->init(e); }

Thus during a call to one of the `element_`

functions, the `field`

pointer is followed then the appropriate
routine is executed. For example, modular addition results when
the input element is an element of a finite field, while
polynomial addition is performed for elements of a polynomial
ring and so on.

void element_add(element_t n, element_t a, element_t b) { n->field->add(n, a, b); }

My design may seem dangerous because if a programmer inadvertently attempts to add a polynomial and a point on an elliptic curve, say, the code will compile without warnings since they have the same data type.

However I settled on having a catch-all “glorified
`void *`

” `element_t`

because I wanted to

- extend a field an arbitrary number of times (though in practice, currently I only need to extend a field twice at most),
- switch fields easily, so for example a program that benchmarks addition in polynomial rings can be trivially modified to benchmark addition in a group, and
- interchange different implementations of the same algebraic structure, for example, compare Montgomery representation versus a naive implementation of integer modulo rings.

Additionally, defining `PBC_DEBUG`

catches many type mismatches.

In mathematics, groups, rings and fields should be distinguished, but for implmentation, it is simplest lump them together under the same heading. In any event, distinct data types may lead to a false sense of security. Fields of prime order with different moduli would still fall under the same data type, with unpleasant results if their elements are mistakenly mixed.

I have vague plans to add flags to `field_t`

describing the capabilities of a
particular `field_t`

. These flags
would be set during initialization, and would indicate for
example whether one can invert every nonzero element, whether
there are one or two operations (that is, group versus ring),
whether the field is an integer mod ring, polynomial ring, or
polynomial mod ring, and so on. Once in place, more runtime
checks can be performed to avoid illegal inversion and similar
problems.

Another option is to introduce data types for each of the four pairing-related algebraic structures, namely G1, G2, GT and Zr, as these are the only ones needed for implementing pairing-based cryptosystems.

An alternative was to simply use ```
void
*
```

instead of `element_t`

and
require the programmer to pass the field as a parameter, e.g.
`element_add(a, b, c, F_13)`

, but I
decided the added annoyance of having to type this extra
variable every time negated any benefits, such as obviating the
need for the `field`

pointer in
`struct element_s`

, even if one
ignores the more serious problem that runtime type checking is
considerably harder, if not impossible.

I suppose one could write a preprocessor to convert one type
of notation to the other, but I would like the code to be
standard C. (On the other hand, as Hovav Shacham suggested, it
may be nice to eventually have a converter that takes
human-friendly infix operator expressions like `a = (b + c) * d`

and outputs the assembly-like
`element_`

equivalents.)