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 105e0438918d8ec95820aeb32d5d81ae26b572c7..6f80254ee75bfdf6fb83ad68a94d86def1d2ae58 100644 (file)
--- 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 00b728d147d040ce0917e53e6e67a74ef6b66aa9..983e1930840915f67cff5cde0b31792092f7c453 100644 (file)
--- 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 }