From: Mark Wooding <mdw@distorted.org.uk>
Date: Wed, 5 Apr 2006 23:07:56 +0000 (+0100)
Subject: gf: New methods for various modular operations.
X-Git-Tag: 1.0.1~17
X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/catacomb-python/commitdiff_plain/fbc145f3a0f8cd119f7f9a9999eecbea0bb20dd4

gf: New methods for various modular operations.

Modular square root and quadratic solution, and trace and halftrace.
Implemented in C for GFReduce, with thin Python glue for GF objects.
---

diff --git a/catacomb/__init__.py b/catacomb/__init__.py
index 105e043..6f80254 100644
--- a/catacomb/__init__.py
+++ b/catacomb/__init__.py
@@ -117,7 +117,12 @@ class _tmp:
 _augment(MP, _tmp)
 
 class _tmp:
+  def zerop(x): return x == 0
   def reduce(x): return GFReduce(x)
+  def trace(x, y): return x.reduce().trace(y)
+  def halftrace(x, y): return x.reduce().halftrace(y)
+  def modsqrt(x, y): return x.reduce().sqrt(y)
+  def quadsolve(x, y): return x.reduce().quadsolve(y)
 _augment(GF, _tmp)
 
 class _tmp:
diff --git a/mp.c b/mp.c
index 00b728d..983e193 100644
--- a/mp.c
+++ b/mp.c
@@ -2141,6 +2141,58 @@ end:
   return (rc);
 }
 
+static PyObject *grmeth_trace(PyObject *me, PyObject *arg)
+{
+  PyObject *rc = 0;
+  mp *xx = 0;
+
+  if (!PyArg_ParseTuple(arg, "O&:trace", convgf, &xx)) goto end;
+  rc = PyInt_FromLong(gfreduce_trace(GFREDUCE_PY(me), xx));
+end:
+  if (xx) MP_DROP(xx);
+  return (rc);
+}
+
+static PyObject *grmeth_halftrace(PyObject *me, PyObject *arg)
+{
+  PyObject *rc = 0;
+  mp *xx = 0;
+
+  if (!PyArg_ParseTuple(arg, "O&:halftrace", convgf, &xx)) goto end;
+  rc = gf_pywrap(gfreduce_halftrace(GFREDUCE_PY(me), MP_NEW, xx));
+end:
+  if (xx) MP_DROP(xx);
+  return (rc);
+}
+
+static PyObject *grmeth_sqrt(PyObject *me, PyObject *arg)
+{
+  PyObject *rc = 0;
+  mp *xx = 0, *yy;
+
+  if (!PyArg_ParseTuple(arg, "O&:sqrt", convgf, &xx)) goto end;
+  if ((yy = gfreduce_sqrt(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
+    VALERR("no modular square root");
+  rc = gf_pywrap(yy);
+end:
+  if (xx) MP_DROP(xx);
+  return (rc);
+}
+
+static PyObject *grmeth_quadsolve(PyObject *me, PyObject *arg)
+{
+  PyObject *rc = 0;
+  mp *xx = 0, *yy;
+
+  if (!PyArg_ParseTuple(arg, "O&:quadsolve", convgf, &xx)) goto end;
+  if ((yy = gfreduce_quadsolve(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
+    VALERR("no solution found");
+  rc = gf_pywrap(yy);
+end:
+  if (xx) MP_DROP(xx);
+  return (rc);
+}
+
 static PyObject *grmeth_reduce(PyObject *me, PyObject *arg)
 {
   PyObject *z = 0;
@@ -2190,6 +2242,10 @@ static PyGetSetDef gfreduce_pygetset[] = {
 static PyMethodDef gfreduce_pymethods[] = {
 #define METHNAME(name) grmeth_##name
   METH	(reduce,	"R.reduce(X) -> X mod B.m")
+  METH	(trace,	       "R.trace(X) -> Tr(X) = x + x^2 + ... + x^{2^{m - 1}}")
+  METH	(halftrace,   "R.halftrace(X) -> x + x^{2^2} + ... + x^{2^{m - 1}}")
+  METH	(sqrt,		"R.sqrt(X) -> Y where Y^2 = X mod R")
+  METH	(quadsolve,	"R.quadsolve(X) -> Y where Y^2 + Y = X mod R")
   METH	(exp,		"R.exp(X, N) -> X^N mod B.m")
 #undef METHNAME
   { 0 }