changeset 1464:47f4c80e1acd

cfield: Added C implementation of GF.
author Marcel Keller <mkeller@cs.au.dk>
date Wed, 11 Aug 2010 18:30:38 +0200
parents fd134edef387
children 2f0eeba34609
files setup.py viff/boost.py viff/cfield.c
diffstat 3 files changed, 615 insertions(+), 3 deletions(-) [+]
line wrap: on
line diff
--- a/setup.py	Mon Aug 02 17:17:34 2010 +0200
+++ b/setup.py	Wed Aug 11 18:30:38 2010 +0200
@@ -53,7 +53,8 @@
 cdefer = Extension('viff.cdefer',
                    sources = ['viff/cdefer.c'])
 cfield = Extension('viff.cfield',
-                   sources = ['viff/cfield.c'])
+                   sources = ['viff/cfield.c'],
+                   libraries = ['gmp'])
 
 setup(name='viff',
       version=viff.__version__,
--- a/viff/boost.py	Mon Aug 02 17:17:34 2010 +0200
+++ b/viff/boost.py	Wed Aug 11 18:30:38 2010 +0200
@@ -115,7 +115,8 @@
     import viff.field
     viff.field.FieldElement = viff.cfield.FieldElement
     viff.field.GF256 = viff.cfield.GF256
-    viff.field._field_cache[256] = viff.cfield.GF256
+    viff.field.GF = viff.cfield.GF
+    viff.field._field_cache = viff.cfield._field_cache
 
     if with_viff_reactor:
         import viff.reactor
--- a/viff/cfield.c	Mon Aug 02 17:17:34 2010 +0200
+++ b/viff/cfield.c	Wed Aug 11 18:30:38 2010 +0200
@@ -21,6 +21,9 @@
 #include <Python.h>
 #include <structmember.h>
 
+#include <gmp.h>
+#include <longintrepr.h>
+
 // dummy type FieldElement
 static PyTypeObject cfield_FieldElementType = {
     PyObject_HEAD_INIT(NULL)
@@ -411,6 +414,605 @@
     0,                          /*tp_weaklist*/
 };
 
+
+// Code stolen from gmpy.
+static void cfield_long2mpz(PyObject* obj, mpz_t z) {
+    mpz_t digit;
+    int len, i, negative;
+    PyLongObject *l = (PyLongObject *) obj;
+
+    assert(PyLong_Check(obj));
+
+    mpz_init_set_si(z, 0);
+    mpz_init(digit);
+
+    if(l->ob_size < 0) {
+        len = - l->ob_size;
+        negative = 1;
+    } else {
+        len = l->ob_size;
+        negative = 0;
+    }
+    for(i=0; i<len; i++) {
+        mpz_set_ui(digit, l->ob_digit[i]);
+        mpz_mul_2exp(digit, digit, i * SHIFT);
+        mpz_ior(z, z, digit);
+    }
+    if(negative)
+        mpz_neg(z, z);
+    mpz_clear(digit);
+}
+
+static PyObject* cfield_mpz2long(mpz_t z) {
+    int negative;
+    int size;
+    int i;
+    PyLongObject *newob;
+    mpz_t temp;
+
+    /* Assume gmp uses limbs as least as large as the builtin longs do */
+    assert(mp_bits_per_limb >= SHIFT);
+
+    mpz_init(temp);
+    if(mpz_sgn(z) < 0) {
+        negative = 1;
+        mpz_neg(temp, z);
+    } else {
+        negative = 0;
+        mpz_set(temp, z);
+    }
+
+    size = (mpz_sizeinbase(temp, 2) + SHIFT - 1) / SHIFT;
+
+    if(!(newob = _PyLong_New(size))) {
+        mpz_clear(temp);
+        return NULL;
+    }
+    for(i=0; i<size; i++) {
+        newob->ob_digit[i] = (unsigned short)(mpz_get_ui(temp) & MASK);
+        mpz_fdiv_q_2exp(temp, temp, SHIFT);
+    }
+    assert(mpz_sgn(temp) == 0);
+    mpz_clear(temp);
+
+    /* long_normalize() is file-static so we must reimplement it */
+    /* longobjp = long_normalize(longobjp); */
+    i = size;
+    while ( (i>0) && (newob->ob_digit[i-1] == 0))
+        i--;
+    newob->ob_size = i;
+
+    if(negative)
+        newob->ob_size = - newob->ob_size;
+    return (PyObject *) newob;
+}
+
+// This breaks binary compatibility with Python versions that change
+// PyTypeObject.
+typedef struct {
+    PyTypeObject type;
+    mpz_t modulus;
+} cfield_GFType;
+
+typedef struct {
+    PyObject_HEAD
+    mpz_t value;
+} cfield_GFElement;
+
+static int cfield_py2mpz(PyObject* o, mpz_t z) {
+    if (PyInt_Check(o)) {
+	mpz_init_set_si(z, PyInt_AS_LONG(o));
+    } else if (PyLong_Check(o))
+	cfield_long2mpz(o, z);
+    else
+	return -1;
+
+    return 0;
+}
+
+static PyObject* cfield_GFElement_new(PyTypeObject* type, PyObject* args,
+				      PyObject* kwargs)
+{
+    cfield_GFElement* self;
+
+    if (PyTuple_GET_SIZE(args) != 1) {
+	PyErr_Format(PyExc_TypeError,
+		     "GFELement takes exactly one argument (%zd given)",
+		     PyTuple_GET_SIZE(args));
+	return NULL;
+    }
+
+    self = (cfield_GFElement*)type->tp_alloc(type, 0);
+
+    if(cfield_py2mpz(PyTuple_GET_ITEM(args, 0), self->value) < 0) {
+	PyErr_SetString(PyExc_TypeError,
+			"GFElement parameter must be a number.");
+	return NULL;
+    }
+
+    mpz_mod(self->value, self->value, ((cfield_GFType*)Py_TYPE(self))->modulus);
+    return (PyObject*)self;
+}
+
+static void cfield_GFElement_dealloc(PyObject* o) {
+    cfield_GFElement* self = (cfield_GFElement*)o;
+    mpz_clear(self->value);
+    Py_TYPE(o)->tp_free(o);
+}
+
+#define GF_ELEMENT_GET_VALUES(IN1, IN2, OUT1, OUT2, OP, TYPE)		\
+    mpz_t tmp1, tmp2;							\
+    if (Py_TYPE(IN1)->tp_as_number != NULL &&				\
+	Py_TYPE(IN1)->tp_as_number->nb_##OP == cfield_GFElement_##OP) { \
+	OUT1 = &((cfield_GFElement*)IN1)->value;			\
+	TYPE = Py_TYPE(IN1);						\
+	if (Py_TYPE(IN2)->tp_as_number != NULL &&			\
+	    Py_TYPE(IN2)->tp_as_number->nb_##OP == cfield_GFElement_##OP) { \
+	    OUT2 = &((cfield_GFElement*)IN2)->value;			\
+	    if (Py_TYPE(IN1) != Py_TYPE(IN2)) {				\
+		Py_INCREF(Py_NotImplemented);				\
+		return Py_NotImplemented;				\
+	    }								\
+	} else {							\
+	    OUT2 = &tmp2;						\
+	    if (cfield_py2mpz(IN2, *OUT2) < 0) {			\
+		Py_INCREF(Py_NotImplemented);				\
+		return Py_NotImplemented;				\
+	    }								\
+	}								\
+    } else {								\
+	OUT1 = &tmp1;							\
+	if (cfield_py2mpz(IN1, *OUT1) < 0) {				\
+	    Py_INCREF(Py_NotImplemented);				\
+	    return Py_NotImplemented;					\
+	}								\
+	OUT2 = &((cfield_GFElement*)IN2)->value;			\
+	TYPE = Py_TYPE(IN2);						\
+    }
+
+#define GF_ELEMENT_VALUE_FREE(OUT1, OUT2)	\
+    if (OUT1 == &tmp1)				\
+	mpz_clear(tmp1);			\
+    else if (OUT2 == &tmp2)			\
+	mpz_clear(tmp2);
+
+static PyObject* cfield_GFElement_add(PyObject* self, PyObject* other) {
+    mpz_t *a, *b;
+    cfield_GFElement* result;
+    PyTypeObject* type;
+    GF_ELEMENT_GET_VALUES(self, other, a, b, add, type);
+    result = PyObject_New(cfield_GFElement, type);
+    mpz_init(result->value);
+    mpz_add(result->value, *a, *b);
+    mpz_mod(result->value, result->value, ((cfield_GFType*)type)->modulus);
+    GF_ELEMENT_VALUE_FREE(a, b);
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GFElement_subtract(PyObject* self, PyObject* other) {
+    mpz_t *a, *b;
+    cfield_GFElement* result;
+    PyTypeObject* type;
+    GF_ELEMENT_GET_VALUES(self, other, a, b, subtract, type);
+    result = PyObject_New(cfield_GFElement, type);
+    mpz_init(result->value);
+    mpz_sub(result->value, *a, *b);
+    mpz_mod(result->value, result->value, ((cfield_GFType*)type)->modulus);
+    GF_ELEMENT_VALUE_FREE(a, b);
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GFElement_multiply(PyObject* self, PyObject* other) {
+    mpz_t *a, *b;
+    cfield_GFElement* result;
+    PyTypeObject* type;
+    GF_ELEMENT_GET_VALUES(self, other, a, b, multiply, type);
+    result = PyObject_New(cfield_GFElement, type);
+    mpz_init(result->value);
+    mpz_mul(result->value, *a, *b);
+    mpz_mod(result->value, result->value, ((cfield_GFType*)type)->modulus);
+    GF_ELEMENT_VALUE_FREE(a, b);
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GFElement_divide(PyObject* self, PyObject* other) {
+    mpz_t *a, *b;
+    cfield_GFElement* result;
+    PyTypeObject* type;
+    GF_ELEMENT_GET_VALUES(self, other, a, b, divide, type);
+    result = PyObject_New(cfield_GFElement, type);
+    mpz_init(result->value);
+
+    if(mpz_invert(result->value, *b, ((cfield_GFType*)type)->modulus) == 0) {
+	PyErr_SetString(PyExc_ZeroDivisionError,
+			"Cannot divide by zero.");
+	return NULL;
+    }
+
+    mpz_mul(result->value, *a, result->value);
+    mpz_mod(result->value, result->value, ((cfield_GFType*)type)->modulus);
+    GF_ELEMENT_VALUE_FREE(a, b);
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GFElement_inv(PyObject* self) {
+    cfield_GFElement* result = PyObject_New(cfield_GFElement, Py_TYPE(self));
+    mpz_init(result->value);
+
+    if(mpz_invert(result->value, ((cfield_GFElement*)self)->value,
+		  ((cfield_GFType*)Py_TYPE(self))->modulus) == 0) {
+	PyErr_SetString(PyExc_ZeroDivisionError,
+			"Cannot invert zero.");
+	return NULL;
+    }
+
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GFElement_pow(PyObject* self, PyObject* other,
+				      PyObject* modulus)
+{
+    cfield_GFElement* result;
+
+    if (modulus != Py_None) {
+	PyErr_SetString(PyExc_TypeError,
+			"Exponentiation with modulus not possible.");
+	return NULL;
+    }
+
+    result = PyObject_New(cfield_GFElement, Py_TYPE(self));
+
+    if (PyInt_Check(other)) {
+	if (PyInt_AS_LONG(other) < 0) {
+	    PyErr_SetString(PyExc_AssertionError,
+			    "Cannot take power to negative exponent.");
+	    return NULL;
+	}
+
+	mpz_init(result->value);
+	mpz_powm_ui(result->value, ((cfield_GFElement*)self)->value,
+		    PyInt_AS_LONG(other),
+		    ((cfield_GFType*)Py_TYPE(self))->modulus);
+    } else if (PyLong_Check(other)) {
+	cfield_long2mpz(other, result->value);
+	mpz_powm(result->value, ((cfield_GFElement*)self)->value,
+		 result->value, ((cfield_GFType*)Py_TYPE(self))->modulus);
+    } else {
+	PyErr_SetString(PyExc_TypeError, "Exponent must be integer.");
+	return NULL;	
+    }
+
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GFElement_xor(PyObject* self, PyObject* other) {
+    mpz_t *a, *b;
+    cfield_GFElement* result;
+    PyTypeObject* type;
+    GF_ELEMENT_GET_VALUES(self, other, a, b, xor, type);
+    result = PyObject_New(cfield_GFElement, type);
+    mpz_init(result->value);
+    mpz_xor(result->value, *a, *b);
+    GF_ELEMENT_VALUE_FREE(a, b);
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GFElement_neg(PyObject* self) {
+    cfield_GFElement* result = PyObject_New(cfield_GFElement, Py_TYPE(self));
+    mpz_init(result->value);
+    mpz_neg(result->value, ((cfield_GFElement*)self)->value);
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GFElement_int(PyObject* self) {
+    return cfield_mpz2long(((cfield_GFElement*)self)->value);
+}
+
+static int cfield_GFElement_nonzero(PyObject* self) {
+    int result = mpz_sgn(((cfield_GFElement*)self)->value);
+    return result * result;
+}
+
+static PyObject* cfield_GFElement_richcompare(PyObject* self, PyObject* other,
+					      int op)
+{
+    mpz_t *a, *b;
+    mpz_t tmp_a, tmp_b;
+    int c;
+    PyObject* result;
+
+    if (Py_TYPE(self)->tp_richcompare == cfield_GFElement_richcompare) {
+	a = &((cfield_GFElement*)self)->value;
+
+	if (Py_TYPE(other)->tp_richcompare == cfield_GFElement_richcompare) {
+	    b = &((cfield_GFElement*)other)->value;
+
+	    if (Py_TYPE(self) != Py_TYPE(other)) {
+		PyErr_SetString(PyExc_AssertionError,
+				"Cannot compare elements of different fields.");
+		return NULL;
+	    }
+	} else {
+	    b = &tmp_b;
+
+	    if (cfield_py2mpz(other, *b) < 0) {
+		Py_INCREF(Py_NotImplemented);
+		return Py_NotImplemented;
+	    }
+	}
+    } else {
+	a = &tmp_a;
+
+	if (cfield_py2mpz(self, *a) < 0) {
+	    Py_INCREF(Py_NotImplemented);
+	    return Py_NotImplemented;
+	}
+
+	b = &((cfield_GFElement*)other)->value;
+    }
+
+    c = mpz_cmp(*a, *b);
+
+    if (a == &tmp_a)
+	mpz_clear(*a);
+    else if (b == &tmp_b)
+	mpz_clear(*b);
+
+    // code from object.c
+    switch (op) {
+    case Py_LT: c = c <  0; break;
+    case Py_LE: c = c <= 0; break;
+    case Py_EQ: c = c == 0; break;
+    case Py_NE: c = c != 0; break;
+    case Py_GT: c = c >  0; break;
+    case Py_GE: c = c >= 0; break;
+    default:
+	Py_INCREF(Py_NotImplemented);
+	return Py_NotImplemented;
+    }
+
+    result = c ? Py_True : Py_False;
+    Py_INCREF(result);
+    return result;
+}
+
+static long cfield_GFElement_hash(PyObject* self) {
+    long result = mpz_get_si(((cfield_GFElement*)self)->value);
+    result += mpz_get_si(((cfield_GFType*)Py_TYPE(self))->modulus) * 1000003L;
+
+    if (result == -1)
+	return -2;
+    else
+	return result;
+}
+
+static PyObject* cfield_GFElement_repr(PyObject* self) {
+    char* str;
+    PyObject* result;
+    str = mpz_get_str(NULL, 10, ((cfield_GFElement*)self)->value);
+    result = PyString_FromFormat("{%s}", str);
+    free(str);
+    return result;
+}
+
+static PyObject* cfield_GFElement_value(PyObject* self, void* noarg) {
+    return cfield_mpz2long(((cfield_GFElement*)self)->value);
+}
+
+static PyObject* cfield_GFElement_sqrt(PyObject* self, PyObject* noarg) {
+    mpz_t* modulus = &((cfield_GFType*)Py_TYPE(self))->modulus;
+    char* str;
+    cfield_GFElement* result;
+
+    if (mpz_congruent_ui_p(*modulus, 3, 4) == 0) {
+	str = mpz_get_str(NULL, 10, *modulus);
+	PyErr_Format(PyExc_AssertionError, "Cannot compute square root "
+		     "with modulus %s.", str);
+	free(str);
+	return NULL;
+    }
+
+    result = PyObject_New(cfield_GFElement, Py_TYPE(self));
+    mpz_init(result->value);
+    mpz_add_ui(result->value, *modulus, 1);
+    mpz_divexact_ui(result->value, result->value, 4);
+    mpz_powm(result->value, ((cfield_GFElement*)self)->value,
+	     result->value, *modulus);
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GFElement_bit(PyObject* self, PyObject* index) {
+    if (!PyInt_Check(index)) {
+	PyErr_SetString(PyExc_TypeError, "Index must be an integer");
+	return NULL;
+    }
+
+    return PyInt_FromLong(mpz_tstbit(((cfield_GFElement*)self)->value,
+				     PyInt_AS_LONG(index)));
+}
+
+static PyObject* cfield_GFElement_signed(PyObject* self, PyObject* noarg) {
+    mpz_t* value = &((cfield_GFElement*)self)->value;
+    mpz_t* modulus = &((cfield_GFType*)Py_TYPE(self))->modulus;
+    mpz_t tmp;
+    PyObject* result;
+
+    mpz_init(tmp);
+    mpz_sub_ui(tmp, *modulus, 1);
+    mpz_divexact_ui(tmp, tmp, 2);
+
+    if (mpz_cmp(*value, tmp) > 0) {
+	mpz_sub(tmp, *value, *modulus);
+	result = cfield_mpz2long(tmp);
+    } else
+	result = cfield_GFElement_value(self, NULL);
+
+    mpz_clear(tmp);
+    return result;
+}
+
+static PyMethodDef cfield_GFElement_methods[] = {
+    {"sqrt", cfield_GFElement_sqrt, METH_NOARGS, 0},
+    {"bit", cfield_GFElement_bit, METH_O, 0},
+    {"signed", cfield_GFElement_signed, METH_NOARGS, 0},
+    {"unsigned", (PyCFunction)cfield_GFElement_value, METH_NOARGS, 0},
+    {0, 0, 0, 0}
+};
+
+static PyGetSetDef cfield_GFElement_getset[] = {
+    {"value", cfield_GFElement_value, 0, 0, 0},
+    {0, 0, 0, 0, 0}
+};
+
+static PyNumberMethods cfield_GFElement_as_number = {
+        cfield_GFElement_add,           /*nb_add*/
+        cfield_GFElement_subtract,      /*nb_subtract*/
+        cfield_GFElement_multiply,      /*nb_multiply*/
+        cfield_GFElement_divide,        /*nb_divide*/
+        0,                              /*nb_remainder*/
+        0,                              /*nb_divmod*/
+        cfield_GFElement_pow,           /*nb_power*/
+        cfield_GFElement_neg,           /*nb_negative*/
+        0,                              /*tp_positive*/
+        0,                              /*tp_absolute*/
+        cfield_GFElement_nonzero,       /*tp_nonzero*/
+        cfield_GFElement_inv,           /*nb_invert*/
+        0,                              /*nb_lshift*/
+        0,                              /*nb_rshift*/
+        0,                              /*nb_and*/
+	cfield_GFElement_xor,           /*nb_xor*/
+        0,                              /*nb_or*/
+        0,                              /*nb_coerce*/
+        cfield_GFElement_int,           /*nb_int*/
+        cfield_GFElement_int,           /*nb_long*/
+        0,                              /*nb_float*/
+        0,                              /*nb_oct*/
+        0,                              /*nb_hex*/
+        0,                              /* nb_inplace_add */
+        0,                              /* nb_inplace_subtract */
+        0,                              /* nb_inplace_multiply */
+        0,                              /* nb_inplace_divide */
+        0,                              /* nb_inplace_remainder */
+        0,                              /* nb_inplace_power */
+        0,                              /* nb_inplace_lshift */
+        0,                              /* nb_inplace_rshift */
+        0,                              /* nb_inplace_and */
+        0,                              /* nb_inplace_xor */
+        0,                              /* nb_inplace_or */
+        cfield_GFElement_divide,        /* nb_floor_divide */
+        cfield_GFElement_divide,        /* nb_true_divide */
+        0,                              /* nb_inplace_floor_divide */
+        0                               /* nb_inplace_true_divide */
+};
+
+static PyTypeObject cfield_GFTypeType = {
+    PyObject_HEAD_INIT(NULL)
+    0,                          /*ob_size*/
+    "cfield.GFType",            /*tp_name*/
+    sizeof(cfield_GFType),      /*tp_basicsize*/
+    0,                          /*tp_itemsize*/
+    0,                          /*tp_dealloc*/
+    0,                          /*tp_print*/
+    0,                          /*tp_getattr*/
+    0,                          /*tp_setattr*/
+    0,                          /*tp_compare*/
+    0,                          /*tp_repr*/
+    0,                          /*tp_as_number*/
+    0,                          /*tp_as_sequence*/
+    0,                          /*tp_as_mapping*/
+    0,                          /*tp_hash */
+    0,                          /*tp_call*/
+    0,                          /*tp_str*/
+    0,                          /*tp_getattro*/
+    0,                          /*tp_setattro*/
+    0,                          /*tp_as_buffer*/
+    Py_TPFLAGS_DEFAULT,         /*tp_flags*/
+    0,                          /*tp_doc*/
+    0,                          /*tp_traverse*/
+    0,                          /*tp_clear*/
+    0,                          /*tp_richcompare*/
+    0,                          /*tp_weaklistoffset*/
+    0,                          /*tp_iter*/
+    0,                          /*tp_iternext*/
+    0,                          /*tp_methods*/
+    0,                          /*tp_members*/
+    0,                          /*tp_getset*/
+    &PyType_Type,               /*tp_base*/
+    0,                          /*tp_dict*/
+    0,                          /*tp_descr_get*/
+    0,                          /*tp_descr_set*/
+    0,                          /*tp_dictoffset*/
+    0,                          /*tp_init*/
+    0,                          /*tp_alloc*/
+    PyType_GenericNew,          /*tp_new*/
+    0,                          /*tp_free*/
+    0,                          /*tp_is_gc*/
+    0,                          /*tp_bases*/
+    0,                          /*tp_mro*/
+    0,                          /*tp_cache*/
+    0,                          /*tp_subclasses*/
+    0,                          /*tp_weaklist*/
+};
+
+static PyObject* cfield_field_cache;
+
+static PyObject* cfield_GF(PyObject* self, PyObject* modulus) {
+    cfield_GFType* field;
+
+    if (PyDict_Contains(cfield_field_cache, modulus)) {
+	field = (cfield_GFType*)PyDict_GetItem(cfield_field_cache, modulus);
+	Py_INCREF(field);
+	return (PyObject*)field;
+    }
+
+    field = PyObject_New(cfield_GFType, &cfield_GFTypeType);
+
+    memset(&field->type.ob_size, 0, sizeof(PyTypeObject) - sizeof(PyObject));
+    field->type.tp_name = "cfield.GFElement";
+    field->type.tp_basicsize = sizeof(cfield_GFElement);
+    field->type.tp_dealloc = cfield_GFElement_dealloc;
+    field->type.tp_repr = cfield_GFElement_repr;
+    field->type.tp_as_number = &cfield_GFElement_as_number;
+    field->type.tp_hash = cfield_GFElement_hash;
+    field->type.tp_str = cfield_GFElement_repr;
+    field->type.tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
+	Py_TPFLAGS_CHECKTYPES;
+    field->type.tp_richcompare = cfield_GFElement_richcompare;
+    field->type.tp_base = &cfield_FieldElementType;
+    field->type.tp_methods = cfield_GFElement_methods;
+    field->type.tp_getset = cfield_GFElement_getset;
+    field->type.tp_new = cfield_GFElement_new;
+
+    // Have to change type for PyType_Ready() to make mro_internal() happy.
+    field->type.ob_type = &PyType_Type;
+    if (PyType_Ready(&field->type) < 0)
+	return NULL;
+    field->type.ob_type = &cfield_GFTypeType;
+
+    PyDict_SetItemString(field->type.tp_dict, "modulus", modulus);
+    PyDict_SetItemString(field->type.tp_dict, "field", (PyObject*)field);
+
+    cfield_py2mpz(modulus, field->modulus);
+
+    if (!field->modulus)
+	return NULL;
+
+    if (mpz_probab_prime_p(field->modulus, 25) == 0) {
+	PyErr_SetString(PyExc_ValueError, "Modulus must be prime.");
+	return NULL;
+    }
+
+    if (PyDict_SetItem(cfield_field_cache, modulus, (PyObject*)field) < 0)
+	return NULL;
+
+    return (PyObject*)field;
+}
+
+static PyMethodDef cfield_methods[] = {
+    {"GF", cfield_GF, METH_O, 0},
+    {0, 0, 0, 0}
+};
+
 PyMODINIT_FUNC initcfield(void) {
     PyObject* m;
     int i;
@@ -418,7 +1020,8 @@
     if (PyType_Ready(&cfield_GF256Type) < 0)
 	return;
 
-    m = Py_InitModule3("cfield", 0, "C implemementation of viff.field");
+    m = Py_InitModule3("cfield", cfield_methods,
+		       "C implemementation of viff.field");
 
     if (!m)
 	return;
@@ -440,4 +1043,11 @@
     }
 
     cfield_GF256_generate_tables();
+
+    PyType_Ready(&cfield_GFTypeType);
+
+    cfield_field_cache = PyDict_New();
+    PyDict_SetItem(cfield_field_cache, PyInt_FromLong(256),
+		   (PyObject*)&cfield_GF256Type);
+    PyModule_AddObject(m, "_field_cache", cfield_field_cache);
 }