X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb-python/blobdiff_plain/bf8910bde6a430a64868ef70319f94e94114c82c..05a8254234de3a315ed1ec33c26b56826678834d:/mp.c

diff --git a/mp.c b/mp.c
index 00b728d..705a65e 100644
--- a/mp.c
+++ b/mp.c
@@ -1,13 +1,11 @@
 /* -*-c-*-
  *
- * $Id$
- *
  * Multiprecision arithmetic
  *
  * (c) 2004 Straylight/Edgeware
  */
 
-/*----- Licensing notice --------------------------------------------------* 
+/*----- Licensing notice --------------------------------------------------*
  *
  * This file is part of the Python interface to Catacomb.
  *
@@ -15,12 +13,12 @@
  * it under the terms of the GNU General Public License as published by
  * the Free Software Foundation; either version 2 of the License, or
  * (at your option) any later version.
- * 
+ *
  * Catacomb/Python is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
- * 
+ *
  * You should have received a copy of the GNU General Public License
  * along with Catacomb/Python; if not, write to the Free Software Foundation,
  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
@@ -498,7 +496,7 @@ static PyObject *mp_pyfloat(PyObject *x)
   return (PyFloat_FromDouble(f));
 }
 
-#define COERCE(pre, PRE) 						\
+#define COERCE(pre, PRE)						\
   static int pre##_pycoerce(PyObject **x, PyObject **y)			\
   {									\
     mp *z;								\
@@ -557,8 +555,6 @@ static PyObject *mpmeth_jacobi(PyObject *me, PyObject *arg)
   PyObject *z = 0;
 
   if (!PyArg_ParseTuple(arg, "O&:jacobi", convmp, &y)) goto end;
-  if (MP_NEGP(MP_X(me)) || MP_EVENP(MP_X(me)))
-    VALERR("must be positive and odd");
   z = PyInt_FromLong(mp_jacobi(y, MP_X(me)));
 end:
   if (y) MP_DROP(y);
@@ -574,7 +570,7 @@ end:
   }
 BITOP(mp, setbit, 2c);
 BITOP(mp, clearbit, 2c);
-BITOP(gf, setbit, ); 
+BITOP(gf, setbit, );
 BITOP(gf, clearbit, );
 #undef BITOP
 
@@ -1193,7 +1189,7 @@ fail:
 
 static PyObject *mm_mexpr(PyObject *me, void *v, int n)
   { return mp_pywrap(mpmont_mexpr(MPMONT_PY(me), MP_NEW, v, n)); }
-  
+
 static void mp_mexp_drop(void *p)
 {
   mp_expfactor *f = p;
@@ -1233,7 +1229,7 @@ fail:
 
 static PyObject *mm_mexp(PyObject *me, void *v, int n)
   { return mp_pywrap(mpmont_mexp(MPMONT_PY(me), MP_NEW, v, n)); }
-  
+
 static PyObject *mmmeth_mexp(PyObject *me, PyObject *arg)
 {
   return mexp_common(me, arg, sizeof(mp_expfactor),
@@ -1386,7 +1382,7 @@ end:
 
 static PyObject *mb_mexp(PyObject *me, void *v, int n)
   { return mp_pywrap(mpbarrett_mexp(MPBARRETT_PY(me), MP_NEW, v, n)); }
-  
+
 static PyObject *mbmeth_mexp(PyObject *me, PyObject *arg)
 {
   return mexp_common(me, arg, sizeof(mp_expfactor),
@@ -1970,7 +1966,7 @@ static PyMethodDef gf_pymethods[] = {
   METH	(gcdx,
 	 "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
   METH	(modinv,	"X.modinv(Y) -> multiplicative inverse of Y mod X")
-  METH	(irreduciblep, 	"X.irreduciblep() -> true/false")
+  METH	(irreduciblep,	"X.irreduciblep() -> true/false")
 #undef METHNAME
 #define METHNAME(func) mpmeth_##func
   KWMETH(tostring,	"X.tostring(radix = 10) -> STR")
@@ -2141,6 +2137,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 +2238,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 }
@@ -2382,13 +2434,13 @@ and normal basis representations.",
 
 static PyMethodDef methods[] = {
 #define METHNAME(func) meth_##func
-  KWMETH(_MP_fromstring,        "\
+  KWMETH(_MP_fromstring,	"\
 fromstring(STR, radix = 0) -> (X, REST)\n\
 \n\
 Parse STR as a large integer, according to radix.  If radix is zero,\n\
 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
 or `R_' for other radix R.")
-  KWMETH(_GF_fromstring,        "\
+  KWMETH(_GF_fromstring,	"\
 fromstring(STR, radix = 0) -> (X, REST)\n\
 \n\
 Parse STR as a binary polynomial, according to radix.  If radix is zero,\n\