chiark - git - mdw - catacomb-python/blob - mp.c

   1 /* -*-c-*-
   2  *
   3  * Multiprecision arithmetic
   4  *
   5  * (c) 2004 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of the Python interface to Catacomb.
  11  *
  12  * Catacomb/Python is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License as published by
  14  * the Free Software Foundation; either version 2 of the License, or
  15  * (at your option) any later version.
  16  *
  17  * Catacomb/Python is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with Catacomb/Python; if not, write to the Free Software Foundation,
  24  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25  */
  26
  27 /*----- Header files ------------------------------------------------------*/
  28
  29 #include "catacomb-python.h"
  30
  31 /*----- General utilities -------------------------------------------------*/
  32
  33 PyTypeObject *mp_pytype = 0;
  34 PyTypeObject *gf_pytype = 0;
  35
  36 mp *mp_frompylong(PyObject *obj)
  37 {
  38   unsigned long bits;
  39   PyLongObject *l = (PyLongObject *)obj;
  40   int sz;
  41   size_t w;
  42   mpd r = 0;
  43   int b = 0;
  44   int i;
  45   mp *x;
  46   mpw *p;
  47
  48   sz = l->ob_size;
  49   if (sz < 0) sz = -sz;
  50   assert(MPW_BITS >= SHIFT);
  51   bits = (unsigned long)sz * SHIFT;
  52   w = (bits + MPW_BITS - 1)/MPW_BITS;
  53   x = mp_new(w, l->ob_size < 0 ? MP_NEG : 0);
  54   p = x->v;
  55   for (i = 0; i < sz; i++) {
  56     r |= (mpd)l->ob_digit[i] << b;
  57     b += SHIFT;
  58     while (b >= MPW_BITS) {
  59       *p++ = MPW(r);
  60       r >>= MPW_BITS;
  61       b -= MPW_BITS;
  62     }
  63   }
  64   while (r) {
  65     *p++ = MPW(r);
  66     r >>= MPW_BITS;
  67   }
  68   x->vl = p;
  69   MP_SHRINK(x);
  70   return (x);
  71 }
  72
  73 PyObject *mp_topylong(mp *x)
  74 {
  75   unsigned long bits = mp_bits(x);
  76   int sz = (bits + SHIFT - 1)/SHIFT;
  77   PyLongObject *l = _PyLong_New(sz);
  78   mpd r = 0;
  79   int b = 0;
  80   mpw *p = x->v;
  81   int i = 0;
  82
  83   assert(MPW_BITS >= SHIFT);
  84   while (i < sz && p < x->vl) {
  85     r |= (mpd)*p++ << b;
  86     b += MPW_BITS;
  87     while (i < sz && b >= SHIFT) {
  88       l->ob_digit[i++] = r & MASK;
  89       r >>= SHIFT;
  90       b -= SHIFT;
  91     }
  92   }
  93   while (i < sz && r) {
  94     l->ob_digit[i++] = r & MASK;
  95     r >>= SHIFT;
  96   }
  97   l->ob_size = (x->f & MP_NEG) ? -sz : sz;
  98   return ((PyObject *)l);
  99 }
 100
 101 mp *mp_frompyobject(PyObject *o, int radix)
 102 {
 103   mp *x;
 104
 105   if (PyString_Check(o)) {
 106     mptext_stringctx sc;
 107     mp *x;
 108     sc.buf = PyString_AS_STRING(o);
 109     sc.lim = sc.buf + PyString_GET_SIZE(o);
 110     x = mp_read(MP_NEW, radix, &mptext_stringops, &sc);
 111     if (!x) return (0);
 112     if (sc.buf < sc.lim) { MP_DROP(x); return (0); }
 113     return (x);
 114   }
 115   if ((x = tomp(o)) != 0)
 116     return (x);
 117   return (0);
 118 }
 119
 120 PyObject *mp_topystring(mp *x, int radix, const char *xpre,
 121                         const char *pre, const char *post)
 122 {
 123   int len = mptext_len(x, radix) + 1;
 124   mptext_stringctx sc;
 125   PyObject *o;
 126   size_t xprelen = xpre ? strlen(xpre) : 0;
 127   size_t prelen = pre ? strlen(pre) : 0;
 128   size_t postlen = post ? strlen(post) : 0;
 129   char *p;
 130   MP_COPY(x);
 131   o = PyString_FromStringAndSize(0, len + 1 + xprelen + prelen + postlen);
 132   p = PyString_AS_STRING(o);
 133   sc.buf = p;
 134   if (xpre) { memcpy(sc.buf, xpre, xprelen); sc.buf += xprelen; }
 135   if (MP_NEGP(x)) { *sc.buf++ = '-'; x = mp_neg(x, x); }
 136   if (pre) { memcpy(sc.buf, pre, prelen); sc.buf += prelen; }
 137   sc.lim = sc.buf + len;
 138   mp_write(x, radix, &mptext_stringops, &sc);
 139   if (post) { memcpy(sc.buf, post, postlen); sc.buf += postlen; }
 140   MP_DROP(x);
 141   _PyString_Resize(&o, sc.buf - p);
 142   return (o);
 143 }
 144
 145 static int good_radix_p(int r, int readp)
 146 {
 147   return ((r >= -255 && r <= -2) ||
 148           (readp && r == 0) ||
 149           (r >= 2 && r <= 62));
 150 }
 151
 152 PyObject *mp_pywrap(mp *x)
 153 {
 154   mp_pyobj *z = PyObject_New(mp_pyobj, mp_pytype);
 155   z->x = x;
 156   return ((PyObject *)z);
 157 }
 158
 159 PyObject *gf_pywrap(mp *x)
 160 {
 161   mp_pyobj *z = PyObject_New(mp_pyobj, gf_pytype);
 162   z->x = x;
 163   return ((PyObject *)z);
 164 }
 165
 166 int mp_tolong_checked(mp *x, long *l, int must)
 167 {
 168   static mp *longmin = 0, *longmax = 0;
 169   int rc = -1;
 170
 171   if (!longmax) {
 172     longmin = mp_fromlong(MP_NEW, LONG_MIN);
 173     longmax = mp_fromlong(MP_NEW, LONG_MAX);
 174   }
 175   if (MP_CMP(x, <, longmin) || MP_CMP(x, >, longmax)) {
 176     if (must) VALERR("mp out of range for int");
 177     else goto end;
 178   }
 179   *l = mp_tolong(x);
 180   rc = 0;
 181 end:
 182   return (rc);
 183 }
 184
 185 /*----- Python interface --------------------------------------------------*/
 186
 187 static void mp_pydealloc(PyObject *o)
 188 {
 189   MP_DROP(MP_X(o));
 190   FREEOBJ(o);
 191 }
 192
 193 static PyObject *mp_pyrepr(PyObject *o)
 194   { return mp_topystring(MP_X(o), 10, "MP(", 0, "L)"); }
 195
 196 static PyObject *mp_pystr(PyObject *o)
 197   { return mp_topystring(MP_X(o), 10, 0, 0, 0); }
 198
 199 mp *tomp(PyObject *o)
 200 {
 201   PyObject *l;
 202   mp *x;
 203
 204   if (!o)
 205     return (0);
 206   else if (MP_PYCHECK(o) || GF_PYCHECK(o))
 207     return (MP_COPY(MP_X(o)));
 208   else if (FE_PYCHECK(o))
 209     return (F_OUT(FE_F(o), MP_NEW, FE_X(o)));
 210   else if (PFILT_PYCHECK(o))
 211     return (MP_COPY(PFILT_F(o)->m));
 212   else if (ECPT_PYCHECK(o)) {
 213     ec p = EC_INIT;
 214     getecptout(&p, o);
 215     x = MP_COPY(p.x);
 216     EC_DESTROY(&p);
 217     return (x);
 218   } else if (GE_PYCHECK(o)) {
 219     if ((x = G_TOINT(GE_G(o), MP_NEW, GE_X(o))) == 0)
 220       return (0);
 221     return (x);
 222   } else if (PyInt_Check(o))
 223     return (mp_fromlong(MP_NEW, PyInt_AS_LONG(o)));
 224   else if ((l = PyNumber_Long(o)) != 0) {
 225     x = mp_frompylong(l);
 226     Py_DECREF(l);
 227     return (x);
 228   } else {
 229     PyErr_Clear();
 230     return (0);
 231   }
 232 }
 233
 234 mp *getmp(PyObject *o)
 235 {
 236   mp *x = 0;
 237   if (!o) return (0);
 238   if ((x = tomp(o)) == 0) {
 239     PyErr_Format(PyExc_TypeError, "can't convert %.100s to mp",
 240                  o->ob_type->tp_name);
 241   }
 242   return (x);
 243 }
 244
 245 int convmp(PyObject *o, void *p)
 246 {
 247   mp *x;
 248   if ((x = getmp(o)) == 0) return (0);
 249   *(mp **)p = x;
 250   return (1);
 251 }
 252
 253 mp *getgf(PyObject *o)
 254 {
 255   mp *x = 0;
 256   if (!o) return (0);
 257   if ((x = tomp(o)) == 0) {
 258     PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
 259                  o->ob_type->tp_name);
 260   }
 261   return (x);
 262 }
 263
 264 int convgf(PyObject *o, void *p)
 265 {
 266   mp *x;
 267   if ((x = getgf(o)) == 0) return (0);
 268   *(mp **)p = x;
 269   return (1);
 270 }
 271
 272 static mp *implicitmp(PyObject *o)
 273 {
 274   if (!o ||
 275       GF_PYCHECK(o) ||
 276       ECPT_PYCHECK(o) ||
 277       FE_PYCHECK(o) ||
 278       GE_PYCHECK(o))
 279     return (0);
 280   return (tomp(o));
 281 }
 282
 283 static mp *implicitgf(PyObject *o)
 284 {
 285   if (!o ||
 286       MP_PYCHECK(o) ||
 287       ECPT_PYCHECK(o) ||
 288       FE_PYCHECK(o) ||
 289       GE_PYCHECK(o))
 290     return (0);
 291   return (tomp(o));
 292 }
 293
 294 static int mpbinop(PyObject *x, PyObject *y, mp **xx, mp **yy)
 295 {
 296   if ((*xx = implicitmp(x)) == 0)
 297     return (-1);
 298   if ((*yy = implicitmp(y)) == 0) {
 299     MP_DROP(*xx);
 300     return (-1);
 301   }
 302   return (0);
 303 }
 304
 305 static int gfbinop(PyObject *x, PyObject *y, mp **xx, mp **yy)
 306 {
 307   if ((*xx = implicitgf(x)) == 0)
 308     return (-1);
 309   if ((*yy = implicitgf(y)) == 0) {
 310     MP_DROP(*xx);
 311     return (-1);
 312   }
 313   return (0);
 314 }
 315
 316 #define gf_and mp_and
 317 #define gf_or mp_or
 318 #define gf_xor mp_xor
 319 #define BINOP(pre, name)                                                \
 320   static PyObject *pre##_py##name(PyObject *x, PyObject *y) {           \
 321     mp *xx, *yy, *zz;                                                   \
 322     if (pre##binop(x, y, &xx, &yy)) RETURN_NOTIMPL;                     \
 323     zz = pre##_##name(MP_NEW, xx, yy);                                  \
 324     MP_DROP(xx); MP_DROP(yy);                                           \
 325     return (pre##_pywrap(zz));                                          \
 326   }
 327 BINOP(mp, add)
 328 BINOP(mp, sub)
 329 BINOP(mp, mul)
 330 BINOP(mp, and2c)
 331 BINOP(mp, or2c)
 332 BINOP(mp, xor2c)
 333 BINOP(gf, add)
 334 BINOP(gf, sub)
 335 BINOP(gf, mul)
 336 BINOP(gf, and)
 337 BINOP(gf, or)
 338 BINOP(gf, xor)
 339 #undef BINOP
 340
 341 static mp *mp_abs(mp *d, mp *x)
 342 {
 343   if (MP_NEGP(x))
 344     return (mp_neg(d, x));
 345   MP_COPY(x);
 346   if (d) MP_DROP(d);
 347   return (x);
 348 }
 349
 350 #define UNOP(pre, name)                                                 \
 351   static PyObject *pre##_py##name(PyObject *x)                          \
 352     { return mp_pywrap(pre##_##name(MP_NEW, MP_X(x))); }
 353 UNOP(mp, neg)
 354 UNOP(mp, abs)
 355 UNOP(mp, not2c)
 356 #undef UNOP
 357
 358 static PyObject *mp_pyid(PyObject *x) { RETURN_OBJ(x); }
 359
 360 #define gf_lsr mp_lsr
 361 #define SHIFTOP(pre, name, rname)                                       \
 362   static PyObject *pre##_py##name(PyObject *x, PyObject *y) {           \
 363     mp *xx, *yy;                                                        \
 364     PyObject *z = 0;                                                    \
 365     long n;                                                             \
 366     if (pre##binop(x, y, &xx, &yy)) RETURN_NOTIMPL;                     \
 367     if (mp_tolong_checked(yy, &n, 1)) goto end;                         \
 368     if (n < 0)                                                          \
 369       z = pre##_pywrap(mp_##rname(MP_NEW, xx, -n));                     \
 370     else                                                                \
 371       z = pre##_pywrap(mp_##name(MP_NEW, xx, n));                       \
 372   end:                                                                  \
 373     MP_DROP(xx); MP_DROP(yy);                                           \
 374     return (z);                                                         \
 375   }
 376 SHIFTOP(mp, lsl2c, lsr2c)
 377 SHIFTOP(mp, lsr2c, lsl2c)
 378 SHIFTOP(gf, lsl, lsr)
 379 SHIFTOP(gf, lsr, lsl)
 380 #undef SHIFTOP
 381
 382 #define DIVOP(pre, name, qq, rr, gather)                                \
 383   static PyObject *pre##_py##name(PyObject *x, PyObject *y) {           \
 384     mp *xx, *yy;                                                        \
 385     PyObject *z = 0;                                                    \
 386     INIT_##qq(q) INIT_##rr(r)                                           \
 387     if (pre##binop(x, y, &xx, &yy)) RETURN_NOTIMPL;                     \
 388     if (MP_ZEROP(yy))                                                   \
 389       ZDIVERR("division by zero");                                      \
 390     pre##_div(ARG_##qq(q), ARG_##rr(r), xx, yy);                        \
 391     z = gather;                                                         \
 392   end:                                                                  \
 393     MP_DROP(xx); MP_DROP(yy);                                           \
 394     return (z);                                                         \
 395   }
 396 #define INIT_YES(p) mp *p = MP_NEW;
 397 #define INIT_NO(p)
 398 #define ARG_YES(p) &p
 399 #define ARG_NO(p) 0
 400 DIVOP(mp, divmod, YES, YES,
 401       Py_BuildValue("(NN)", mp_pywrap(q), mp_pywrap(r)))
 402 DIVOP(mp, div, YES, NO, mp_pywrap(q))
 403 DIVOP(mp, mod, NO, YES, mp_pywrap(r))
 404 DIVOP(gf, divmod, YES, YES,
 405       Py_BuildValue("(NN)", gf_pywrap(q), gf_pywrap(r)))
 406 DIVOP(gf, div, YES, NO, gf_pywrap(q))
 407 DIVOP(gf, mod, NO, YES, gf_pywrap(r))
 408 #undef INIT_YES
 409 #undef INIT_NO
 410 #undef ARG_YES
 411 #undef ARG_NO
 412 #undef DIVOP
 413
 414 static mp *mp_modinv_checked(mp *d, mp *x, mp *p)
 415 {
 416   mp *g = MP_NEW;
 417   mp_gcd(&g, 0, &d, p, x);
 418   if (!MP_EQ(g, MP_ONE)) {
 419     MP_DROP(g); MP_DROP(d);
 420     PyErr_SetString(PyExc_ZeroDivisionError, "no modular inverse");
 421     return (0);
 422   }
 423   MP_DROP(g); return (d);
 424 }
 425
 426 static PyObject *mp_pyexp(PyObject *x, PyObject *y, PyObject *z)
 427 {
 428   mp *xx = 0, *yy = 0, *zz = 0;
 429   mp *r = 0;
 430   PyObject *rc = 0;
 431
 432   if ((xx = implicitmp(x)) == 0 || (yy = implicitmp(y)) == 0 ||
 433       (z && z != Py_None && (zz = tomp(z)) == 0)) {
 434     mp_drop(xx); mp_drop(yy); mp_drop(zz);
 435     RETURN_NOTIMPL;
 436   }
 437   if (!z || z == Py_None) {
 438     if (MP_NEGP(yy)) VALERR("negative exponent");
 439     r = mp_exp(MP_NEW, xx, yy);
 440   } else {
 441     if (!MP_POSP(zz)) VALERR("modulus must be positive");
 442     if (MP_NEGP(yy)) {
 443       if ((xx = mp_modinv_checked(xx, xx, zz)) == 0) goto end;
 444       yy = mp_neg(yy, yy);
 445     }
 446     if (MP_ODDP(zz)) {
 447       mpmont mm;
 448       mpmont_create(&mm, zz);
 449       r = mpmont_exp(&mm, MP_NEW, xx, yy);
 450       mpmont_destroy(&mm);
 451     } else {
 452       mpbarrett mb;
 453       mpbarrett_create(&mb, zz);
 454       r = mpbarrett_exp(&mb, MP_NEW, xx, yy);
 455       mpbarrett_destroy(&mb);
 456     }
 457   }
 458   rc = mp_pywrap(r);
 459 end:
 460   mp_drop(xx); mp_drop(yy); mp_drop(zz);
 461   return (rc);
 462 }
 463
 464 static mp *gf_modinv_checked(mp *d, mp *x, mp *p)
 465 {
 466   mp *g = MP_NEW;
 467   gf_gcd(&g, 0, &d, p, x);
 468   if (!MP_EQ(g, MP_ONE)) {
 469     MP_DROP(g); MP_DROP(d);
 470     PyErr_SetString(PyExc_ZeroDivisionError, "no modular inverse");
 471     return (0);
 472   }
 473   MP_DROP(g); return (d);
 474 }
 475
 476 #define BASEOP(name, radix, pre)                                        \
 477   static PyObject *mp_py##name(PyObject *x)                             \
 478     { return mp_topystring(MP_X(x), radix, 0, pre, 0); }
 479 BASEOP(oct, 8, "0");
 480 BASEOP(hex, 16, "0x");
 481 #undef BASEOP
 482
 483 static int mp_pynonzerop(PyObject *x) { return !MP_ZEROP(MP_X(x)); }
 484
 485 static PyObject *mp_pyint(PyObject *x)
 486 {
 487   long l;
 488   if (!mp_tolong_checked(MP_X(x), &l, 0)) return (PyInt_FromLong(l));
 489   else return mp_topylong(MP_X(x));
 490 }
 491 static PyObject *mp_pylong(PyObject *x)
 492   { return (mp_topylong(MP_X(x))); }
 493 static PyObject *mp_pyfloat(PyObject *x)
 494 {
 495   PyObject *l = mp_topylong(MP_X(x));
 496   double f = PyLong_AsDouble(l);
 497   Py_DECREF(l);
 498   return (PyFloat_FromDouble(f));
 499 }
 500
 501 #define COERCE(pre, PRE)                                                \
 502   static int pre##_pycoerce(PyObject **x, PyObject **y)                 \
 503   {                                                                     \
 504     mp *z;                                                              \
 505                                                                         \
 506     if (PRE##_PYCHECK(*y)) {                                            \
 507       Py_INCREF(*x); Py_INCREF(*y);                                     \
 508       return (0);                                                       \
 509     }                                                                   \
 510     if ((z = tomp(*y)) != 0) {                                          \
 511       Py_INCREF(*x);                                                    \
 512       *y = pre##_pywrap(z);                                             \
 513       return (0);                                                       \
 514     }                                                                   \
 515     return (1);                                                         \
 516   }
 517 COERCE(mp, MP)
 518 COERCE(gf, GF)
 519 #undef COERCE
 520
 521 static int mp_pycompare(PyObject *x, PyObject *y)
 522   { return mp_cmp(MP_X(x), MP_X(y)); }
 523
 524 static PyObject *mp_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
 525 {
 526   PyObject *x;
 527   mp *z;
 528   mp_pyobj *zz = 0;
 529   int radix = 0;
 530   char *kwlist[] = { "x", "radix", 0 };
 531
 532   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:new", kwlist, &x, &radix))
 533     goto end;
 534   if (MP_PYCHECK(x)) RETURN_OBJ(x);
 535   if (!good_radix_p(radix, 1)) VALERR("bad radix");
 536   if ((z = mp_frompyobject(x, radix)) == 0) {
 537     PyErr_Format(PyExc_TypeError, "can't convert %.100s to mp",
 538                  x->ob_type->tp_name);
 539     goto end;
 540   }
 541   zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
 542   zz->x = z;
 543 end:
 544   return ((PyObject *)zz);
 545 }
 546
 547 static long mp_pyhash(PyObject *me)
 548 {
 549   long h;
 550   PyObject *l = mp_topylong(MP_X(me)); h = PyObject_Hash(l);
 551   Py_DECREF(l); return (h);
 552 }
 553
 554 static PyObject *mpmeth_jacobi(PyObject *me, PyObject *arg)
 555 {
 556   mp *y = 0;
 557   PyObject *z = 0;
 558
 559   if (!PyArg_ParseTuple(arg, "O&:jacobi", convmp, &y)) goto end;
 560   z = PyInt_FromLong(mp_jacobi(y, MP_X(me)));
 561 end:
 562   if (y) MP_DROP(y);
 563   return (z);
 564 }
 565
 566 #define BITOP(pre, name, c)                                             \
 567   static PyObject *pre##meth_##name(PyObject *me, PyObject *arg)        \
 568   {                                                                     \
 569     unsigned long i;                                                    \
 570     if (!PyArg_ParseTuple(arg, "O&:" #name, convulong, &i)) return (0); \
 571     return (pre##_pywrap(mp_##name##c(MP_NEW, MP_X(me), i)));           \
 572   }
 573 BITOP(mp, setbit, 2c);
 574 BITOP(mp, clearbit, 2c);
 575 BITOP(gf, setbit, );
 576 BITOP(gf, clearbit, );
 577 #undef BITOP
 578
 579 static PyObject *mpmeth_testbit(PyObject *me, PyObject *arg)
 580 {
 581   unsigned long i;
 582   if (!PyArg_ParseTuple(arg, "O&:testbit", convulong, &i)) return (0);
 583   return (getbool(mp_testbit2c(MP_X(me), i)));
 584 }
 585
 586 static PyObject *gfmeth_testbit(PyObject *me, PyObject *arg)
 587 {
 588   unsigned long i;
 589   if (!PyArg_ParseTuple(arg, "O&:testbit", convulong, &i)) return (0);
 590   return (getbool(mp_testbit(MP_X(me), i)));
 591 }
 592
 593 static PyObject *mpmeth_odd(PyObject *me, PyObject *arg)
 594 {
 595   mp *t;
 596   size_t s;
 597
 598   if (!PyArg_ParseTuple(arg, ":odd")) return (0);
 599   t = mp_odd(MP_NEW, MP_X(me), &s);
 600   return (Py_BuildValue("(lN)", (long)s, mp_pywrap(t)));
 601 }
 602
 603 static PyObject *mpmeth_sqr(PyObject *me, PyObject *arg)
 604 {
 605   if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
 606   return (mp_pywrap(mp_sqr(MP_NEW, MP_X(me))));
 607 }
 608
 609 static PyObject *mpmeth_sqrt(PyObject *me, PyObject *arg)
 610 {
 611   if (!PyArg_ParseTuple(arg, ":sqrt")) return (0);
 612   if (MP_NEGP(MP_X(me))) VALERR("negative root");
 613   return (mp_pywrap(mp_sqrt(MP_NEW, MP_X(me))));
 614 end:
 615   return (0);
 616 }
 617
 618 static PyObject *mpmeth_gcd(PyObject *me, PyObject *arg)
 619 {
 620   mp *y = 0, *zz = MP_NEW;
 621   PyObject *z = 0;
 622
 623   if (!PyArg_ParseTuple(arg, "O&:gcd", convmp, &y)) goto end;
 624   mp_gcd(&zz, 0, 0, MP_X(me), y);
 625   z = mp_pywrap(zz);
 626 end:
 627   if (y) MP_DROP(y);
 628   return (z);
 629 }
 630
 631 static PyObject *mpmeth_gcdx(PyObject *me, PyObject *arg)
 632 {
 633   PyObject *z = 0;
 634   mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
 635
 636   if (!PyArg_ParseTuple(arg, "O&:gcdx", convmp, &yy)) goto end;
 637   mp_gcd(&zz, &uu, &vv, MP_X(me), yy);
 638   z = Py_BuildValue("(NNN)",
 639                     mp_pywrap(zz), mp_pywrap(uu), mp_pywrap(vv));
 640 end:
 641   if (yy) MP_DROP(yy);
 642   return (z);
 643 }
 644
 645 static PyObject *mpmeth_modinv(PyObject *me, PyObject *arg)
 646 {
 647   PyObject *z = 0;
 648   mp *yy = 0, *zz = MP_NEW;
 649
 650   if (!PyArg_ParseTuple(arg, "O&:modinv", convmp, &yy) ||
 651       (zz = mp_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
 652     goto end;
 653   z = mp_pywrap(zz);
 654 end:
 655   if (yy) MP_DROP(yy);
 656   return (z);
 657 }
 658
 659 static PyObject *mpmeth_tostring(PyObject *me, PyObject *arg, PyObject *kw)
 660 {
 661   int radix = 10;
 662   char *kwlist[] = { "radix", 0 };
 663   if (!PyArg_ParseTupleAndKeywords(arg, kw, "|i:tostring", kwlist, &radix))
 664     goto end;
 665   if (!good_radix_p(radix, 0)) VALERR("bad radix");
 666   return (mp_topystring(MP_X(me), radix, 0, 0, 0));
 667 end:
 668   return (0);
 669 }
 670
 671 static PyObject *mpmeth_modsqrt(PyObject *me, PyObject *arg)
 672 {
 673   PyObject *z = 0;
 674   mp *yy = 0, *zz = MP_NEW;
 675
 676   if (!PyArg_ParseTuple(arg, "O&:modsqrt", convmp, &yy)) goto end;
 677   if ((zz = mp_modsqrt(MP_NEW, yy, MP_X(me))) == 0)
 678     VALERR("no modular square root");
 679   z = mp_pywrap(zz);
 680 end:
 681   if (yy) MP_DROP(yy);
 682   return (z);
 683 }
 684
 685 #define STOREOP(name, c)                                                \
 686   static PyObject *mpmeth_##name(PyObject *me,                          \
 687                                  PyObject *arg, PyObject *kw)           \
 688   {                                                                     \
 689     long len = -1;                                                      \
 690     char *kwlist[] = { "len", 0 };                                      \
 691     PyObject *rc = 0;                                                   \
 692                                                                         \
 693     if (!PyArg_ParseTupleAndKeywords(arg, kw, "|l:" #name,              \
 694                                     kwlist, &len))                      \
 695       goto end;                                                         \
 696     if (len < 0) {                                                      \
 697       len = mp_octets##c(MP_X(me));                                     \
 698       if (!len) len = 1;                                                \
 699     }                                                                   \
 700     rc = bytestring_pywrap(0, len);                                     \
 701     mp_##name(MP_X(me), PyString_AS_STRING(rc), len);                   \
 702   end:                                                                  \
 703     return (rc);                                                        \
 704   }
 705 STOREOP(storel, )
 706 STOREOP(storeb, )
 707 STOREOP(storel2c, 2c)
 708 STOREOP(storeb2c, 2c)
 709 #undef STOREOP
 710
 711 #define BUFOP(ty, pyty)                                                 \
 712   static PyObject *meth__##pyty##_frombuf(PyObject *me, PyObject *arg)  \
 713   {                                                                     \
 714     buf b;                                                              \
 715     char *p;                                                            \
 716     Py_ssize_t sz;                                                      \
 717     PyObject *rc = 0;                                                   \
 718     mp *x;                                                              \
 719                                                                         \
 720     if (!PyArg_ParseTuple(arg, "Os#:frombuf", &me, &p, &sz)) goto end;  \
 721     buf_init(&b, p, sz);                                                \
 722     if ((x = buf_getmp(&b)) == 0) VALERR("malformed data");             \
 723     rc = Py_BuildValue("(NN)", ty##_pywrap(x),                          \
 724                        bytestring_pywrapbuf(&b));                       \
 725   end:                                                                  \
 726     return (rc);                                                        \
 727   }
 728 BUFOP(mp, MP)
 729 BUFOP(gf, GF)
 730 #undef BUFOP
 731
 732 static PyObject *mpmeth_tobuf(PyObject *me, PyObject *arg)
 733 {
 734   buf b;
 735   PyObject *rc;
 736   mp *x;
 737   size_t n;
 738
 739   if (!PyArg_ParseTuple(arg, ":tobuf")) return (0);
 740   x = MP_X(me);
 741   n = mp_octets(x) + 3;
 742   rc = bytestring_pywrap(0, n);
 743   buf_init(&b, PyString_AS_STRING(rc), n);
 744   buf_putmp(&b, x);
 745   assert(BOK(&b));
 746   _PyString_Resize(&rc, BLEN(&b));
 747   return (rc);
 748 }
 749
 750 static PyObject *mpmeth_primep(PyObject *me, PyObject *arg, PyObject *kw)
 751 {
 752   grand *r = &rand_global;
 753   char *kwlist[] = { "rng", 0 };
 754   PyObject *rc = 0;
 755
 756   if (!PyArg_ParseTupleAndKeywords(arg, kw, "|O&", kwlist, convgrand, &r))
 757     goto end;
 758   rc = getbool(pgen_primep(MP_X(me), r));
 759 end:
 760   return (rc);
 761 }
 762
 763 static PyObject *mpget_nbits(PyObject *me, void *hunoz)
 764   { return (PyInt_FromLong(mp_bits(MP_X(me)))); }
 765
 766 static PyObject *mpget_noctets(PyObject *me, void *hunoz)
 767   { return (PyInt_FromLong(mp_octets(MP_X(me)))); }
 768
 769 static PyObject *mpget_noctets2c(PyObject *me, void *hunoz)
 770   { return (PyInt_FromLong(mp_octets2c(MP_X(me)))); }
 771
 772 static PyGetSetDef mp_pygetset[] = {
 773 #define GETSETNAME(op, func) mp##op##_##func
 774   GET   (nbits,         "X.nbits -> bit length of X")
 775   GET   (noctets,       "X.noctets -> octet length of X")
 776   GET   (noctets2c,     "X.noctets2c -> two's complement octet length of X")
 777 #undef GETSETNAME
 778   { 0 }
 779 };
 780
 781 static PyMethodDef mp_pymethods[] = {
 782 #define METHNAME(func) mpmeth_##func
 783   METH  (jacobi,        "X.jacobi(Y) -> Jacobi symbol (Y/X) (NB inversion!)")
 784   METH  (setbit,        "X.setbit(N) -> X with bit N set")
 785   METH  (clearbit,      "X.clearbit(N) -> X with bit N clear")
 786   METH  (testbit,       "X.testbit(N) -> true/false if bit N set/clear in X")
 787   METH  (odd,           "X.odd() -> S, T where X = 2^S T with T odd")
 788   METH  (sqr,           "X.sqr() -> X^2")
 789   METH  (sqrt,          "X.sqrt() -> largest integer <= sqrt(X)")
 790   METH  (gcd,           "X.gcd(Y) -> gcd(X, Y)")
 791   METH  (gcdx,
 792          "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
 793   METH  (modinv,        "X.modinv(Y) -> multiplicative inverse of Y mod X")
 794   METH  (modsqrt,       "X.modsqrt(Y) -> square root of Y mod X, if X prime")
 795   KWMETH(primep,        "X.primep(rng = rand) -> true/false if X is prime")
 796   KWMETH(tostring,      "X.tostring(radix = 10) -> STR")
 797   KWMETH(storel,        "X.storel(len = -1) -> little-endian bytes")
 798   KWMETH(storeb,        "X.storeb(len = -1) -> big-endian bytes")
 799   KWMETH(storel2c,
 800          "X.storel2c(len = -1) -> little-endian bytes, two's complement")
 801   KWMETH(storeb2c,
 802          "X.storeb2c(len = -1) -> big-endian bytes, two's complement")
 803   METH  (tobuf,         "X.tobuf() -> buffer format")
 804 #undef METHNAME
 805   { 0 }
 806 };
 807
 808 static PyNumberMethods mp_pynumber = {
 809   mp_pyadd,                             /* @nb_add@ */
 810   mp_pysub,                             /* @nb_subtract@ */
 811   mp_pymul,                             /* @nb_multiply@ */
 812   0,                                    /* @nb_divide@ */
 813   mp_pymod,                             /* @nb_remainder@ */
 814   mp_pydivmod,                          /* @nb_divmod@ */
 815   mp_pyexp,                             /* @nb_power@ */
 816   mp_pyneg,                             /* @nb_negative@ */
 817   mp_pyid,                              /* @nb_positive@ */
 818   mp_pyabs,                             /* @nb_absolute@ */
 819   mp_pynonzerop,                        /* @nb_nonzero@ */
 820   mp_pynot2c,                           /* @nb_invert@ */
 821   mp_pylsl2c,                           /* @nb_lshift@ */
 822   mp_pylsr2c,                           /* @nb_rshift@ */
 823   mp_pyand2c,                           /* @nb_and@ */
 824   mp_pyxor2c,                           /* @nb_xor@ */
 825   mp_pyor2c,                            /* @nb_or@ */
 826   mp_pycoerce,                          /* @nb_coerce@ */
 827   mp_pyint,                             /* @nb_int@ */
 828   mp_pylong,                            /* @nb_long@ */
 829   mp_pyfloat,                           /* @nb_float@ */
 830   mp_pyoct,                             /* @nb_oct@ */
 831   mp_pyhex,                             /* @nb_hex@ */
 832
 833   0,                                    /* @nb_inplace_add@ */
 834   0,                                    /* @nb_inplace_subtract@ */
 835   0,                                    /* @nb_inplace_multiply@ */
 836   0,                                    /* @nb_inplace_divide@ */
 837   0,                                    /* @nb_inplace_remainder@ */
 838   0,                                    /* @nb_inplace_power@ */
 839   0,                                    /* @nb_inplace_lshift@ */
 840   0,                                    /* @nb_inplace_rshift@ */
 841   0,                                    /* @nb_inplace_and@ */
 842   0,                                    /* @nb_inplace_xor@ */
 843   0,                                    /* @nb_inplace_or@ */
 844
 845   mp_pydiv,                             /* @nb_floor_divide@ */
 846   0,                                    /* @nb_true_divide@ */
 847   0,                                    /* @nb_inplace_floor_divide@ */
 848   0,                                    /* @nb_inplace_true_divide@ */
 849 };
 850
 851 static PyTypeObject mp_pytype_skel = {
 852   PyObject_HEAD_INIT(0) 0,              /* Header */
 853   "MP",                                 /* @tp_name@ */
 854   sizeof(mp_pyobj),                     /* @tp_basicsize@ */
 855   0,                                    /* @tp_itemsize@ */
 856
 857   mp_pydealloc,                         /* @tp_dealloc@ */
 858   0,                                    /* @tp_print@ */
 859   0,                                    /* @tp_getattr@ */
 860   0,                                    /* @tp_setattr@ */
 861   mp_pycompare,                         /* @tp_compare@ */
 862   mp_pyrepr,                            /* @tp_repr@ */
 863   &mp_pynumber,                         /* @tp_as_number@ */
 864   0,                                    /* @tp_as_sequence@ */
 865   0,                                    /* @tp_as_mapping@ */
 866   mp_pyhash,                            /* @tp_hash@ */
 867   0,                                    /* @tp_call@ */
 868   mp_pystr,                             /* @tp_str@ */
 869   0,                                    /* @tp_getattro@ */
 870   0,                                    /* @tp_setattro@ */
 871   0,                                    /* @tp_as_buffer@ */
 872   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 873     Py_TPFLAGS_CHECKTYPES |
 874     Py_TPFLAGS_BASETYPE,
 875
 876   /* @tp_doc@ */
 877 "Multiprecision integers, similar to `long' but more efficient and\n\
 878 versatile.  Support all the standard arithmetic operations.\n\
 879 \n\
 880 Constructor mp(X, radix = R) attempts to convert X to an `mp'.  If\n\
 881 X is a string, it's read in radix-R form, or we look for a prefix\n\
 882 if R = 0.  Other acceptable things are ints and longs.\n\
 883 \n\
 884 Notes:\n\
 885 \n\
 886   * Use `//' for division.  MPs don't have `/' division.",
 887
 888   0,                                    /* @tp_traverse@ */
 889   0,                                    /* @tp_clear@ */
 890   0,                                    /* @tp_richcompare@ */
 891   0,                                    /* @tp_weaklistoffset@ */
 892   0,                                    /* @tp_iter@ */
 893   0,                                    /* @tp_iternext@ */
 894   mp_pymethods,                         /* @tp_methods@ */
 895   0,                                    /* @tp_members@ */
 896   mp_pygetset,                          /* @tp_getset@ */
 897   0,                                    /* @tp_base@ */
 898   0,                                    /* @tp_dict@ */
 899   0,                                    /* @tp_descr_get@ */
 900   0,                                    /* @tp_descr_set@ */
 901   0,                                    /* @tp_dictoffset@ */
 902   0,                                    /* @tp_init@ */
 903   PyType_GenericAlloc,                  /* @tp_alloc@ */
 904   mp_pynew,                             /* @tp_new@ */
 905   0,                                    /* @tp_free@ */
 906   0                                     /* @tp_is_gc@ */
 907 };
 908
 909 static PyObject *meth__MP_fromstring(PyObject *me,
 910                                      PyObject *arg, PyObject *kw)
 911 {
 912   int r = 0;
 913   char *p;
 914   Py_ssize_t len;
 915   PyObject *z = 0;
 916   mp *zz;
 917   mptext_stringctx sc;
 918   char *kwlist[] = { "class", "x", "radix", 0 };
 919
 920   if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
 921                                    kwlist, &me, &p, &len, &r))
 922     goto end;
 923   if (!good_radix_p(r, 1)) VALERR("bad radix");
 924   sc.buf = p; sc.lim = p + len;
 925   if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0)
 926     VALERR("bad integer");
 927   z = Py_BuildValue("(Ns#)", mp_pywrap(zz),
 928                     sc.buf, (Py_ssize_t)(sc.lim - sc.buf));
 929 end:
 930   return (z);
 931 }
 932
 933 static PyObject *meth__MP_factorial(PyObject *me, PyObject *arg)
 934 {
 935   unsigned long i;
 936   mp *x;
 937   if (!PyArg_ParseTuple(arg, "OO&:factorial", &me, convulong, &i))
 938     return (0);
 939   x = mp_factorial(i);
 940   return mp_pywrap(x);
 941 }
 942
 943 static PyObject *meth__MP_fibonacci(PyObject *me, PyObject *arg)
 944 {
 945   long i;
 946   mp *x;
 947   if (!PyArg_ParseTuple(arg, "Ol:fibonacci", &me, &i)) return (0);
 948   x = mp_fibonacci(i);
 949   return mp_pywrap(x);
 950 }
 951
 952 #define LOADOP(pre, py, name)                                           \
 953   static PyObject *meth__##py##_##name(PyObject *me, PyObject *arg)     \
 954   {                                                                     \
 955     char *p;                                                            \
 956     Py_ssize_t len;                                                     \
 957     if (!PyArg_ParseTuple(arg, "Os#:" #name, &me, &p, &len)) return (0); \
 958     return (pre##_pywrap(mp_##name(MP_NEW, p, len)));                   \
 959   }
 960 LOADOP(mp, MP, loadl)
 961 LOADOP(mp, MP, loadb)
 962 LOADOP(mp, MP, loadl2c)
 963 LOADOP(mp, MP, loadb2c)
 964 LOADOP(gf, GF, loadl)
 965 LOADOP(gf, GF, loadb)
 966 #undef LOADOP
 967
 968 /*----- Products of small integers ----------------------------------------*/
 969
 970 typedef struct mpmul_pyobj {
 971   PyObject_HEAD
 972   int livep;
 973   mpmul mm;
 974 } mpmul_pyobj;
 975
 976 #define MPMUL_LIVEP(o) (((mpmul_pyobj *)(o))->livep)
 977 #define MPMUL_PY(o) (&((mpmul_pyobj *)(o))->mm)
 978
 979 static void mpmul_pydealloc(PyObject *me)
 980 {
 981   if (MPMUL_LIVEP(me))
 982     mp_drop(mpmul_done(MPMUL_PY(me)));
 983   FREEOBJ(me);
 984 }
 985
 986 static PyObject *mmmeth_factor(PyObject *me, PyObject *arg)
 987 {
 988   PyObject *q, *i;
 989   mp *x;
 990
 991   if (!MPMUL_LIVEP(me)) VALERR("MPMul object invalid");
 992   if (PyTuple_Size(arg) != 1)
 993     i = PyObject_GetIter(arg);
 994   else {
 995     if ((q = PyTuple_GetItem(arg, 0)) == 0) goto end;
 996     if ((i = PyObject_GetIter(q)) == 0) {
 997       PyErr_Clear(); /* that's ok */
 998       i = PyObject_GetIter(arg);
 999     }
1000   }
1001   if (!i) goto end;
1002   while ((q = PyIter_Next(i)) != 0) {
1003     x = getmp(q); Py_DECREF(q); if (!x) {
1004       Py_DECREF(i);
1005       goto end;
1006     }
1007     mpmul_add(MPMUL_PY(me), x);
1008     MP_DROP(x);
1009   }
1010   Py_DECREF(i);
1011   RETURN_ME;
1012 end:
1013   return (0);
1014 }
1015
1016 static PyObject *mmmeth_done(PyObject *me, PyObject *arg)
1017 {
1018   mp *x;
1019
1020   if (!PyArg_ParseTuple(arg, ":done")) goto end;
1021   if (!MPMUL_LIVEP(me)) VALERR("MPMul object invalid");
1022   x = mpmul_done(MPMUL_PY(me));
1023   MPMUL_LIVEP(me) = 0;
1024   return (mp_pywrap(x));
1025 end:
1026   return (0);
1027 }
1028
1029 static PyObject *mpmul_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1030 {
1031   mpmul_pyobj *mm;
1032
1033   if (kw) TYERR("keyword arguments not allowed here");
1034   mm = (mpmul_pyobj *)ty->tp_alloc(ty, 0);
1035   mpmul_init(&mm->mm);
1036   mm->livep = 1;
1037   if (mmmeth_factor((PyObject *)mm, arg) == 0) {
1038     Py_DECREF(mm);
1039     goto end;
1040   }
1041   return ((PyObject *)mm);
1042 end:
1043   return (0);
1044 }
1045
1046 static PyObject *mmget_livep(PyObject *me, void *hunoz)
1047   { return (getbool(MPMUL_LIVEP(me))); }
1048
1049 static PyGetSetDef mpmul_pygetset[] = {
1050 #define GETSETNAME(op, name) mm##op##_##name
1051   GET   (livep,                 "MM.livep -> flag: object still valid?")
1052 #undef GETSETNAME
1053   { 0 }
1054 };
1055
1056 static PyMethodDef mpmul_pymethods[] = {
1057 #define METHNAME(name) mmmeth_##name
1058   METH  (factor,                "MM.factor(ITERABLE) or MM.factor(I, ...)")
1059   METH  (done,                  "MM.done() -> PRODUCT")
1060 #undef METHNAME
1061   { 0 }
1062 };
1063
1064 static PyTypeObject *mpmul_pytype, mpmul_pytype_skel = {
1065   PyObject_HEAD_INIT(0) 0,              /* Header */
1066   "MPMul",                              /* @tp_name@ */
1067   sizeof(mpmul_pyobj),                  /* @tp_basicsize@ */
1068   0,                                    /* @tp_itemsize@ */
1069
1070   mpmul_pydealloc,                      /* @tp_dealloc@ */
1071   0,                                    /* @tp_print@ */
1072   0,                                    /* @tp_getattr@ */
1073   0,                                    /* @tp_setattr@ */
1074   0,                                    /* @tp_compare@ */
1075   0,                                    /* @tp_repr@ */
1076   0,                                    /* @tp_as_number@ */
1077   0,                                    /* @tp_as_sequence@ */
1078   0,                                    /* @tp_as_mapping@ */
1079   0,                                    /* @tp_hash@ */
1080   0,                                    /* @tp_call@ */
1081   0,                                    /* @tp_str@ */
1082   0,                                    /* @tp_getattro@ */
1083   0,                                    /* @tp_setattro@ */
1084   0,                                    /* @tp_as_buffer@ */
1085   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1086     Py_TPFLAGS_BASETYPE,
1087
1088   /* @tp_doc@ */
1089 "An object for multiplying many small integers.",
1090
1091   0,                                    /* @tp_traverse@ */
1092   0,                                    /* @tp_clear@ */
1093   0,                                    /* @tp_richcompare@ */
1094   0,                                    /* @tp_weaklistoffset@ */
1095   0,                                    /* @tp_iter@ */
1096   0,                                    /* @tp_iternext@ */
1097   mpmul_pymethods,                      /* @tp_methods@ */
1098   0,                                    /* @tp_members@ */
1099   mpmul_pygetset,                       /* @tp_getset@ */
1100   0,                                    /* @tp_base@ */
1101   0,                                    /* @tp_dict@ */
1102   0,                                    /* @tp_descr_get@ */
1103   0,                                    /* @tp_descr_set@ */
1104   0,                                    /* @tp_dictoffset@ */
1105   0,                                    /* @tp_init@ */
1106   PyType_GenericAlloc,                  /* @tp_alloc@ */
1107   mpmul_pynew,                          /* @tp_new@ */
1108   0,                                    /* @tp_free@ */
1109   0                                     /* @tp_is_gc@ */
1110 };
1111
1112 /*----- Montgomery reduction ----------------------------------------------*/
1113
1114 typedef struct mpmont_pyobj {
1115   PyObject_HEAD
1116   mpmont mm;
1117 } mpmont_pyobj;
1118
1119 #define MPMONT_PY(o) (&((mpmont_pyobj *)(o))->mm)
1120
1121 static PyObject *mmmeth_int(PyObject *me, PyObject *arg)
1122 {
1123   PyObject *z = 0;
1124   mp *yy = 0;
1125   mpmont *mm = MPMONT_PY(me);
1126
1127   if (!PyArg_ParseTuple(arg, "O&:in", convmp, &yy))
1128     goto end;
1129   mp_div(0, &yy, yy, mm->m);
1130   z = mp_pywrap(mpmont_mul(mm, MP_NEW, yy, mm->r2));
1131 end:
1132   if (yy) MP_DROP(yy);
1133   return (z);
1134 }
1135
1136 static PyObject *mmmeth_mul(PyObject *me, PyObject *arg)
1137 {
1138   PyObject *rc = 0;
1139   mp *yy = 0, *zz = 0;
1140
1141   if (!PyArg_ParseTuple(arg, "O&O&:mul", convmp, &yy, convmp, &zz))
1142     goto end;
1143   rc = mp_pywrap(mpmont_mul(MPMONT_PY(me), MP_NEW, yy, zz));
1144 end:
1145   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1146   return (rc);
1147 }
1148
1149 static PyObject *mmmeth_exp(PyObject *me, PyObject *arg)
1150 {
1151   PyObject *rc = 0;
1152   mp *yy = 0, *zz = 0;
1153
1154   if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1155     goto end;
1156   if (MP_NEGP(zz)) {
1157     if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
1158     zz = mp_neg(zz, zz);
1159   }
1160   rc = mp_pywrap(mpmont_exp(MPMONT_PY(me), MP_NEW, yy, zz));
1161 end:
1162   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1163   return (rc);
1164 }
1165
1166 static PyObject *mmmeth_expr(PyObject *me, PyObject *arg)
1167 {
1168   PyObject *rc = 0;
1169   mp *yy = 0, *zz = 0;
1170
1171   if (!PyArg_ParseTuple(arg, "O&O&:expr", convmp, &yy, convmp, &zz))
1172     goto end;
1173   if (MP_NEGP(zz)) {
1174     yy = mpmont_reduce(MPMONT_PY(me), yy, yy);
1175     if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
1176     yy = mpmont_mul(MPMONT_PY(me), yy, yy, MPMONT_PY(me)->r2);
1177     zz = mp_neg(zz, zz);
1178   }
1179   rc = mp_pywrap(mpmont_expr(MPMONT_PY(me), MP_NEW, yy, zz));
1180 end:
1181   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1182   return (rc);
1183 }
1184
1185 static PyObject *mm_mexpr_id(PyObject *me)
1186   { return mp_pywrap(MP_COPY(MPMONT_PY(me)->r)); }
1187
1188 static int mm_mexpr_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
1189 {
1190   mp *xx = 0, *yy = 0;
1191   mp_expfactor *f = p;
1192   mpmont *mm = MPMONT_PY(me);
1193
1194   if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
1195     goto fail;
1196   if (MP_NEGP(yy)) {
1197     xx = mpmont_reduce(mm, xx, xx);
1198     if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
1199       goto fail;
1200     xx = mpmont_mul(mm, xx, xx, mm->r2);
1201     yy = mp_neg(yy, yy);
1202   }
1203   f->base = xx;
1204   f->exp = yy;
1205   return (0);
1206
1207 fail:
1208   mp_drop(xx); mp_drop(yy);
1209   return (-1);
1210 }
1211
1212 static PyObject *mm_mexpr(PyObject *me, void *v, int n)
1213   { return mp_pywrap(mpmont_mexpr(MPMONT_PY(me), MP_NEW, v, n)); }
1214
1215 static void mp_mexp_drop(void *p)
1216 {
1217   mp_expfactor *f = p;
1218   mp_drop(f->base);
1219   mp_drop(f->exp);
1220 }
1221
1222 static PyObject *mmmeth_mexpr(PyObject *me, PyObject *arg)
1223 {
1224   return mexp_common(me, arg, sizeof(mp_expfactor),
1225                      mm_mexpr_id, mm_mexpr_fill, mm_mexpr, mp_mexp_drop);
1226 }
1227
1228 static PyObject *mp_mexp_id(PyObject *me)
1229   { return mp_pywrap(MP_ONE); }
1230
1231 static int mp_mexp_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
1232 {
1233   mp *xx = 0, *yy = 0;
1234   mp_expfactor *f = p;
1235
1236   if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
1237     goto fail;
1238   if (MP_NEGP(yy)) {
1239     if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
1240       goto fail;
1241     yy = mp_neg(yy, yy);
1242   }
1243   f->base = xx;
1244   f->exp = yy;
1245   return (0);
1246
1247 fail:
1248   mp_drop(xx); mp_drop(yy);
1249   return (-1);
1250 }
1251
1252 static PyObject *mm_mexp(PyObject *me, void *v, int n)
1253   { return mp_pywrap(mpmont_mexp(MPMONT_PY(me), MP_NEW, v, n)); }
1254
1255 static PyObject *mmmeth_mexp(PyObject *me, PyObject *arg)
1256 {
1257   return mexp_common(me, arg, sizeof(mp_expfactor),
1258                      mp_mexp_id, mp_mexp_fill, mm_mexp, mp_mexp_drop);
1259 }
1260
1261 #define mmmeth_ext mmmeth_reduce
1262 static PyObject *mmmeth_reduce(PyObject *me, PyObject *arg)
1263 {
1264   PyObject *z = 0;
1265   mp *yy = 0;
1266
1267   if (!PyArg_ParseTuple(arg, "O&", convmp, &yy)) goto end;
1268   z = mp_pywrap(mpmont_reduce(MPMONT_PY(me), MP_NEW, yy));
1269 end:
1270   return (z);
1271 }
1272
1273 static void mpmont_pydealloc(PyObject *me)
1274 {
1275   mpmont_destroy(MPMONT_PY(me));
1276   FREEOBJ(me);
1277 }
1278
1279 static PyObject *mpmont_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1280 {
1281   mpmont_pyobj *mm = 0;
1282   char *kwlist[] = { "m", 0 };
1283   mp *xx = 0;
1284
1285   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1286     goto end;
1287   if (!MP_POSP(xx) || !MP_ODDP(xx)) VALERR("m must be positive and odd");
1288   mm = (mpmont_pyobj *)ty->tp_alloc(ty, 0);
1289   mpmont_create(&mm->mm, xx);
1290 end:
1291   if (xx) MP_DROP(xx);
1292   return ((PyObject *)mm);
1293 }
1294
1295 static PyObject *mmget_m(PyObject *me, void *hunoz)
1296   { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->m))); }
1297
1298 static PyObject *mmget_r(PyObject *me, void *hunoz)
1299   { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r))); }
1300
1301 static PyObject *mmget_r2(PyObject *me, void *hunoz)
1302   { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r2))); }
1303
1304 static PyGetSetDef mpmont_pygetset[] = {
1305 #define GETSETNAME(op, name) mm##op##_##name
1306   GET   (m,             "M.m -> modulus for reduction")
1307   GET   (r,             "M.r -> multiplicative identity")
1308   GET   (r2,            "M.r2 -> M.r^2, Montgomerization factor")
1309 #undef GETSETNAME
1310   { 0 }
1311 };
1312
1313 static PyMethodDef mpmont_pymethods[] = {
1314 #define METHNAME(name) mmmeth_##name
1315   METH  (int,           "M.int(X) -> XR")
1316   METH  (mul,           "M.mul(XR, YR) -> ZR where Z = X Y")
1317   METH  (expr,          "M.expr(XR, N) -> ZR where Z = X^N mod M.m")
1318   METH  (mexpr,         "\
1319 M.mexpr([(XR0, N0), (XR1, N1), ...]) = ZR where Z = X0^N0 X1^N1 ... mod M.m\n\
1320 \t(the list may be flattened if this more convenient.)")
1321   METH  (reduce,        "M.reduce(XR) -> X")
1322   METH  (ext,           "M.ext(XR) -> X")
1323   METH  (exp,           "M.exp(X, N) -> X^N mod M.m")
1324   METH  (mexp,          "\
1325 M.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 ... mod M.m\n\
1326 \t(the list may be flattened if this more convenient.)")
1327 #undef METHNAME
1328   { 0 }
1329 };
1330
1331 static PyTypeObject *mpmont_pytype, mpmont_pytype_skel = {
1332   PyObject_HEAD_INIT(0) 0,              /* Header */
1333   "MPMont",                             /* @tp_name@ */
1334   sizeof(mpmont_pyobj),                 /* @tp_basicsize@ */
1335   0,                                    /* @tp_itemsize@ */
1336
1337   mpmont_pydealloc,                     /* @tp_dealloc@ */
1338   0,                                    /* @tp_print@ */
1339   0,                                    /* @tp_getattr@ */
1340   0,                                    /* @tp_setattr@ */
1341   0,                                    /* @tp_compare@ */
1342   0,                                    /* @tp_repr@ */
1343   0,                                    /* @tp_as_number@ */
1344   0,                                    /* @tp_as_sequence@ */
1345   0,                                    /* @tp_as_mapping@ */
1346   0,                                    /* @tp_hash@ */
1347   0,                                    /* @tp_call@ */
1348   0,                                    /* @tp_str@ */
1349   0,                                    /* @tp_getattro@ */
1350   0,                                    /* @tp_setattro@ */
1351   0,                                    /* @tp_as_buffer@ */
1352   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1353     Py_TPFLAGS_BASETYPE,
1354
1355   /* @tp_doc@ */
1356 "A Montgomery reduction context.",
1357
1358   0,                                    /* @tp_traverse@ */
1359   0,                                    /* @tp_clear@ */
1360   0,                                    /* @tp_richcompare@ */
1361   0,                                    /* @tp_weaklistoffset@ */
1362   0,                                    /* @tp_iter@ */
1363   0,                                    /* @tp_iternext@ */
1364   mpmont_pymethods,                     /* @tp_methods@ */
1365   0,                                    /* @tp_members@ */
1366   mpmont_pygetset,                      /* @tp_getset@ */
1367   0,                                    /* @tp_base@ */
1368   0,                                    /* @tp_dict@ */
1369   0,                                    /* @tp_descr_get@ */
1370   0,                                    /* @tp_descr_set@ */
1371   0,                                    /* @tp_dictoffset@ */
1372   0,                                    /* @tp_init@ */
1373   PyType_GenericAlloc,                  /* @tp_alloc@ */
1374   mpmont_pynew,                         /* @tp_new@ */
1375   0,                                    /* @tp_free@ */
1376   0                                     /* @tp_is_gc@ */
1377 };
1378
1379 /*----- Barrett reduction -------------------------------------------------*/
1380
1381 typedef struct mpbarrett_pyobj {
1382   PyObject_HEAD
1383   mpbarrett mb;
1384 } mpbarrett_pyobj;
1385
1386 #define MPBARRETT_PY(o) (&((mpbarrett_pyobj *)(o))->mb)
1387
1388 static PyObject *mbmeth_exp(PyObject *me, PyObject *arg)
1389 {
1390   PyObject *rc = 0;
1391   mp *yy = 0, *zz = 0;
1392
1393   if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1394     goto end;
1395   if (MP_NEGP(zz)) {
1396     if ((yy = mp_modinv_checked(yy, yy, MPBARRETT_PY(me)->m)) == 0) goto end;
1397     zz = mp_neg(zz, zz);
1398   }
1399   rc = mp_pywrap(mpbarrett_exp(MPBARRETT_PY(me), MP_NEW, yy, zz));
1400 end:
1401   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1402   return (rc);
1403 }
1404
1405 static PyObject *mb_mexp(PyObject *me, void *v, int n)
1406   { return mp_pywrap(mpbarrett_mexp(MPBARRETT_PY(me), MP_NEW, v, n)); }
1407
1408 static PyObject *mbmeth_mexp(PyObject *me, PyObject *arg)
1409 {
1410   return mexp_common(me, arg, sizeof(mp_expfactor),
1411                      mp_mexp_id, mp_mexp_fill, mb_mexp, mp_mexp_drop);
1412 }
1413
1414 static PyObject *mbmeth_reduce(PyObject *me, PyObject *arg)
1415 {
1416   PyObject *z = 0;
1417   mp *yy = 0;
1418
1419   if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy))
1420     goto end;
1421   z = mp_pywrap(mpbarrett_reduce(MPBARRETT_PY(me), MP_NEW, yy));
1422 end:
1423   return (z);
1424 }
1425
1426 static void mpbarrett_pydealloc(PyObject *me)
1427 {
1428   mpbarrett_destroy(MPBARRETT_PY(me));
1429   FREEOBJ(me);
1430 }
1431
1432 static PyObject *mpbarrett_pynew(PyTypeObject *ty,
1433                                  PyObject *arg, PyObject *kw)
1434 {
1435   mpbarrett_pyobj *mb = 0;
1436   char *kwlist[] = { "m", 0 };
1437   mp *xx = 0;
1438
1439   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1440     goto end;
1441   if (!MP_POSP(xx)) VALERR("m must be positive");
1442   mb = (mpbarrett_pyobj *)ty->tp_alloc(ty, 0);
1443   mpbarrett_create(&mb->mb, xx);
1444 end:
1445   if (xx) MP_DROP(xx);
1446   return ((PyObject *)mb);
1447 }
1448
1449 static PyObject *mbget_m(PyObject *me, void *hunoz)
1450   { return (mp_pywrap(MP_COPY(MPBARRETT_PY(me)->m))); }
1451
1452 static PyGetSetDef mpbarrett_pygetset[] = {
1453 #define GETSETNAME(op, name) mb##op##_##name
1454   GET   (m,             "B.m -> modulus for reduction")
1455 #undef GETSETNAME
1456   { 0 }
1457 };
1458
1459 static PyMethodDef mpbarrett_pymethods[] = {
1460 #define METHNAME(name) mbmeth_##name
1461   METH  (reduce,        "B.reduce(X) -> X mod B.m")
1462   METH  (exp,           "B.exp(X, N) -> X^N mod B.m")
1463   METH  (mexp,          "\
1464 B.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 ... mod B.m\n\
1465 \t(the list may be flattened if this more convenient.)")
1466 #undef METHNAME
1467   { 0 }
1468 };
1469
1470 static PyTypeObject *mpbarrett_pytype, mpbarrett_pytype_skel = {
1471   PyObject_HEAD_INIT(0) 0,              /* Header */
1472   "MPBarrett",                          /* @tp_name@ */
1473   sizeof(mpbarrett_pyobj),              /* @tp_basicsize@ */
1474   0,                                    /* @tp_itemsize@ */
1475
1476   mpbarrett_pydealloc,                  /* @tp_dealloc@ */
1477   0,                                    /* @tp_print@ */
1478   0,                                    /* @tp_getattr@ */
1479   0,                                    /* @tp_setattr@ */
1480   0,                                    /* @tp_compare@ */
1481   0,                                    /* @tp_repr@ */
1482   0,                                    /* @tp_as_number@ */
1483   0,                                    /* @tp_as_sequence@ */
1484   0,                                    /* @tp_as_mapping@ */
1485   0,                                    /* @tp_hash@ */
1486   0,                                    /* @tp_call@ */
1487   0,                                    /* @tp_str@ */
1488   0,                                    /* @tp_getattro@ */
1489   0,                                    /* @tp_setattro@ */
1490   0,                                    /* @tp_as_buffer@ */
1491   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1492     Py_TPFLAGS_BASETYPE,
1493
1494   /* @tp_doc@ */
1495 "A Barrett reduction context.",
1496
1497   0,                                    /* @tp_traverse@ */
1498   0,                                    /* @tp_clear@ */
1499   0,                                    /* @tp_richcompare@ */
1500   0,                                    /* @tp_weaklistoffset@ */
1501   0,                                    /* @tp_iter@ */
1502   0,                                    /* @tp_iternext@ */
1503   mpbarrett_pymethods,                  /* @tp_methods@ */
1504   0,                                    /* @tp_members@ */
1505   mpbarrett_pygetset,                   /* @tp_getset@ */
1506   0,                                    /* @tp_base@ */
1507   0,                                    /* @tp_dict@ */
1508   0,                                    /* @tp_descr_get@ */
1509   0,                                    /* @tp_descr_set@ */
1510   0,                                    /* @tp_dictoffset@ */
1511   0,                                    /* @tp_init@ */
1512   PyType_GenericAlloc,                  /* @tp_alloc@ */
1513   mpbarrett_pynew,                      /* @tp_new@ */
1514   0,                                    /* @tp_free@ */
1515   0                                     /* @tp_is_gc@ */
1516 };
1517
1518 /*----- Nice prime reduction ----------------------------------------------*/
1519
1520 typedef struct mpreduce_pyobj {
1521   PyObject_HEAD
1522   mpreduce mr;
1523 } mpreduce_pyobj;
1524
1525 #define MPREDUCE_PY(o) (&((mpreduce_pyobj *)(o))->mr)
1526
1527 static PyObject *mrmeth_exp(PyObject *me, PyObject *arg)
1528 {
1529   PyObject *rc = 0;
1530   mp *yy = 0, *zz = 0;
1531
1532   if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1533     goto end;
1534   if (MP_NEGP(zz)) {
1535     if ((yy = mp_modinv_checked(yy, yy, MPREDUCE_PY(me)->p)) == 0) goto end;
1536     zz = mp_neg(zz, zz);
1537   }
1538   rc = mp_pywrap(mpreduce_exp(MPREDUCE_PY(me), MP_NEW, yy, zz));
1539 end:
1540   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1541   return (rc);
1542 }
1543
1544 static PyObject *mrmeth_reduce(PyObject *me, PyObject *arg)
1545 {
1546   PyObject *z = 0;
1547   mp *yy = 0;
1548
1549   if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy)) goto end;
1550   z = mp_pywrap(mpreduce_do(MPREDUCE_PY(me), MP_NEW, yy));
1551 end:
1552   return (z);
1553 }
1554
1555 static void mpreduce_pydealloc(PyObject *me)
1556 {
1557   mpreduce_destroy(MPREDUCE_PY(me));
1558   FREEOBJ(me);
1559 }
1560
1561 static PyObject *mpreduce_pynew(PyTypeObject *ty,
1562                                  PyObject *arg, PyObject *kw)
1563 {
1564   mpreduce_pyobj *mr = 0;
1565   mpreduce r;
1566   char *kwlist[] = { "m", 0 };
1567   mp *xx = 0;
1568
1569   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1570     goto end;
1571   if (!MP_POSP(xx)) VALERR("m must be positive");
1572   if (mpreduce_create(&r, xx)) VALERR("bad modulus (must be 2^k - ...)");
1573   mr = (mpreduce_pyobj *)ty->tp_alloc(ty, 0);
1574   mr->mr = r;
1575 end:
1576   if (xx) MP_DROP(xx);
1577   return ((PyObject *)mr);
1578 }
1579
1580 static PyObject *mrget_m(PyObject *me, void *hunoz)
1581   { return (mp_pywrap(MP_COPY(MPREDUCE_PY(me)->p))); }
1582
1583 static PyGetSetDef mpreduce_pygetset[] = {
1584 #define GETSETNAME(op, name) mr##op##_##name
1585   GET   (m,             "R.m -> modulus for reduction")
1586 #undef GETSETNAME
1587   { 0 }
1588 };
1589
1590 static PyMethodDef mpreduce_pymethods[] = {
1591 #define METHNAME(name) mrmeth_##name
1592   METH  (reduce,        "R.reduce(X) -> X mod B.m")
1593   METH  (exp,           "R.exp(X, N) -> X^N mod B.m")
1594 #undef METHNAME
1595   { 0 }
1596 };
1597
1598 static PyTypeObject *mpreduce_pytype, mpreduce_pytype_skel = {
1599   PyObject_HEAD_INIT(0) 0,              /* Header */
1600   "MPReduce",                           /* @tp_name@ */
1601   sizeof(mpreduce_pyobj),               /* @tp_basicsize@ */
1602   0,                                    /* @tp_itemsize@ */
1603
1604   mpreduce_pydealloc,                   /* @tp_dealloc@ */
1605   0,                                    /* @tp_print@ */
1606   0,                                    /* @tp_getattr@ */
1607   0,                                    /* @tp_setattr@ */
1608   0,                                    /* @tp_compare@ */
1609   0,                                    /* @tp_repr@ */
1610   0,                                    /* @tp_as_number@ */
1611   0,                                    /* @tp_as_sequence@ */
1612   0,                                    /* @tp_as_mapping@ */
1613   0,                                    /* @tp_hash@ */
1614   0,                                    /* @tp_call@ */
1615   0,                                    /* @tp_str@ */
1616   0,                                    /* @tp_getattro@ */
1617   0,                                    /* @tp_setattro@ */
1618   0,                                    /* @tp_as_buffer@ */
1619   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1620     Py_TPFLAGS_BASETYPE,
1621
1622   /* @tp_doc@ */
1623 "A reduction context for reduction modulo primes of special form.",
1624
1625   0,                                    /* @tp_traverse@ */
1626   0,                                    /* @tp_clear@ */
1627   0,                                    /* @tp_richcompare@ */
1628   0,                                    /* @tp_weaklistoffset@ */
1629   0,                                    /* @tp_iter@ */
1630   0,                                    /* @tp_iternext@ */
1631   mpreduce_pymethods,                   /* @tp_methods@ */
1632   0,                                    /* @tp_members@ */
1633   mpreduce_pygetset,                    /* @tp_getset@ */
1634   0,                                    /* @tp_base@ */
1635   0,                                    /* @tp_dict@ */
1636   0,                                    /* @tp_descr_get@ */
1637   0,                                    /* @tp_descr_set@ */
1638   0,                                    /* @tp_dictoffset@ */
1639   0,                                    /* @tp_init@ */
1640   PyType_GenericAlloc,                  /* @tp_alloc@ */
1641   mpreduce_pynew,                       /* @tp_new@ */
1642   0,                                    /* @tp_free@ */
1643   0                                     /* @tp_is_gc@ */
1644 };
1645
1646 /*----- Chinese Remainder Theorem solution --------------------------------*/
1647
1648 typedef struct mpcrt_pyobj {
1649   PyObject_HEAD
1650   mpcrt c;
1651 } mpcrt_pyobj;
1652
1653 #define MPCRT_PY(o) (&((mpcrt_pyobj *)(o))->c)
1654
1655 static PyObject *mcmeth_solve(PyObject *me, PyObject *arg)
1656 {
1657   mpcrt *c = MPCRT_PY(me);
1658   PyObject *q = 0, *x, *z = 0;
1659   mp *xx;
1660   mp **v = 0;
1661   int i = 0, n = c->k;
1662
1663   Py_INCREF(me);
1664   if (PyTuple_Size(arg) == n)
1665     q = arg;
1666   else if (!PyArg_ParseTuple(arg, "O:solve", &q))
1667     goto end;
1668   Py_INCREF(q);
1669   if (!PySequence_Check(q)) TYERR("want a sequence of residues");
1670   if (PySequence_Size(q) != n) VALERR("residue count mismatch");
1671   v = xmalloc(n * sizeof(*v));
1672   for (i = 0; i < n; i++) {
1673     if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1674     xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1675     v[i] = xx;
1676   }
1677   z = mp_pywrap(mpcrt_solve(c, MP_NEW, v));
1678 end:
1679   if (v) {
1680     n = i;
1681     for (i = 0; i < n; i++)
1682       MP_DROP(v[i]);
1683     xfree(v);
1684   }
1685   Py_DECREF(me);
1686   Py_XDECREF(q);
1687   return (z);
1688 }
1689
1690 static void mpcrt_pydealloc(PyObject *me)
1691 {
1692   mpcrt *c = MPCRT_PY(me);
1693   mpcrt_destroy(c);
1694   xfree(c->v);
1695 }
1696
1697 static PyObject *mpcrt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1698 {
1699   mpcrt_mod *v = 0;
1700   int n, i = 0;
1701   char *kwlist[] = { "mv", 0 };
1702   PyObject *q = 0, *x;
1703   mp *xx;
1704   mpcrt_pyobj *c = 0;
1705
1706   if (PyTuple_Size(arg) > 1)
1707     q = arg;
1708   else if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &q))
1709     goto end;
1710   Py_INCREF(q);
1711   if (!PySequence_Check(q)) TYERR("want a sequence of moduli");
1712   n = PySequence_Size(q);
1713   if (PyErr_Occurred()) goto end;
1714   if (!n) VALERR("want at least one modulus");
1715   v = xmalloc(n * sizeof(*v));
1716   for (i = 0; i < n; i++) {
1717     if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1718     xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1719     v[i].m = xx; v[i].n = 0; v[i].ni = 0; v[i].nni = 0;
1720   }
1721   c = (mpcrt_pyobj *)ty->tp_alloc(ty, 0);
1722   mpcrt_create(&c->c, v, n, 0);
1723   Py_DECREF(q);
1724   return ((PyObject *)c);
1725
1726 end:
1727   if (v) {
1728     n = i;
1729     for (i = 0; i < n; i++)
1730       MP_DROP(v[i].m);
1731     xfree(v);
1732   }
1733   Py_XDECREF(q);
1734   return (0);
1735 }
1736
1737 static PyObject *mcget_product(PyObject *me, void *hunoz)
1738   { return (mp_pywrap(MP_COPY(MPCRT_PY(me)->mb.m))); }
1739
1740 static PyObject *mcget_moduli(PyObject *me, void *hunoz)
1741 {
1742   int i;
1743   PyObject *q;
1744   mpcrt *c = MPCRT_PY(me);
1745
1746   if ((q = PyList_New(c->k)) == 0) return (0);
1747   for (i = 0; i < c->k; i++)
1748     PyList_SetItem(q, i, mp_pywrap(c->v[i].m));
1749   return (q);
1750 }
1751
1752 static PyGetSetDef mpcrt_pygetset[] = {
1753 #define GETSETNAME(op, name) mc##op##_##name
1754   GET   (product,       "C.product -> product of moduli")
1755   GET   (moduli,        "C.moduli -> list of individual moduli")
1756 #undef GETSETNAME
1757   { 0 }
1758 };
1759
1760 static PyMethodDef mpcrt_pymethods[] = {
1761 #define METHNAME(name) mcmeth_##name
1762   METH  (solve,         "C.solve([R0, R1]) -> X mod C.product")
1763 #undef METHNAME
1764   { 0 }
1765 };
1766
1767 static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = {
1768   PyObject_HEAD_INIT(0) 0,              /* Header */
1769   "MPCRT",                              /* @tp_name@ */
1770   sizeof(mpcrt_pyobj),                  /* @tp_basicsize@ */
1771   0,                                    /* @tp_itemsize@ */
1772
1773   mpcrt_pydealloc,                      /* @tp_dealloc@ */
1774   0,                                    /* @tp_print@ */
1775   0,                                    /* @tp_getattr@ */
1776   0,                                    /* @tp_setattr@ */
1777   0,                                    /* @tp_compare@ */
1778   0,                                    /* @tp_repr@ */
1779   0,                                    /* @tp_as_number@ */
1780   0,                                    /* @tp_as_sequence@ */
1781   0,                                    /* @tp_as_mapping@ */
1782   0,                                    /* @tp_hash@ */
1783   0,                                    /* @tp_call@ */
1784   0,                                    /* @tp_str@ */
1785   0,                                    /* @tp_getattro@ */
1786   0,                                    /* @tp_setattro@ */
1787   0,                                    /* @tp_as_buffer@ */
1788   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1789     Py_TPFLAGS_BASETYPE,
1790
1791   /* @tp_doc@ */
1792 "A context for the solution of Chinese Remainder Theorem problems.",
1793
1794   0,                                    /* @tp_traverse@ */
1795   0,                                    /* @tp_clear@ */
1796   0,                                    /* @tp_richcompare@ */
1797   0,                                    /* @tp_weaklistoffset@ */
1798   0,                                    /* @tp_iter@ */
1799   0,                                    /* @tp_iternext@ */
1800   mpcrt_pymethods,                      /* @tp_methods@ */
1801   0,                                    /* @tp_members@ */
1802   mpcrt_pygetset,                       /* @tp_getset@ */
1803   0,                                    /* @tp_base@ */
1804   0,                                    /* @tp_dict@ */
1805   0,                                    /* @tp_descr_get@ */
1806   0,                                    /* @tp_descr_set@ */
1807   0,                                    /* @tp_dictoffset@ */
1808   0,                                    /* @tp_init@ */
1809   PyType_GenericAlloc,                  /* @tp_alloc@ */
1810   mpcrt_pynew,                          /* @tp_new@ */
1811   0,                                    /* @tp_free@ */
1812   0                                     /* @tp_is_gc@ */
1813 };
1814
1815 /*----- Binary polynomials ------------------------------------------------*/
1816
1817 static PyObject *gf_pyrepr(PyObject *o)
1818   { return mp_topystring(MP_X(o), 16, "GF(", "0x", "L)"); }
1819
1820 static PyObject *gf_pyrichcompare(PyObject *x, PyObject *y, int op)
1821 {
1822   mp *xx, *yy;
1823   int xl, yl;
1824   int b;
1825
1826   if (gfbinop(x, y, &xx, &yy)) RETURN_NOTIMPL;
1827   switch (op) {
1828     case Py_EQ: b = MP_EQ(xx, yy); break;
1829     case Py_NE: b = !MP_EQ(xx, yy); break;
1830     default:
1831       xl = mp_bits(xx);
1832       yl = mp_bits(yy);
1833       switch (op) {
1834         case Py_LT: b = xl < yl; break;
1835         case Py_LE: b = xl <= yl; break;
1836         case Py_GT: b = xl > yl; break;
1837         case Py_GE: b = xl >= yl; break;
1838         default: abort();
1839       }
1840       break;
1841   }
1842   MP_DROP(xx); MP_DROP(yy);
1843   return (getbool(b));
1844 }
1845
1846 static PyObject *gf_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1847 {
1848   PyObject *x;
1849   mp *z;
1850   mp_pyobj *zz = 0;
1851   int radix = 0;
1852   char *kwlist[] = { "x", "radix", 0 };
1853
1854   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:gf", kwlist, &x, &radix))
1855     goto end;
1856   if (GF_PYCHECK(x)) RETURN_OBJ(x);
1857   if (!good_radix_p(radix, 1)) VALERR("radix out of range");
1858   if ((z = mp_frompyobject(x, radix)) == 0) {
1859     PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
1860                  x->ob_type->tp_name);
1861     goto end;
1862   }
1863   if (MP_NEGP(z)) {
1864     MP_DROP(z);
1865     VALERR("gf cannot be negative");
1866   }
1867   zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
1868   zz->x = z;
1869 end:
1870   return ((PyObject *)zz);
1871 }
1872
1873 static long gf_pyhash(PyObject *me)
1874 {
1875   long i = mp_tolong(MP_X(me));
1876   i ^= 0xc7ecd67c; /* random perturbance */
1877   if (i == -1)
1878     i = -2;
1879   return (i);
1880 }
1881
1882 static PyObject *gf_pyexp(PyObject *x, PyObject *y, PyObject *z)
1883 {
1884   mp *xx = 0, *yy = 0, *zz = 0;
1885   mp *r = 0;
1886   PyObject *rc = 0;
1887
1888   if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 ||
1889       (z && z != Py_None && (zz = tomp(z)) == 0)) {
1890     mp_drop(xx); mp_drop(yy); mp_drop(zz);
1891     RETURN_NOTIMPL;
1892   }
1893   if (!z || z == Py_None) {
1894     if (MP_NEGP(yy)) VALERR("negative exponent");
1895     r = gf_exp(MP_NEW, xx, yy);
1896   } else {
1897     gfreduce gr;
1898     if (MP_ZEROP(zz)) ZDIVERR("zero modulus");
1899     if (MP_NEGP(yy)) {
1900       if ((xx = gf_modinv_checked(xx, xx, zz)) == 0) goto end;
1901       yy = mp_neg(yy, yy);
1902     }
1903     gfreduce_create(&gr, zz);
1904     r = gfreduce_exp(&gr, MP_NEW, xx, yy);
1905     gfreduce_destroy(&gr);
1906   }
1907   rc = gf_pywrap(r);
1908 end:
1909   mp_drop(xx); mp_drop(yy); mp_drop(zz);
1910   return (rc);
1911 }
1912
1913 static PyObject *gfmeth_sqr(PyObject *me, PyObject *arg)
1914 {
1915   if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
1916   return (gf_pywrap(gf_sqr(MP_NEW, MP_X(me))));
1917 }
1918
1919 static PyObject *gfmeth_gcd(PyObject *me, PyObject *arg)
1920 {
1921   PyObject *z = 0;
1922   mp *yy = 0, *zz = MP_NEW;
1923
1924   if (!PyArg_ParseTuple(arg, "O&:gcd", convgf, &yy)) goto end;
1925   gf_gcd(&zz, 0, 0, MP_X(me), yy);
1926   z = gf_pywrap(zz);
1927 end:
1928   if (yy) MP_DROP(yy);
1929   return (z);
1930 }
1931
1932 static PyObject *gfmeth_gcdx(PyObject *me, PyObject *arg)
1933 {
1934   PyObject *z = 0;
1935   mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
1936
1937   if (!PyArg_ParseTuple(arg, "O&:gcdx", convgf, &yy))
1938     goto end;
1939   gf_gcd(&zz, &uu, &vv, MP_X(me), yy);
1940   z = Py_BuildValue("(NNN)",
1941                     gf_pywrap(zz), gf_pywrap(uu), gf_pywrap(vv));
1942 end:
1943   if (yy) MP_DROP(yy);
1944   return (z);
1945 }
1946
1947 static PyObject *gfmeth_modinv(PyObject *me, PyObject *arg)
1948 {
1949   PyObject *z = 0;
1950   mp *yy = 0, *zz = MP_NEW;
1951
1952   if (!PyArg_ParseTuple(arg, "O&:modinv", convgf, &yy) ||
1953       (zz = gf_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
1954     goto end;
1955   z = gf_pywrap(zz);
1956 end:
1957   if (yy) MP_DROP(yy);
1958   return (z);
1959 }
1960
1961 static PyObject *gfmeth_irreduciblep(PyObject *me, PyObject *arg)
1962 {
1963   if (!PyArg_ParseTuple(arg, ":irreduciblep")) return (0);
1964   return getbool(gf_irreduciblep(MP_X(me)));
1965 }
1966
1967 static PyObject *gfget_degree(PyObject *me, void *hunoz)
1968   { return (PyInt_FromLong(mp_bits(MP_X(me)) - 1)); }
1969
1970 static PyGetSetDef gf_pygetset[] = {
1971 #define GETSETNAME(op, name) gf##op##_##name
1972   GET   (degree,        "X.degree -> polynomial degree of X")
1973 #undef GETSETNAME
1974 #define GETSETNAME(op, name) mp##op##_##name
1975   GET   (nbits,         "X.nbits -> bit length of X")
1976   GET   (noctets,       "X.noctets -> octet length of X")
1977 #undef GETSETNAME
1978   { 0 }
1979 };
1980
1981 static PyMethodDef gf_pymethods[] = {
1982 #define METHNAME(func) gfmeth_##func
1983   METH  (setbit,        "X.setbit(N) -> X with bit N set")
1984   METH  (clearbit,      "X.clearbit(N) -> X with bit N clear")
1985   METH  (testbit,       "X.testbit(N) -> true/false if bit N set/clear in X")
1986   METH  (sqr,           "X.sqr() -> X^2")
1987   METH  (gcd,           "X.gcd(Y) -> gcd(X, Y)")
1988   METH  (gcdx,
1989          "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
1990   METH  (modinv,        "X.modinv(Y) -> multiplicative inverse of Y mod X")
1991   METH  (irreduciblep,  "X.irreduciblep() -> true/false")
1992 #undef METHNAME
1993 #define METHNAME(func) mpmeth_##func
1994   KWMETH(tostring,      "X.tostring(radix = 10) -> STR")
1995   KWMETH(storel,        "X.storel(len = -1) -> little-endian bytes")
1996   KWMETH(storeb,        "X.storeb(len = -1) -> big-endian bytes")
1997   KWMETH(storel2c,
1998          "X.storel2c(len = -1) -> little-endian bytes, two's complement")
1999   KWMETH(storeb2c,
2000          "X.storeb2c(len = -1) -> big-endian bytes, two's complement")
2001   METH  (tobuf,         "X.tobuf() -> buffer format")
2002 #undef METHNAME
2003   { 0 }
2004 };
2005
2006 static PyNumberMethods gf_pynumber = {
2007   gf_pyadd,                             /* @nb_add@ */
2008   gf_pysub,                             /* @nb_subtract@ */
2009   gf_pymul,                             /* @nb_multiply@ */
2010   0,                                    /* @nb_divide@ */
2011   gf_pymod,                             /* @nb_remainder@ */
2012   gf_pydivmod,                          /* @nb_divmod@ */
2013   gf_pyexp,                             /* @nb_power@ */
2014   mp_pyid,                              /* @nb_negative@ */
2015   mp_pyid,                              /* @nb_positive@ */
2016   mp_pyid,                              /* @nb_absolute@ */
2017   mp_pynonzerop,                        /* @nb_nonzero@ */
2018   0 /* doesn't make any sense */,       /* @nb_invert@ */
2019   gf_pylsl,                             /* @nb_lshift@ */
2020   gf_pylsr,                             /* @nb_rshift@ */
2021   gf_pyand,                             /* @nb_and@ */
2022   gf_pyxor,                             /* @nb_xor@ */
2023   gf_pyor,                              /* @nb_or@ */
2024   gf_pycoerce,                          /* @nb_coerce@ */
2025   mp_pyint,                             /* @nb_int@ */
2026   mp_pylong,                            /* @nb_long@ */
2027   0 /* doesn't make any sense */,       /* @nb_float@ */
2028   mp_pyoct,                             /* @nb_oct@ */
2029   mp_pyhex,                             /* @nb_hex@ */
2030
2031   0,                                    /* @nb_inplace_add@ */
2032   0,                                    /* @nb_inplace_subtract@ */
2033   0,                                    /* @nb_inplace_multiply@ */
2034   0,                                    /* @nb_inplace_divide@ */
2035   0,                                    /* @nb_inplace_remainder@ */
2036   0,                                    /* @nb_inplace_power@ */
2037   0,                                    /* @nb_inplace_lshift@ */
2038   0,                                    /* @nb_inplace_rshift@ */
2039   0,                                    /* @nb_inplace_and@ */
2040   0,                                    /* @nb_inplace_xor@ */
2041   0,                                    /* @nb_inplace_or@ */
2042
2043   gf_pydiv,                             /* @nb_floor_divide@ */
2044   0,                                    /* @nb_true_divide@ */
2045   0,                                    /* @nb_inplace_floor_divide@ */
2046   0,                                    /* @nb_inplace_true_divide@ */
2047 };
2048
2049 static PyTypeObject gf_pytype_skel = {
2050   PyObject_HEAD_INIT(0) 0,              /* Header */
2051   "GF",                                 /* @tp_name@ */
2052   sizeof(mp_pyobj),                     /* @tp_basicsize@ */
2053   0,                                    /* @tp_itemsize@ */
2054
2055   mp_pydealloc,                         /* @tp_dealloc@ */
2056   0,                                    /* @tp_print@ */
2057   0,                                    /* @tp_getattr@ */
2058   0,                                    /* @tp_setattr@ */
2059   0,                                    /* @tp_compare@ */
2060   gf_pyrepr,                            /* @tp_repr@ */
2061   &gf_pynumber,                         /* @tp_as_number@ */
2062   0,                                    /* @tp_as_sequence@ */
2063   0,                                    /* @tp_as_mapping@ */
2064   gf_pyhash,                            /* @tp_hash@ */
2065   0,                                    /* @tp_call@ */
2066   mp_pyhex,                             /* @tp_str@ */
2067   0,                                    /* @tp_getattro@ */
2068   0,                                    /* @tp_setattro@ */
2069   0,                                    /* @tp_as_buffer@ */
2070   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
2071     Py_TPFLAGS_CHECKTYPES |
2072     Py_TPFLAGS_BASETYPE,
2073
2074   /* @tp_doc@ */
2075 "Binary polynomials.  Support almost all the standard arithmetic\n\
2076 operations.\n\
2077 \n\
2078 Constructor gf(X, radix = R) attempts to convert X to a `gf'.  If\n\
2079 X is a string, it's read in radix-R form, or we look for a prefix\n\
2080 if R = 0.  Other acceptable things are ints and longs.\n\
2081 \n\
2082 The name is hopelessly wrong from a technical point of view, but\n\
2083 but it's much easier to type than `p2' or `c2' or whatever.\n\
2084 \n\
2085 Notes:\n\
2086 \n\
2087   * Use `//' for division.  GFs don't have `/' division.",
2088
2089   0,                                    /* @tp_traverse@ */
2090   0,                                    /* @tp_clear@ */
2091   gf_pyrichcompare,                     /* @tp_richcompare@ */
2092   0,                                    /* @tp_weaklistoffset@ */
2093   0,                                    /* @tp_iter@ */
2094   0,                                    /* @tp_iternext@ */
2095   gf_pymethods,                         /* @tp_methods@ */
2096   0,                                    /* @tp_members@ */
2097   gf_pygetset,                          /* @tp_getset@ */
2098   0,                                    /* @tp_base@ */
2099   0,                                    /* @tp_dict@ */
2100   0,                                    /* @tp_descr_get@ */
2101   0,                                    /* @tp_descr_set@ */
2102   0,                                    /* @tp_dictoffset@ */
2103   0,                                    /* @tp_init@ */
2104   PyType_GenericAlloc,                  /* @tp_alloc@ */
2105   gf_pynew,                             /* @tp_new@ */
2106   0,                                    /* @tp_free@ */
2107   0                                     /* @tp_is_gc@ */
2108 };
2109
2110 static PyObject *meth__GF_fromstring(PyObject *me,
2111                                     PyObject *arg, PyObject *kw)
2112 {
2113   int r = 0;
2114   char *p;
2115   Py_ssize_t len;
2116   PyObject *z = 0;
2117   mp *zz;
2118   mptext_stringctx sc;
2119   char *kwlist[] = { "class", "x", "radix", 0 };
2120
2121   if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
2122                                    kwlist, &me, &p, &len, &r))
2123     goto end;
2124   if (!good_radix_p(r, 1)) VALERR("bad radix");
2125   sc.buf = p; sc.lim = p + len;
2126   if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0 ||
2127       MP_NEGP(zz)) {
2128     if (zz) MP_DROP(zz);
2129     VALERR("bad binary polynomial");
2130   }
2131   z = Py_BuildValue("(Ns#)", gf_pywrap(zz),
2132                     sc.buf, (Py_ssize_t)(sc.lim - sc.buf));
2133 end:
2134   return (z);
2135 }
2136
2137 /*----- Sparse poly reduction ---------------------------------------------*/
2138
2139 typedef struct gfreduce_pyobj {
2140   PyObject_HEAD
2141   gfreduce mr;
2142 } gfreduce_pyobj;
2143
2144 #define GFREDUCE_PY(o) (&((gfreduce_pyobj *)(o))->mr)
2145
2146 static PyObject *grmeth_exp(PyObject *me, PyObject *arg)
2147 {
2148   PyObject *rc = 0;
2149   mp *yy = 0, *zz = 0;
2150
2151   if (!PyArg_ParseTuple(arg, "O&O&:exp", convgf, &yy, convgf, &zz))
2152     goto end;
2153   if (MP_NEGP(zz)) {
2154     if ((yy = gf_modinv_checked(yy, yy, GFREDUCE_PY(me)->p)) == 0) goto end;
2155     zz = mp_neg(zz, zz);
2156   }
2157   rc = gf_pywrap(gfreduce_exp(GFREDUCE_PY(me), MP_NEW, yy, zz));
2158 end:
2159   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
2160   return (rc);
2161 }
2162
2163 static PyObject *grmeth_trace(PyObject *me, PyObject *arg)
2164 {
2165   PyObject *rc = 0;
2166   mp *xx = 0;
2167
2168   if (!PyArg_ParseTuple(arg, "O&:trace", convgf, &xx)) goto end;
2169   rc = PyInt_FromLong(gfreduce_trace(GFREDUCE_PY(me), xx));
2170 end:
2171   if (xx) MP_DROP(xx);
2172   return (rc);
2173 }
2174
2175 static PyObject *grmeth_halftrace(PyObject *me, PyObject *arg)
2176 {
2177   PyObject *rc = 0;
2178   mp *xx = 0;
2179
2180   if (!PyArg_ParseTuple(arg, "O&:halftrace", convgf, &xx)) goto end;
2181   rc = gf_pywrap(gfreduce_halftrace(GFREDUCE_PY(me), MP_NEW, xx));
2182 end:
2183   if (xx) MP_DROP(xx);
2184   return (rc);
2185 }
2186
2187 static PyObject *grmeth_sqrt(PyObject *me, PyObject *arg)
2188 {
2189   PyObject *rc = 0;
2190   mp *xx = 0, *yy;
2191
2192   if (!PyArg_ParseTuple(arg, "O&:sqrt", convgf, &xx)) goto end;
2193   if ((yy = gfreduce_sqrt(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
2194     VALERR("no modular square root");
2195   rc = gf_pywrap(yy);
2196 end:
2197   if (xx) MP_DROP(xx);
2198   return (rc);
2199 }
2200
2201 static PyObject *grmeth_quadsolve(PyObject *me, PyObject *arg)
2202 {
2203   PyObject *rc = 0;
2204   mp *xx = 0, *yy;
2205
2206   if (!PyArg_ParseTuple(arg, "O&:quadsolve", convgf, &xx)) goto end;
2207   if ((yy = gfreduce_quadsolve(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
2208     VALERR("no solution found");
2209   rc = gf_pywrap(yy);
2210 end:
2211   if (xx) MP_DROP(xx);
2212   return (rc);
2213 }
2214
2215 static PyObject *grmeth_reduce(PyObject *me, PyObject *arg)
2216 {
2217   PyObject *z = 0;
2218   mp *yy = 0;
2219
2220   if (!PyArg_ParseTuple(arg, "O&:reduce", convgf, &yy)) goto end;
2221   z = gf_pywrap(gfreduce_do(GFREDUCE_PY(me), MP_NEW, yy));
2222 end:
2223   return (z);
2224 }
2225
2226 static void gfreduce_pydealloc(PyObject *me)
2227 {
2228   gfreduce_destroy(GFREDUCE_PY(me));
2229   FREEOBJ(me);
2230 }
2231
2232 static PyObject *gfreduce_pynew(PyTypeObject *ty,
2233                                  PyObject *arg, PyObject *kw)
2234 {
2235   gfreduce_pyobj *mr = 0;
2236   gfreduce r;
2237   char *kwlist[] = { "m", 0 };
2238   mp *xx = 0;
2239
2240   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convgf, &xx))
2241     goto end;
2242   if (MP_ZEROP(xx)) ZDIVERR("modulus is zero!");
2243   gfreduce_create(&r, xx);
2244   mr = (gfreduce_pyobj *)ty->tp_alloc(ty, 0);
2245   mr->mr = r;
2246 end:
2247   if (xx) MP_DROP(xx);
2248   return ((PyObject *)mr);
2249 }
2250
2251 static PyObject *grget_m(PyObject *me, void *hunoz)
2252   { return (gf_pywrap(MP_COPY(GFREDUCE_PY(me)->p))); }
2253
2254 static PyGetSetDef gfreduce_pygetset[] = {
2255 #define GETSETNAME(op, name) gr##op##_##name
2256   GET   (m,             "R.m -> reduction polynomial")
2257 #undef GETSETNAME
2258   { 0 }
2259 };
2260
2261 static PyMethodDef gfreduce_pymethods[] = {
2262 #define METHNAME(name) grmeth_##name
2263   METH  (reduce,        "R.reduce(X) -> X mod B.m")
2264   METH  (trace,        "R.trace(X) -> Tr(X) = x + x^2 + ... + x^{2^{m - 1}}")
2265   METH  (halftrace,   "R.halftrace(X) -> x + x^{2^2} + ... + x^{2^{m - 1}}")
2266   METH  (sqrt,          "R.sqrt(X) -> Y where Y^2 = X mod R")
2267   METH  (quadsolve,     "R.quadsolve(X) -> Y where Y^2 + Y = X mod R")
2268   METH  (exp,           "R.exp(X, N) -> X^N mod B.m")
2269 #undef METHNAME
2270   { 0 }
2271 };
2272
2273 static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = {
2274   PyObject_HEAD_INIT(0) 0,              /* Header */
2275   "GFReduce",                           /* @tp_name@ */
2276   sizeof(gfreduce_pyobj),               /* @tp_basicsize@ */
2277   0,                                    /* @tp_itemsize@ */
2278
2279   gfreduce_pydealloc,                   /* @tp_dealloc@ */
2280   0,                                    /* @tp_print@ */
2281   0,                                    /* @tp_getattr@ */
2282   0,                                    /* @tp_setattr@ */
2283   0,                                    /* @tp_compare@ */
2284   0,                                    /* @tp_repr@ */
2285   0,                                    /* @tp_as_number@ */
2286   0,                                    /* @tp_as_sequence@ */
2287   0,                                    /* @tp_as_mapping@ */
2288   0,                                    /* @tp_hash@ */
2289   0,                                    /* @tp_call@ */
2290   0,                                    /* @tp_str@ */
2291   0,                                    /* @tp_getattro@ */
2292   0,                                    /* @tp_setattro@ */
2293   0,                                    /* @tp_as_buffer@ */
2294   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
2295     Py_TPFLAGS_BASETYPE,
2296
2297   /* @tp_doc@ */
2298 "A reduction context for reduction modulo sparse irreducible polynomials.",
2299
2300   0,                                    /* @tp_traverse@ */
2301   0,                                    /* @tp_clear@ */
2302   0,                                    /* @tp_richcompare@ */
2303   0,                                    /* @tp_weaklistoffset@ */
2304   0,                                    /* @tp_iter@ */
2305   0,                                    /* @tp_iternext@ */
2306   gfreduce_pymethods,                   /* @tp_methods@ */
2307   0,                                    /* @tp_members@ */
2308   gfreduce_pygetset,                    /* @tp_getset@ */
2309   0,                                    /* @tp_base@ */
2310   0,                                    /* @tp_dict@ */
2311   0,                                    /* @tp_descr_get@ */
2312   0,                                    /* @tp_descr_set@ */
2313   0,                                    /* @tp_dictoffset@ */
2314   0,                                    /* @tp_init@ */
2315   PyType_GenericAlloc,                  /* @tp_alloc@ */
2316   gfreduce_pynew,                       /* @tp_new@ */
2317   0,                                    /* @tp_free@ */
2318   0                                     /* @tp_is_gc@ */
2319 };
2320
2321 /*----- Normal/poly transformation ----------------------------------------*/
2322
2323 typedef struct gfn_pyobj {
2324   PyObject_HEAD
2325   mp *p;
2326   gfn ntop, pton;
2327 } gfn_pyobj;
2328
2329 static PyTypeObject *gfn_pytype, gfn_pytype_skel;
2330
2331 #define GFN_P(o) (((gfn_pyobj *)(o))->p)
2332 #define GFN_PTON(o) (&((gfn_pyobj *)(o))->pton)
2333 #define GFN_NTOP(o) (&((gfn_pyobj *)(o))->ntop)
2334
2335 static PyObject *gfn_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
2336 {
2337   mp *p = 0, *beta = 0;
2338   gfn_pyobj *gg = 0;
2339   char *kwlist[] = { "p", "beta", 0 };
2340
2341   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", kwlist,
2342                                    convgf, &p, convgf, &beta))
2343     goto end;
2344   gg = PyObject_New(gfn_pyobj, ty);
2345   if (gfn_create(p, beta, &gg->ntop, &gg->pton)) {
2346     FREEOBJ(gg);
2347     gg = 0;
2348     VALERR("can't invert transformation matrix");
2349   }
2350   gg->p = MP_COPY(p);
2351 end:
2352   mp_drop(p);
2353   mp_drop(beta);
2354   return ((PyObject *)gg);
2355 }
2356
2357 static PyObject *gfnget_p(PyObject *me, void *hunoz)
2358   { return (gf_pywrap(MP_COPY(GFN_P(me)))); }
2359
2360 static PyObject *gfnget_beta(PyObject *me, void *hunoz)
2361 {
2362   gfn *n = GFN_NTOP(me);
2363   mp *x = n->r[n->n - 1];
2364   return (gf_pywrap(MP_COPY(x)));
2365 }
2366
2367 #define XFORMOP(name, NAME)                                             \
2368   static PyObject *gfnmeth_##name(PyObject *me, PyObject *arg)          \
2369   {                                                                     \
2370     mp *xx = 0;                                                         \
2371     mp *z = 0;                                                          \
2372                                                                         \
2373     if (!PyArg_ParseTuple(arg, "O&:" #name, convgf, &xx)) goto end;     \
2374     z = gfn_transform(GFN_##NAME(me), MP_NEW, xx);                      \
2375   end:                                                                  \
2376     mp_drop(xx);                                                        \
2377     if (!z) return (0);                                                 \
2378     return (mp_pywrap(z));                                              \
2379   }
2380 XFORMOP(pton, PTON)
2381 XFORMOP(ntop, NTOP)
2382 #undef XFORMOP
2383
2384 static void gfn_pydealloc(PyObject *me)
2385 {
2386   gfn_destroy(GFN_PTON(me));
2387   gfn_destroy(GFN_NTOP(me));
2388   FREEOBJ(me);
2389 }
2390
2391 static PyGetSetDef gfn_pygetset[] = {
2392 #define GETSETNAME(op, name) gfn##op##_##name
2393   GET   (p,             "X.p -> polynomial basis, as polynomial")
2394   GET   (beta,          "X.beta -> normal basis element, in poly form")
2395 #undef GETSETNAME
2396   { 0 }
2397 };
2398
2399 static PyMethodDef gfn_pymethods[] = {
2400 #define METHNAME(name) gfnmeth_##name
2401   METH  (pton,          "X.pton(A) -> normal-basis representation of A")
2402   METH  (ntop,          "X.ntop(A) -> polynomial-basis representation of A")
2403 #undef METHNAME
2404   { 0 }
2405 };
2406
2407 static PyTypeObject gfn_pytype_skel = {
2408   PyObject_HEAD_INIT(0) 0,              /* Header */
2409   "GFN",                                /* @tp_name@ */
2410   sizeof(gfn_pyobj),                    /* @tp_basicsize@ */
2411   0,                                    /* @tp_itemsize@ */
2412
2413   gfn_pydealloc,                        /* @tp_dealloc@ */
2414   0,                                    /* @tp_print@ */
2415   0,                                    /* @tp_getattr@ */
2416   0,                                    /* @tp_setattr@ */
2417   0,                                    /* @tp_compare@ */
2418   0,                                    /* @tp_repr@ */
2419   0,                                    /* @tp_as_number@ */
2420   0,                                    /* @tp_as_sequence@ */
2421   0,                                    /* @tp_as_mapping@ */
2422   0,                                    /* @tp_hash@ */
2423   0,                                    /* @tp_call@ */
2424   0,                                    /* @tp_str@ */
2425   0,                                    /* @tp_getattro@ */
2426   0,                                    /* @tp_setattro@ */
2427   0,                                    /* @tp_as_buffer@ */
2428   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
2429     Py_TPFLAGS_BASETYPE,
2430
2431   /* @tp_doc@ */
2432 "An object for transforming elements of binary fields between polynomial\n\
2433 and normal basis representations.",
2434
2435   0,                                    /* @tp_traverse@ */
2436   0,                                    /* @tp_clear@ */
2437   0,                                    /* @tp_richcompare@ */
2438   0,                                    /* @tp_weaklistoffset@ */
2439   0,                                    /* @tp_iter@ */
2440   0,                                    /* @tp_iternext@ */
2441   gfn_pymethods,                        /* @tp_methods@ */
2442   0,                                    /* @tp_members@ */
2443   gfn_pygetset,                         /* @tp_getset@ */
2444   0,                                    /* @tp_base@ */
2445   0,                                    /* @tp_dict@ */
2446   0,                                    /* @tp_descr_get@ */
2447   0,                                    /* @tp_descr_set@ */
2448   0,                                    /* @tp_dictoffset@ */
2449   0,                                    /* @tp_init@ */
2450   PyType_GenericAlloc,                  /* @tp_alloc@ */
2451   gfn_pynew,                            /* @tp_new@ */
2452   0,                                    /* @tp_free@ */
2453   0                                     /* @tp_is_gc@ */
2454 };
2455
2456 /*----- Glue --------------------------------------------------------------*/
2457
2458 static PyMethodDef methods[] = {
2459 #define METHNAME(func) meth_##func
2460   KWMETH(_MP_fromstring,        "\
2461 fromstring(STR, radix = 0) -> (X, REST)\n\
2462 \n\
2463 Parse STR as a large integer, according to radix.  If radix is zero,\n\
2464 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2465 or `R_' for other radix R.")
2466   KWMETH(_GF_fromstring,        "\
2467 fromstring(STR, radix = 0) -> (X, REST)\n\
2468 \n\
2469 Parse STR as a binary polynomial, according to radix.  If radix is zero,\n\
2470 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2471 or `R_' for other radix R.")
2472   METH  (_MP_factorial,         "\
2473 factorial(I) -> I!: compute factorial")
2474   METH  (_MP_fibonacci,         "\
2475 fibonacci(I) -> F(I): compute Fibonacci number")
2476   METH  (_MP_loadl,             "\
2477 loadl(STR) -> X: read little-endian bytes")
2478   METH  (_MP_loadb,             "\
2479 loadb(STR) -> X: read big-endian bytes")
2480   METH  (_MP_loadl2c,           "\
2481 loadl2c(STR) -> X: read little-endian bytes, two's complement")
2482   METH  (_MP_loadb2c,           "\
2483 loadb2c(STR) -> X: read big-endian bytes, two's complement")
2484   METH  (_MP_frombuf,           "\
2485 frombuf(STR) -> (X, REST): read buffer format")
2486   METH  (_GF_loadl,             "\
2487 loadl(STR) -> X: read little-endian bytes")
2488   METH  (_GF_loadb,             "\
2489 loadb(STR) -> X: read big-endian bytes")
2490   METH  (_GF_frombuf,           "\
2491 frombuf(STR) -> (X, REST): read buffer format")
2492 #undef METHNAME
2493   { 0 }
2494 };
2495
2496 void mp_pyinit(void)
2497 {
2498   INITTYPE(mp, root);
2499   INITTYPE(gf, root);
2500   INITTYPE(mpmul, root);
2501   INITTYPE(mpmont, root);
2502   INITTYPE(mpbarrett, root);
2503   INITTYPE(mpreduce, root);
2504   INITTYPE(mpcrt, root);
2505   INITTYPE(gfreduce, root);
2506   INITTYPE(gfn, root);
2507   addmethods(methods);
2508 }
2509
2510 void mp_pyinsert(PyObject *mod)
2511 {
2512   INSERT("MP", mp_pytype);
2513   INSERT("MPMul", mpmul_pytype);
2514   INSERT("MPMont", mpmont_pytype);
2515   INSERT("MPBarrett", mpbarrett_pytype);
2516   INSERT("MPReduce", mpreduce_pytype);
2517   INSERT("MPCRT", mpcrt_pytype);
2518   INSERT("GF", gf_pytype);
2519   INSERT("GFReduce", gfreduce_pytype);
2520   INSERT("GFN", gfn_pytype);
2521 }
2522
2523 /*----- That's all, folks -------------------------------------------------*/