#include <Python.h>
#include <structmember.h>
#define BAD_MODULUS -1
#define BAD_DEGREE -1
#define ModPoly_Check(v) (PyObject_TypeCheck(v, &ModPolyType))
typedef struct {
PyObject_HEAD
/* Type specific fields */
Py_ssize_t ob_size;
PyObject **ob_item;
Py_ssize_t allocated;
PyObject *r_modulus;
PyObject *n_modulus;
PyObject *degree;
} ModPoly;
static PyTypeObject ModPolyType;
static PyObject *ModPoly_Equal(PyObject *, PyObject *);
static void
ModPoly_dealloc(ModPoly *self)
{
Py_XDECREF(self->r_modulus);
Py_XDECREF(self->n_modulus);
Py_XDECREF(self->degree);
if (self->ob_item != NULL) {
Py_ssize_t i;
for (i=0; i < self->ob_size; i++) {
Py_XDECREF(self->ob_item[i]);
}
free(self->ob_item);
}
self->ob_type->tp_free((PyObject *)self);
}
static PyObject *
ModPoly_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
ModPoly *self;
self = (ModPoly *)type->tp_alloc(type, 0);
if (self != NULL) {
self->r_modulus = PyInt_FromLong(BAD_MODULUS);
if (self->r_modulus == NULL) {
Py_DECREF(self);
return NULL;
}
self->n_modulus = PyInt_FromLong(BAD_MODULUS);
if (self->n_modulus == NULL) {
Py_DECREF(self);
return NULL;
}
self->degree = PyInt_FromLong(BAD_DEGREE);
if (self->degree == NULL) {
Py_DECREF(self);
return NULL;
}
self->ob_size = 0;
self->ob_item = NULL;
self->allocated = 0;
}
return (PyObject *)self;
}
static int
ModPoly_init(ModPoly *self, PyObject *args, PyObject *kwds)
{
PyObject *r_modulus=NULL, *n_modulus=NULL, *coefs=NULL, *tmp;
PyObject **tmp_ar;
static char *kwlist[] = {"r_modulus", "n_modulus", "coefficients", NULL};
if (!PyArg_ParseTupleAndKeywords(args, kwds, "OO|O", kwlist,
&r_modulus, &n_modulus, &coefs))
return -1;
if (r_modulus) {
if (!PyInt_Check(r_modulus) && PyLong_Check(r_modulus)) {
PyErr_SetString(PyExc_TypeError, "The r modulus must be an integer.");
return -1;
}
tmp = self->r_modulus;
Py_INCREF(r_modulus);
self->r_modulus = r_modulus;
Py_XDECREF(tmp);
}
if (n_modulus) {
if (!PyInt_Check(n_modulus) && PyLong_Check(n_modulus)) {
PyErr_SetString(PyExc_TypeError, "The n modulus must be an integer.");
Py_DECREF(self->r_modulus);
return -1;
}
tmp = self->n_modulus;
Py_INCREF(n_modulus);
self->n_modulus = n_modulus;
Py_XDECREF(tmp);
}
self->degree = PyInt_FromLong(1);
if (self->degree == NULL) {
Py_DECREF(self->r_modulus);
Py_DECREF(self->n_modulus);
return -1;
}
tmp_ar = (PyObject **)malloc(2 * sizeof(PyObject*));
if (tmp_ar == NULL) {
Py_DECREF(self->r_modulus);
Py_DECREF(self->n_modulus);
Py_DECREF(self->degree);
return -1;
}
tmp_ar[0] = PyInt_FromLong(0);
if (tmp_ar[0] != NULL) {
tmp_ar[1] = PyInt_FromLong(1);
}
if (tmp_ar[0] == NULL || tmp_ar[0] == NULL) {
Py_DECREF(self->r_modulus);
Py_DECREF(self->n_modulus);
Py_DECREF(self->degree);
Py_XDECREF(tmp_ar[0]);
Py_XDECREF(tmp_ar[1]);
free(tmp_ar);
return -1;
}
self->ob_size = 2;
self->allocated = 2;
return 0;
}
static PyObject *
ModPoly_compare(PyObject *a, PyObject *b, int op)
{
switch (op) {
case Py_EQ:
return ModPoly_Equal(a, b);
break;
case Py_NE: {
PyObject *res = ModPoly_Equal(a, b);
int r;
if (res == NULL)
return NULL;
r = PyObject_Not(res);
Py_DECREF(res);
if (r) {
Py_RETURN_TRUE;
} else {
Py_RETURN_FALSE;
}
break; }
default:
Py_INCREF(Py_NotImplemented);
return Py_NotImplemented;
break;
}
}
static PyObject *
ModPoly_Equal(PyObject *a, PyObject *b)
{
if (!ModPoly_Check(b)) {
Py_RETURN_FALSE;
}
ModPoly *A=(ModPoly *)a, *B=(ModPoly *)b;
if (!PyObject_RichCompareBool(A->r_modulus, B->r_modulus,Py_EQ)) {
Py_RETURN_FALSE;
} else if (!PyObject_RichCompareBool(A->n_modulus, B->n_modulus,Py_EQ)) {
Py_RETURN_FALSE;
}
Py_RETURN_TRUE;
}
static PyObject *
ModPoly_getcoefs(ModPoly *self, void *closure)
{
PyTupleObject *res=(PyTupleObject*)PyTuple_New(self->ob_size);
Py_ssize_t i;
PyObject *tmp;
if (res == NULL)
return NULL;
for (i=0; i < self->ob_size; i++) {
tmp = self->ob_item[i];
Py_INCREF(tmp);
PyTuple_SET_ITEM(res, i, tmp);
}
return (PyObject *)res;
}
static PyObject *
ModPoly_setcoefs(ModPoly *self, PyObject *value, void* closure)
{
PyErr_SetString(PyExc_AttributeError,
"Cannot set the coefficients of a polynomial.");
return NULL;
}
static PyMemberDef ModPoly_members[] = {
{"r_modulus", T_OBJECT_EX, offsetof(ModPoly, r_modulus), READONLY,
"The exponent of the polynomial modulus (x^r-1)."},
{"n_modulus", T_OBJECT_EX, offsetof(ModPoly, n_modulus), READONLY,
"The coefficient modulus."},
{"degree", T_OBJECT_EX, offsetof(ModPoly, degree), READONLY,
"The polynomial degree."},
{NULL}
};
static PyGetSetDef ModPoly_getsetters[] = {
{"coefficients",
(getter)ModPoly_getcoefs, (setter)ModPoly_setcoefs,
"The polynomial coefficients.", NULL},
{NULL, 0, 0, NULL, NULL}
};
static PyTypeObject ModPolyType = {
PyObject_HEAD_INIT(NULL)
0, /* ob_size */
"algebra.polynomials.ModPolynomial", /* tp_name */
sizeof(ModPoly), /* tp_basicsize */
0, /* tp_itemsize */
(destructor)ModPoly_dealloc, /* 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 | Py_TPFLAGS_BASETYPE, /* tp_flags */
"Represent a polynomial on (Z/nZ)[x]/x^r-1", /* tp_doc */
0, /* tp_traverse */
0, /* tp_clear */
(richcmpfunc)ModPoly_compare, /* tp_richcompare */
0, /* tp_weaklistoffset */
0, /* tp_iter */
0, /* tp_iternext */
0, /* tp_methods */
ModPoly_members, /* tp_members */
ModPoly_getsetters, /* tp_getset */
0, /* tp_base */
0, /* tp_dict */
0, /* tp_descr_get */
0, /* tp_descr_set */
0, /* tp_dictoffset */
(initproc)ModPoly_init, /* tp_init */
0, /* tp_alloc */
ModPoly_new, /* tp_new */
};
static PyMethodDef module_methods[] = {
{NULL, NULL, 0, NULL} /* Sentinel */
};
#ifndef PyMODINIT_FUNC
#define PyMODINIT_FUNC void
#endif
PyMODINIT_FUNC
init_modpoly(void)
{
PyObject *m;
ModPolyType.tp_new = PyType_GenericNew;
if (PyType_Ready(&ModPolyType) < 0)
return;
m = Py_InitModule3("_modpoly", module_methods,
"Representation of polynomials on (Z/nZ)[x]/x^r-1.");
if (m == NULL)
return;
Py_INCREF(&ModPolyType);
PyModule_AddObject(m, "ModPolynomial", (PyObject *)&ModPolyType);
}