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 static PyObject *mpmeth_leastcongruent(PyObject *me, PyObject *arg)
 686 {
 687   mp *z, *b, *m;
 688   PyObject *rc = 0;
 689
 690   if (!PyArg_ParseTuple(arg, "O&O&:leastcongruent", convmp, &b, convmp, &m))
 691     goto end;
 692   z = mp_leastcongruent(MP_NEW, b, MP_X(me), m);
 693   rc = mp_pywrap(z);
 694 end:
 695   return (rc);
 696 }
 697
 698 #define STOREOP(name, c)                                                \
 699   static PyObject *mpmeth_##name(PyObject *me,                          \
 700                                  PyObject *arg, PyObject *kw)           \
 701   {                                                                     \
 702     long len = -1;                                                      \
 703     char *kwlist[] = { "len", 0 };                                      \
 704     PyObject *rc = 0;                                                   \
 705                                                                         \
 706     if (!PyArg_ParseTupleAndKeywords(arg, kw, "|l:" #name,              \
 707                                     kwlist, &len))                      \
 708       goto end;                                                         \
 709     if (len < 0) {                                                      \
 710       len = mp_octets##c(MP_X(me));                                     \
 711       if (!len) len = 1;                                                \
 712     }                                                                   \
 713     rc = bytestring_pywrap(0, len);                                     \
 714     mp_##name(MP_X(me), PyString_AS_STRING(rc), len);                   \
 715   end:                                                                  \
 716     return (rc);                                                        \
 717   }
 718 STOREOP(storel, )
 719 STOREOP(storeb, )
 720 STOREOP(storel2c, 2c)
 721 STOREOP(storeb2c, 2c)
 722 #undef STOREOP
 723
 724 #define BUFOP(ty, pyty)                                                 \
 725   static PyObject *meth__##pyty##_frombuf(PyObject *me, PyObject *arg)  \
 726   {                                                                     \
 727     buf b;                                                              \
 728     char *p;                                                            \
 729     Py_ssize_t sz;                                                      \
 730     PyObject *rc = 0;                                                   \
 731     mp *x;                                                              \
 732                                                                         \
 733     if (!PyArg_ParseTuple(arg, "Os#:frombuf", &me, &p, &sz)) goto end;  \
 734     buf_init(&b, p, sz);                                                \
 735     if ((x = buf_getmp(&b)) == 0) VALERR("malformed data");             \
 736     rc = Py_BuildValue("(NN)", ty##_pywrap(x),                          \
 737                        bytestring_pywrapbuf(&b));                       \
 738   end:                                                                  \
 739     return (rc);                                                        \
 740   }
 741 BUFOP(mp, MP)
 742 BUFOP(gf, GF)
 743 #undef BUFOP
 744
 745 static PyObject *mpmeth_tobuf(PyObject *me, PyObject *arg)
 746 {
 747   buf b;
 748   PyObject *rc;
 749   mp *x;
 750   size_t n;
 751
 752   if (!PyArg_ParseTuple(arg, ":tobuf")) return (0);
 753   x = MP_X(me);
 754   n = mp_octets(x) + 3;
 755   rc = bytestring_pywrap(0, n);
 756   buf_init(&b, PyString_AS_STRING(rc), n);
 757   buf_putmp(&b, x);
 758   assert(BOK(&b));
 759   _PyString_Resize(&rc, BLEN(&b));
 760   return (rc);
 761 }
 762
 763 static PyObject *mpmeth_primep(PyObject *me, PyObject *arg, PyObject *kw)
 764 {
 765   grand *r = &rand_global;
 766   char *kwlist[] = { "rng", 0 };
 767   PyObject *rc = 0;
 768
 769   if (!PyArg_ParseTupleAndKeywords(arg, kw, "|O&", kwlist, convgrand, &r))
 770     goto end;
 771   rc = getbool(pgen_primep(MP_X(me), r));
 772 end:
 773   return (rc);
 774 }
 775
 776 static PyObject *mpget_nbits(PyObject *me, void *hunoz)
 777   { return (PyInt_FromLong(mp_bits(MP_X(me)))); }
 778
 779 static PyObject *mpget_noctets(PyObject *me, void *hunoz)
 780   { return (PyInt_FromLong(mp_octets(MP_X(me)))); }
 781
 782 static PyObject *mpget_noctets2c(PyObject *me, void *hunoz)
 783   { return (PyInt_FromLong(mp_octets2c(MP_X(me)))); }
 784
 785 static PyGetSetDef mp_pygetset[] = {
 786 #define GETSETNAME(op, func) mp##op##_##func
 787   GET   (nbits,         "X.nbits -> bit length of X")
 788   GET   (noctets,       "X.noctets -> octet length of X")
 789   GET   (noctets2c,     "X.noctets2c -> two's complement octet length of X")
 790 #undef GETSETNAME
 791   { 0 }
 792 };
 793
 794 static PyMethodDef mp_pymethods[] = {
 795 #define METHNAME(func) mpmeth_##func
 796   METH  (jacobi,        "X.jacobi(Y) -> Jacobi symbol (Y/X) (NB inversion!)")
 797   METH  (setbit,        "X.setbit(N) -> X with bit N set")
 798   METH  (clearbit,      "X.clearbit(N) -> X with bit N clear")
 799   METH  (testbit,       "X.testbit(N) -> true/false if bit N set/clear in X")
 800   METH  (odd,           "X.odd() -> S, T where X = 2^S T with T odd")
 801   METH  (sqr,           "X.sqr() -> X^2")
 802   METH  (sqrt,          "X.sqrt() -> largest integer <= sqrt(X)")
 803   METH  (gcd,           "X.gcd(Y) -> gcd(X, Y)")
 804   METH  (gcdx,
 805          "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
 806   METH  (modinv,        "X.modinv(Y) -> multiplicative inverse of Y mod X")
 807   METH  (modsqrt,       "X.modsqrt(Y) -> square root of Y mod X, if X prime")
 808   METH  (leastcongruent,
 809          "X.leastcongruent(B, M) -> smallest Z >= B with Z == X (mod M)")
 810   KWMETH(primep,        "X.primep(rng = rand) -> true/false if X is prime")
 811   KWMETH(tostring,      "X.tostring(radix = 10) -> STR")
 812   KWMETH(storel,        "X.storel(len = -1) -> little-endian bytes")
 813   KWMETH(storeb,        "X.storeb(len = -1) -> big-endian bytes")
 814   KWMETH(storel2c,
 815          "X.storel2c(len = -1) -> little-endian bytes, two's complement")
 816   KWMETH(storeb2c,
 817          "X.storeb2c(len = -1) -> big-endian bytes, two's complement")
 818   METH  (tobuf,         "X.tobuf() -> buffer format")
 819 #undef METHNAME
 820   { 0 }
 821 };
 822
 823 static PyNumberMethods mp_pynumber = {
 824   mp_pyadd,                             /* @nb_add@ */
 825   mp_pysub,                             /* @nb_subtract@ */
 826   mp_pymul,                             /* @nb_multiply@ */
 827   0,                                    /* @nb_divide@ */
 828   mp_pymod,                             /* @nb_remainder@ */
 829   mp_pydivmod,                          /* @nb_divmod@ */
 830   mp_pyexp,                             /* @nb_power@ */
 831   mp_pyneg,                             /* @nb_negative@ */
 832   mp_pyid,                              /* @nb_positive@ */
 833   mp_pyabs,                             /* @nb_absolute@ */
 834   mp_pynonzerop,                        /* @nb_nonzero@ */
 835   mp_pynot2c,                           /* @nb_invert@ */
 836   mp_pylsl2c,                           /* @nb_lshift@ */
 837   mp_pylsr2c,                           /* @nb_rshift@ */
 838   mp_pyand2c,                           /* @nb_and@ */
 839   mp_pyxor2c,                           /* @nb_xor@ */
 840   mp_pyor2c,                            /* @nb_or@ */
 841   mp_pycoerce,                          /* @nb_coerce@ */
 842   mp_pyint,                             /* @nb_int@ */
 843   mp_pylong,                            /* @nb_long@ */
 844   mp_pyfloat,                           /* @nb_float@ */
 845   mp_pyoct,                             /* @nb_oct@ */
 846   mp_pyhex,                             /* @nb_hex@ */
 847
 848   0,                                    /* @nb_inplace_add@ */
 849   0,                                    /* @nb_inplace_subtract@ */
 850   0,                                    /* @nb_inplace_multiply@ */
 851   0,                                    /* @nb_inplace_divide@ */
 852   0,                                    /* @nb_inplace_remainder@ */
 853   0,                                    /* @nb_inplace_power@ */
 854   0,                                    /* @nb_inplace_lshift@ */
 855   0,                                    /* @nb_inplace_rshift@ */
 856   0,                                    /* @nb_inplace_and@ */
 857   0,                                    /* @nb_inplace_xor@ */
 858   0,                                    /* @nb_inplace_or@ */
 859
 860   mp_pydiv,                             /* @nb_floor_divide@ */
 861   0,                                    /* @nb_true_divide@ */
 862   0,                                    /* @nb_inplace_floor_divide@ */
 863   0,                                    /* @nb_inplace_true_divide@ */
 864 };
 865
 866 static PyTypeObject mp_pytype_skel = {
 867   PyObject_HEAD_INIT(0) 0,              /* Header */
 868   "MP",                                 /* @tp_name@ */
 869   sizeof(mp_pyobj),                     /* @tp_basicsize@ */
 870   0,                                    /* @tp_itemsize@ */
 871
 872   mp_pydealloc,                         /* @tp_dealloc@ */
 873   0,                                    /* @tp_print@ */
 874   0,                                    /* @tp_getattr@ */
 875   0,                                    /* @tp_setattr@ */
 876   mp_pycompare,                         /* @tp_compare@ */
 877   mp_pyrepr,                            /* @tp_repr@ */
 878   &mp_pynumber,                         /* @tp_as_number@ */
 879   0,                                    /* @tp_as_sequence@ */
 880   0,                                    /* @tp_as_mapping@ */
 881   mp_pyhash,                            /* @tp_hash@ */
 882   0,                                    /* @tp_call@ */
 883   mp_pystr,                             /* @tp_str@ */
 884   0,                                    /* @tp_getattro@ */
 885   0,                                    /* @tp_setattro@ */
 886   0,                                    /* @tp_as_buffer@ */
 887   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 888     Py_TPFLAGS_CHECKTYPES |
 889     Py_TPFLAGS_BASETYPE,
 890
 891   /* @tp_doc@ */
 892 "Multiprecision integers, similar to `long' but more efficient and\n\
 893 versatile.  Support all the standard arithmetic operations.\n\
 894 \n\
 895 Constructor mp(X, radix = R) attempts to convert X to an `mp'.  If\n\
 896 X is a string, it's read in radix-R form, or we look for a prefix\n\
 897 if R = 0.  Other acceptable things are ints and longs.\n\
 898 \n\
 899 Notes:\n\
 900 \n\
 901   * Use `//' for division.  MPs don't have `/' division.",
 902
 903   0,                                    /* @tp_traverse@ */
 904   0,                                    /* @tp_clear@ */
 905   0,                                    /* @tp_richcompare@ */
 906   0,                                    /* @tp_weaklistoffset@ */
 907   0,                                    /* @tp_iter@ */
 908   0,                                    /* @tp_iternext@ */
 909   mp_pymethods,                         /* @tp_methods@ */
 910   0,                                    /* @tp_members@ */
 911   mp_pygetset,                          /* @tp_getset@ */
 912   0,                                    /* @tp_base@ */
 913   0,                                    /* @tp_dict@ */
 914   0,                                    /* @tp_descr_get@ */
 915   0,                                    /* @tp_descr_set@ */
 916   0,                                    /* @tp_dictoffset@ */
 917   0,                                    /* @tp_init@ */
 918   PyType_GenericAlloc,                  /* @tp_alloc@ */
 919   mp_pynew,                             /* @tp_new@ */
 920   0,                                    /* @tp_free@ */
 921   0                                     /* @tp_is_gc@ */
 922 };
 923
 924 static PyObject *meth__MP_fromstring(PyObject *me,
 925                                      PyObject *arg, PyObject *kw)
 926 {
 927   int r = 0;
 928   char *p;
 929   Py_ssize_t len;
 930   PyObject *z = 0;
 931   mp *zz;
 932   mptext_stringctx sc;
 933   char *kwlist[] = { "class", "x", "radix", 0 };
 934
 935   if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
 936                                    kwlist, &me, &p, &len, &r))
 937     goto end;
 938   if (!good_radix_p(r, 1)) VALERR("bad radix");
 939   sc.buf = p; sc.lim = p + len;
 940   if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0)
 941     VALERR("bad integer");
 942   z = Py_BuildValue("(Ns#)", mp_pywrap(zz),
 943                     sc.buf, (Py_ssize_t)(sc.lim - sc.buf));
 944 end:
 945   return (z);
 946 }
 947
 948 static PyObject *meth__MP_factorial(PyObject *me, PyObject *arg)
 949 {
 950   unsigned long i;
 951   mp *x;
 952   if (!PyArg_ParseTuple(arg, "OO&:factorial", &me, convulong, &i))
 953     return (0);
 954   x = mp_factorial(i);
 955   return mp_pywrap(x);
 956 }
 957
 958 static PyObject *meth__MP_fibonacci(PyObject *me, PyObject *arg)
 959 {
 960   long i;
 961   mp *x;
 962   if (!PyArg_ParseTuple(arg, "Ol:fibonacci", &me, &i)) return (0);
 963   x = mp_fibonacci(i);
 964   return mp_pywrap(x);
 965 }
 966
 967 #define LOADOP(pre, py, name)                                           \
 968   static PyObject *meth__##py##_##name(PyObject *me, PyObject *arg)     \
 969   {                                                                     \
 970     char *p;                                                            \
 971     Py_ssize_t len;                                                     \
 972     if (!PyArg_ParseTuple(arg, "Os#:" #name, &me, &p, &len)) return (0); \
 973     return (pre##_pywrap(mp_##name(MP_NEW, p, len)));                   \
 974   }
 975 LOADOP(mp, MP, loadl)
 976 LOADOP(mp, MP, loadb)
 977 LOADOP(mp, MP, loadl2c)
 978 LOADOP(mp, MP, loadb2c)
 979 LOADOP(gf, GF, loadl)
 980 LOADOP(gf, GF, loadb)
 981 #undef LOADOP
 982
 983 /*----- Products of small integers ----------------------------------------*/
 984
 985 typedef struct mpmul_pyobj {
 986   PyObject_HEAD
 987   int livep;
 988   mpmul mm;
 989 } mpmul_pyobj;
 990
 991 #define MPMUL_LIVEP(o) (((mpmul_pyobj *)(o))->livep)
 992 #define MPMUL_PY(o) (&((mpmul_pyobj *)(o))->mm)
 993
 994 static void mpmul_pydealloc(PyObject *me)
 995 {
 996   if (MPMUL_LIVEP(me))
 997     mp_drop(mpmul_done(MPMUL_PY(me)));
 998   FREEOBJ(me);
 999 }
1000
1001 static PyObject *mmmeth_factor(PyObject *me, PyObject *arg)
1002 {
1003   PyObject *q, *i;
1004   mp *x;
1005
1006   if (!MPMUL_LIVEP(me)) VALERR("MPMul object invalid");
1007   if (PyTuple_Size(arg) != 1)
1008     i = PyObject_GetIter(arg);
1009   else {
1010     if ((q = PyTuple_GetItem(arg, 0)) == 0) goto end;
1011     if ((i = PyObject_GetIter(q)) == 0) {
1012       PyErr_Clear(); /* that's ok */
1013       i = PyObject_GetIter(arg);
1014     }
1015   }
1016   if (!i) goto end;
1017   while ((q = PyIter_Next(i)) != 0) {
1018     x = getmp(q); Py_DECREF(q); if (!x) {
1019       Py_DECREF(i);
1020       goto end;
1021     }
1022     mpmul_add(MPMUL_PY(me), x);
1023     MP_DROP(x);
1024   }
1025   Py_DECREF(i);
1026   RETURN_ME;
1027 end:
1028   return (0);
1029 }
1030
1031 static PyObject *mmmeth_done(PyObject *me, PyObject *arg)
1032 {
1033   mp *x;
1034
1035   if (!PyArg_ParseTuple(arg, ":done")) goto end;
1036   if (!MPMUL_LIVEP(me)) VALERR("MPMul object invalid");
1037   x = mpmul_done(MPMUL_PY(me));
1038   MPMUL_LIVEP(me) = 0;
1039   return (mp_pywrap(x));
1040 end:
1041   return (0);
1042 }
1043
1044 static PyObject *mpmul_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1045 {
1046   mpmul_pyobj *mm;
1047
1048   if (kw) TYERR("keyword arguments not allowed here");
1049   mm = (mpmul_pyobj *)ty->tp_alloc(ty, 0);
1050   mpmul_init(&mm->mm);
1051   mm->livep = 1;
1052   if (mmmeth_factor((PyObject *)mm, arg) == 0) {
1053     Py_DECREF(mm);
1054     goto end;
1055   }
1056   return ((PyObject *)mm);
1057 end:
1058   return (0);
1059 }
1060
1061 static PyObject *mmget_livep(PyObject *me, void *hunoz)
1062   { return (getbool(MPMUL_LIVEP(me))); }
1063
1064 static PyGetSetDef mpmul_pygetset[] = {
1065 #define GETSETNAME(op, name) mm##op##_##name
1066   GET   (livep,                 "MM.livep -> flag: object still valid?")
1067 #undef GETSETNAME
1068   { 0 }
1069 };
1070
1071 static PyMethodDef mpmul_pymethods[] = {
1072 #define METHNAME(name) mmmeth_##name
1073   METH  (factor,                "MM.factor(ITERABLE) or MM.factor(I, ...)")
1074   METH  (done,                  "MM.done() -> PRODUCT")
1075 #undef METHNAME
1076   { 0 }
1077 };
1078
1079 static PyTypeObject *mpmul_pytype, mpmul_pytype_skel = {
1080   PyObject_HEAD_INIT(0) 0,              /* Header */
1081   "MPMul",                              /* @tp_name@ */
1082   sizeof(mpmul_pyobj),                  /* @tp_basicsize@ */
1083   0,                                    /* @tp_itemsize@ */
1084
1085   mpmul_pydealloc,                      /* @tp_dealloc@ */
1086   0,                                    /* @tp_print@ */
1087   0,                                    /* @tp_getattr@ */
1088   0,                                    /* @tp_setattr@ */
1089   0,                                    /* @tp_compare@ */
1090   0,                                    /* @tp_repr@ */
1091   0,                                    /* @tp_as_number@ */
1092   0,                                    /* @tp_as_sequence@ */
1093   0,                                    /* @tp_as_mapping@ */
1094   0,                                    /* @tp_hash@ */
1095   0,                                    /* @tp_call@ */
1096   0,                                    /* @tp_str@ */
1097   0,                                    /* @tp_getattro@ */
1098   0,                                    /* @tp_setattro@ */
1099   0,                                    /* @tp_as_buffer@ */
1100   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1101     Py_TPFLAGS_BASETYPE,
1102
1103   /* @tp_doc@ */
1104 "An object for multiplying many small integers.",
1105
1106   0,                                    /* @tp_traverse@ */
1107   0,                                    /* @tp_clear@ */
1108   0,                                    /* @tp_richcompare@ */
1109   0,                                    /* @tp_weaklistoffset@ */
1110   0,                                    /* @tp_iter@ */
1111   0,                                    /* @tp_iternext@ */
1112   mpmul_pymethods,                      /* @tp_methods@ */
1113   0,                                    /* @tp_members@ */
1114   mpmul_pygetset,                       /* @tp_getset@ */
1115   0,                                    /* @tp_base@ */
1116   0,                                    /* @tp_dict@ */
1117   0,                                    /* @tp_descr_get@ */
1118   0,                                    /* @tp_descr_set@ */
1119   0,                                    /* @tp_dictoffset@ */
1120   0,                                    /* @tp_init@ */
1121   PyType_GenericAlloc,                  /* @tp_alloc@ */
1122   mpmul_pynew,                          /* @tp_new@ */
1123   0,                                    /* @tp_free@ */
1124   0                                     /* @tp_is_gc@ */
1125 };
1126
1127 /*----- Montgomery reduction ----------------------------------------------*/
1128
1129 typedef struct mpmont_pyobj {
1130   PyObject_HEAD
1131   mpmont mm;
1132 } mpmont_pyobj;
1133
1134 #define MPMONT_PY(o) (&((mpmont_pyobj *)(o))->mm)
1135
1136 static PyObject *mmmeth_int(PyObject *me, PyObject *arg)
1137 {
1138   PyObject *z = 0;
1139   mp *yy = 0;
1140   mpmont *mm = MPMONT_PY(me);
1141
1142   if (!PyArg_ParseTuple(arg, "O&:in", convmp, &yy))
1143     goto end;
1144   mp_div(0, &yy, yy, mm->m);
1145   z = mp_pywrap(mpmont_mul(mm, MP_NEW, yy, mm->r2));
1146 end:
1147   if (yy) MP_DROP(yy);
1148   return (z);
1149 }
1150
1151 static PyObject *mmmeth_mul(PyObject *me, PyObject *arg)
1152 {
1153   PyObject *rc = 0;
1154   mp *yy = 0, *zz = 0;
1155
1156   if (!PyArg_ParseTuple(arg, "O&O&:mul", convmp, &yy, convmp, &zz))
1157     goto end;
1158   rc = mp_pywrap(mpmont_mul(MPMONT_PY(me), MP_NEW, yy, zz));
1159 end:
1160   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1161   return (rc);
1162 }
1163
1164 static PyObject *mmmeth_exp(PyObject *me, PyObject *arg)
1165 {
1166   PyObject *rc = 0;
1167   mp *yy = 0, *zz = 0;
1168
1169   if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1170     goto end;
1171   if (MP_NEGP(zz)) {
1172     if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
1173     zz = mp_neg(zz, zz);
1174   }
1175   rc = mp_pywrap(mpmont_exp(MPMONT_PY(me), MP_NEW, yy, zz));
1176 end:
1177   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1178   return (rc);
1179 }
1180
1181 static PyObject *mmmeth_expr(PyObject *me, PyObject *arg)
1182 {
1183   PyObject *rc = 0;
1184   mp *yy = 0, *zz = 0;
1185
1186   if (!PyArg_ParseTuple(arg, "O&O&:expr", convmp, &yy, convmp, &zz))
1187     goto end;
1188   if (MP_NEGP(zz)) {
1189     yy = mpmont_reduce(MPMONT_PY(me), yy, yy);
1190     if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
1191     yy = mpmont_mul(MPMONT_PY(me), yy, yy, MPMONT_PY(me)->r2);
1192     zz = mp_neg(zz, zz);
1193   }
1194   rc = mp_pywrap(mpmont_expr(MPMONT_PY(me), MP_NEW, yy, zz));
1195 end:
1196   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1197   return (rc);
1198 }
1199
1200 static PyObject *mm_mexpr_id(PyObject *me)
1201   { return mp_pywrap(MP_COPY(MPMONT_PY(me)->r)); }
1202
1203 static int mm_mexpr_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
1204 {
1205   mp *xx = 0, *yy = 0;
1206   mp_expfactor *f = p;
1207   mpmont *mm = MPMONT_PY(me);
1208
1209   if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
1210     goto fail;
1211   if (MP_NEGP(yy)) {
1212     xx = mpmont_reduce(mm, xx, xx);
1213     if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
1214       goto fail;
1215     xx = mpmont_mul(mm, xx, xx, mm->r2);
1216     yy = mp_neg(yy, yy);
1217   }
1218   f->base = xx;
1219   f->exp = yy;
1220   return (0);
1221
1222 fail:
1223   mp_drop(xx); mp_drop(yy);
1224   return (-1);
1225 }
1226
1227 static PyObject *mm_mexpr(PyObject *me, void *v, int n)
1228   { return mp_pywrap(mpmont_mexpr(MPMONT_PY(me), MP_NEW, v, n)); }
1229
1230 static void mp_mexp_drop(void *p)
1231 {
1232   mp_expfactor *f = p;
1233   mp_drop(f->base);
1234   mp_drop(f->exp);
1235 }
1236
1237 static PyObject *mmmeth_mexpr(PyObject *me, PyObject *arg)
1238 {
1239   return mexp_common(me, arg, sizeof(mp_expfactor),
1240                      mm_mexpr_id, mm_mexpr_fill, mm_mexpr, mp_mexp_drop);
1241 }
1242
1243 static PyObject *mp_mexp_id(PyObject *me)
1244   { return mp_pywrap(MP_ONE); }
1245
1246 static int mp_mexp_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
1247 {
1248   mp *xx = 0, *yy = 0;
1249   mp_expfactor *f = p;
1250
1251   if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
1252     goto fail;
1253   if (MP_NEGP(yy)) {
1254     if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
1255       goto fail;
1256     yy = mp_neg(yy, yy);
1257   }
1258   f->base = xx;
1259   f->exp = yy;
1260   return (0);
1261
1262 fail:
1263   mp_drop(xx); mp_drop(yy);
1264   return (-1);
1265 }
1266
1267 static PyObject *mm_mexp(PyObject *me, void *v, int n)
1268   { return mp_pywrap(mpmont_mexp(MPMONT_PY(me), MP_NEW, v, n)); }
1269
1270 static PyObject *mmmeth_mexp(PyObject *me, PyObject *arg)
1271 {
1272   return mexp_common(me, arg, sizeof(mp_expfactor),
1273                      mp_mexp_id, mp_mexp_fill, mm_mexp, mp_mexp_drop);
1274 }
1275
1276 #define mmmeth_ext mmmeth_reduce
1277 static PyObject *mmmeth_reduce(PyObject *me, PyObject *arg)
1278 {
1279   PyObject *z = 0;
1280   mp *yy = 0;
1281
1282   if (!PyArg_ParseTuple(arg, "O&", convmp, &yy)) goto end;
1283   z = mp_pywrap(mpmont_reduce(MPMONT_PY(me), MP_NEW, yy));
1284 end:
1285   return (z);
1286 }
1287
1288 static void mpmont_pydealloc(PyObject *me)
1289 {
1290   mpmont_destroy(MPMONT_PY(me));
1291   FREEOBJ(me);
1292 }
1293
1294 static PyObject *mpmont_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1295 {
1296   mpmont_pyobj *mm = 0;
1297   char *kwlist[] = { "m", 0 };
1298   mp *xx = 0;
1299
1300   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1301     goto end;
1302   if (!MP_POSP(xx) || !MP_ODDP(xx)) VALERR("m must be positive and odd");
1303   mm = (mpmont_pyobj *)ty->tp_alloc(ty, 0);
1304   mpmont_create(&mm->mm, xx);
1305 end:
1306   if (xx) MP_DROP(xx);
1307   return ((PyObject *)mm);
1308 }
1309
1310 static PyObject *mmget_m(PyObject *me, void *hunoz)
1311   { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->m))); }
1312
1313 static PyObject *mmget_r(PyObject *me, void *hunoz)
1314   { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r))); }
1315
1316 static PyObject *mmget_r2(PyObject *me, void *hunoz)
1317   { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r2))); }
1318
1319 static PyGetSetDef mpmont_pygetset[] = {
1320 #define GETSETNAME(op, name) mm##op##_##name
1321   GET   (m,             "M.m -> modulus for reduction")
1322   GET   (r,             "M.r -> multiplicative identity")
1323   GET   (r2,            "M.r2 -> M.r^2, Montgomerization factor")
1324 #undef GETSETNAME
1325   { 0 }
1326 };
1327
1328 static PyMethodDef mpmont_pymethods[] = {
1329 #define METHNAME(name) mmmeth_##name
1330   METH  (int,           "M.int(X) -> XR")
1331   METH  (mul,           "M.mul(XR, YR) -> ZR where Z = X Y")
1332   METH  (expr,          "M.expr(XR, N) -> ZR where Z = X^N mod M.m")
1333   METH  (mexpr,         "\
1334 M.mexpr([(XR0, N0), (XR1, N1), ...]) = ZR where Z = X0^N0 X1^N1 ... mod M.m\n\
1335 \t(the list may be flattened if this more convenient.)")
1336   METH  (reduce,        "M.reduce(XR) -> X")
1337   METH  (ext,           "M.ext(XR) -> X")
1338   METH  (exp,           "M.exp(X, N) -> X^N mod M.m")
1339   METH  (mexp,          "\
1340 M.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 ... mod M.m\n\
1341 \t(the list may be flattened if this more convenient.)")
1342 #undef METHNAME
1343   { 0 }
1344 };
1345
1346 static PyTypeObject *mpmont_pytype, mpmont_pytype_skel = {
1347   PyObject_HEAD_INIT(0) 0,              /* Header */
1348   "MPMont",                             /* @tp_name@ */
1349   sizeof(mpmont_pyobj),                 /* @tp_basicsize@ */
1350   0,                                    /* @tp_itemsize@ */
1351
1352   mpmont_pydealloc,                     /* @tp_dealloc@ */
1353   0,                                    /* @tp_print@ */
1354   0,                                    /* @tp_getattr@ */
1355   0,                                    /* @tp_setattr@ */
1356   0,                                    /* @tp_compare@ */
1357   0,                                    /* @tp_repr@ */
1358   0,                                    /* @tp_as_number@ */
1359   0,                                    /* @tp_as_sequence@ */
1360   0,                                    /* @tp_as_mapping@ */
1361   0,                                    /* @tp_hash@ */
1362   0,                                    /* @tp_call@ */
1363   0,                                    /* @tp_str@ */
1364   0,                                    /* @tp_getattro@ */
1365   0,                                    /* @tp_setattro@ */
1366   0,                                    /* @tp_as_buffer@ */
1367   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1368     Py_TPFLAGS_BASETYPE,
1369
1370   /* @tp_doc@ */
1371 "A Montgomery reduction context.",
1372
1373   0,                                    /* @tp_traverse@ */
1374   0,                                    /* @tp_clear@ */
1375   0,                                    /* @tp_richcompare@ */
1376   0,                                    /* @tp_weaklistoffset@ */
1377   0,                                    /* @tp_iter@ */
1378   0,                                    /* @tp_iternext@ */
1379   mpmont_pymethods,                     /* @tp_methods@ */
1380   0,                                    /* @tp_members@ */
1381   mpmont_pygetset,                      /* @tp_getset@ */
1382   0,                                    /* @tp_base@ */
1383   0,                                    /* @tp_dict@ */
1384   0,                                    /* @tp_descr_get@ */
1385   0,                                    /* @tp_descr_set@ */
1386   0,                                    /* @tp_dictoffset@ */
1387   0,                                    /* @tp_init@ */
1388   PyType_GenericAlloc,                  /* @tp_alloc@ */
1389   mpmont_pynew,                         /* @tp_new@ */
1390   0,                                    /* @tp_free@ */
1391   0                                     /* @tp_is_gc@ */
1392 };
1393
1394 /*----- Barrett reduction -------------------------------------------------*/
1395
1396 typedef struct mpbarrett_pyobj {
1397   PyObject_HEAD
1398   mpbarrett mb;
1399 } mpbarrett_pyobj;
1400
1401 #define MPBARRETT_PY(o) (&((mpbarrett_pyobj *)(o))->mb)
1402
1403 static PyObject *mbmeth_exp(PyObject *me, PyObject *arg)
1404 {
1405   PyObject *rc = 0;
1406   mp *yy = 0, *zz = 0;
1407
1408   if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1409     goto end;
1410   if (MP_NEGP(zz)) {
1411     if ((yy = mp_modinv_checked(yy, yy, MPBARRETT_PY(me)->m)) == 0) goto end;
1412     zz = mp_neg(zz, zz);
1413   }
1414   rc = mp_pywrap(mpbarrett_exp(MPBARRETT_PY(me), MP_NEW, yy, zz));
1415 end:
1416   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1417   return (rc);
1418 }
1419
1420 static PyObject *mb_mexp(PyObject *me, void *v, int n)
1421   { return mp_pywrap(mpbarrett_mexp(MPBARRETT_PY(me), MP_NEW, v, n)); }
1422
1423 static PyObject *mbmeth_mexp(PyObject *me, PyObject *arg)
1424 {
1425   return mexp_common(me, arg, sizeof(mp_expfactor),
1426                      mp_mexp_id, mp_mexp_fill, mb_mexp, mp_mexp_drop);
1427 }
1428
1429 static PyObject *mbmeth_reduce(PyObject *me, PyObject *arg)
1430 {
1431   PyObject *z = 0;
1432   mp *yy = 0;
1433
1434   if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy))
1435     goto end;
1436   z = mp_pywrap(mpbarrett_reduce(MPBARRETT_PY(me), MP_NEW, yy));
1437 end:
1438   return (z);
1439 }
1440
1441 static void mpbarrett_pydealloc(PyObject *me)
1442 {
1443   mpbarrett_destroy(MPBARRETT_PY(me));
1444   FREEOBJ(me);
1445 }
1446
1447 static PyObject *mpbarrett_pynew(PyTypeObject *ty,
1448                                  PyObject *arg, PyObject *kw)
1449 {
1450   mpbarrett_pyobj *mb = 0;
1451   char *kwlist[] = { "m", 0 };
1452   mp *xx = 0;
1453
1454   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1455     goto end;
1456   if (!MP_POSP(xx)) VALERR("m must be positive");
1457   mb = (mpbarrett_pyobj *)ty->tp_alloc(ty, 0);
1458   mpbarrett_create(&mb->mb, xx);
1459 end:
1460   if (xx) MP_DROP(xx);
1461   return ((PyObject *)mb);
1462 }
1463
1464 static PyObject *mbget_m(PyObject *me, void *hunoz)
1465   { return (mp_pywrap(MP_COPY(MPBARRETT_PY(me)->m))); }
1466
1467 static PyGetSetDef mpbarrett_pygetset[] = {
1468 #define GETSETNAME(op, name) mb##op##_##name
1469   GET   (m,             "B.m -> modulus for reduction")
1470 #undef GETSETNAME
1471   { 0 }
1472 };
1473
1474 static PyMethodDef mpbarrett_pymethods[] = {
1475 #define METHNAME(name) mbmeth_##name
1476   METH  (reduce,        "B.reduce(X) -> X mod B.m")
1477   METH  (exp,           "B.exp(X, N) -> X^N mod B.m")
1478   METH  (mexp,          "\
1479 B.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 ... mod B.m\n\
1480 \t(the list may be flattened if this more convenient.)")
1481 #undef METHNAME
1482   { 0 }
1483 };
1484
1485 static PyTypeObject *mpbarrett_pytype, mpbarrett_pytype_skel = {
1486   PyObject_HEAD_INIT(0) 0,              /* Header */
1487   "MPBarrett",                          /* @tp_name@ */
1488   sizeof(mpbarrett_pyobj),              /* @tp_basicsize@ */
1489   0,                                    /* @tp_itemsize@ */
1490
1491   mpbarrett_pydealloc,                  /* @tp_dealloc@ */
1492   0,                                    /* @tp_print@ */
1493   0,                                    /* @tp_getattr@ */
1494   0,                                    /* @tp_setattr@ */
1495   0,                                    /* @tp_compare@ */
1496   0,                                    /* @tp_repr@ */
1497   0,                                    /* @tp_as_number@ */
1498   0,                                    /* @tp_as_sequence@ */
1499   0,                                    /* @tp_as_mapping@ */
1500   0,                                    /* @tp_hash@ */
1501   0,                                    /* @tp_call@ */
1502   0,                                    /* @tp_str@ */
1503   0,                                    /* @tp_getattro@ */
1504   0,                                    /* @tp_setattro@ */
1505   0,                                    /* @tp_as_buffer@ */
1506   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1507     Py_TPFLAGS_BASETYPE,
1508
1509   /* @tp_doc@ */
1510 "A Barrett reduction context.",
1511
1512   0,                                    /* @tp_traverse@ */
1513   0,                                    /* @tp_clear@ */
1514   0,                                    /* @tp_richcompare@ */
1515   0,                                    /* @tp_weaklistoffset@ */
1516   0,                                    /* @tp_iter@ */
1517   0,                                    /* @tp_iternext@ */
1518   mpbarrett_pymethods,                  /* @tp_methods@ */
1519   0,                                    /* @tp_members@ */
1520   mpbarrett_pygetset,                   /* @tp_getset@ */
1521   0,                                    /* @tp_base@ */
1522   0,                                    /* @tp_dict@ */
1523   0,                                    /* @tp_descr_get@ */
1524   0,                                    /* @tp_descr_set@ */
1525   0,                                    /* @tp_dictoffset@ */
1526   0,                                    /* @tp_init@ */
1527   PyType_GenericAlloc,                  /* @tp_alloc@ */
1528   mpbarrett_pynew,                      /* @tp_new@ */
1529   0,                                    /* @tp_free@ */
1530   0                                     /* @tp_is_gc@ */
1531 };
1532
1533 /*----- Nice prime reduction ----------------------------------------------*/
1534
1535 typedef struct mpreduce_pyobj {
1536   PyObject_HEAD
1537   mpreduce mr;
1538 } mpreduce_pyobj;
1539
1540 #define MPREDUCE_PY(o) (&((mpreduce_pyobj *)(o))->mr)
1541
1542 static PyObject *mrmeth_exp(PyObject *me, PyObject *arg)
1543 {
1544   PyObject *rc = 0;
1545   mp *yy = 0, *zz = 0;
1546
1547   if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1548     goto end;
1549   if (MP_NEGP(zz)) {
1550     if ((yy = mp_modinv_checked(yy, yy, MPREDUCE_PY(me)->p)) == 0) goto end;
1551     zz = mp_neg(zz, zz);
1552   }
1553   rc = mp_pywrap(mpreduce_exp(MPREDUCE_PY(me), MP_NEW, yy, zz));
1554 end:
1555   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1556   return (rc);
1557 }
1558
1559 static PyObject *mrmeth_reduce(PyObject *me, PyObject *arg)
1560 {
1561   PyObject *z = 0;
1562   mp *yy = 0;
1563
1564   if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy)) goto end;
1565   z = mp_pywrap(mpreduce_do(MPREDUCE_PY(me), MP_NEW, yy));
1566 end:
1567   return (z);
1568 }
1569
1570 static void mpreduce_pydealloc(PyObject *me)
1571 {
1572   mpreduce_destroy(MPREDUCE_PY(me));
1573   FREEOBJ(me);
1574 }
1575
1576 static PyObject *mpreduce_pynew(PyTypeObject *ty,
1577                                  PyObject *arg, PyObject *kw)
1578 {
1579   mpreduce_pyobj *mr = 0;
1580   mpreduce r;
1581   char *kwlist[] = { "m", 0 };
1582   mp *xx = 0;
1583
1584   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1585     goto end;
1586   if (!MP_POSP(xx)) VALERR("m must be positive");
1587   if (mpreduce_create(&r, xx)) VALERR("bad modulus (must be 2^k - ...)");
1588   mr = (mpreduce_pyobj *)ty->tp_alloc(ty, 0);
1589   mr->mr = r;
1590 end:
1591   if (xx) MP_DROP(xx);
1592   return ((PyObject *)mr);
1593 }
1594
1595 static PyObject *mrget_m(PyObject *me, void *hunoz)
1596   { return (mp_pywrap(MP_COPY(MPREDUCE_PY(me)->p))); }
1597
1598 static PyGetSetDef mpreduce_pygetset[] = {
1599 #define GETSETNAME(op, name) mr##op##_##name
1600   GET   (m,             "R.m -> modulus for reduction")
1601 #undef GETSETNAME
1602   { 0 }
1603 };
1604
1605 static PyMethodDef mpreduce_pymethods[] = {
1606 #define METHNAME(name) mrmeth_##name
1607   METH  (reduce,        "R.reduce(X) -> X mod B.m")
1608   METH  (exp,           "R.exp(X, N) -> X^N mod B.m")
1609 #undef METHNAME
1610   { 0 }
1611 };
1612
1613 static PyTypeObject *mpreduce_pytype, mpreduce_pytype_skel = {
1614   PyObject_HEAD_INIT(0) 0,              /* Header */
1615   "MPReduce",                           /* @tp_name@ */
1616   sizeof(mpreduce_pyobj),               /* @tp_basicsize@ */
1617   0,                                    /* @tp_itemsize@ */
1618
1619   mpreduce_pydealloc,                   /* @tp_dealloc@ */
1620   0,                                    /* @tp_print@ */
1621   0,                                    /* @tp_getattr@ */
1622   0,                                    /* @tp_setattr@ */
1623   0,                                    /* @tp_compare@ */
1624   0,                                    /* @tp_repr@ */
1625   0,                                    /* @tp_as_number@ */
1626   0,                                    /* @tp_as_sequence@ */
1627   0,                                    /* @tp_as_mapping@ */
1628   0,                                    /* @tp_hash@ */
1629   0,                                    /* @tp_call@ */
1630   0,                                    /* @tp_str@ */
1631   0,                                    /* @tp_getattro@ */
1632   0,                                    /* @tp_setattro@ */
1633   0,                                    /* @tp_as_buffer@ */
1634   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1635     Py_TPFLAGS_BASETYPE,
1636
1637   /* @tp_doc@ */
1638 "A reduction context for reduction modulo primes of special form.",
1639
1640   0,                                    /* @tp_traverse@ */
1641   0,                                    /* @tp_clear@ */
1642   0,                                    /* @tp_richcompare@ */
1643   0,                                    /* @tp_weaklistoffset@ */
1644   0,                                    /* @tp_iter@ */
1645   0,                                    /* @tp_iternext@ */
1646   mpreduce_pymethods,                   /* @tp_methods@ */
1647   0,                                    /* @tp_members@ */
1648   mpreduce_pygetset,                    /* @tp_getset@ */
1649   0,                                    /* @tp_base@ */
1650   0,                                    /* @tp_dict@ */
1651   0,                                    /* @tp_descr_get@ */
1652   0,                                    /* @tp_descr_set@ */
1653   0,                                    /* @tp_dictoffset@ */
1654   0,                                    /* @tp_init@ */
1655   PyType_GenericAlloc,                  /* @tp_alloc@ */
1656   mpreduce_pynew,                       /* @tp_new@ */
1657   0,                                    /* @tp_free@ */
1658   0                                     /* @tp_is_gc@ */
1659 };
1660
1661 /*----- Chinese Remainder Theorem solution --------------------------------*/
1662
1663 typedef struct mpcrt_pyobj {
1664   PyObject_HEAD
1665   mpcrt c;
1666 } mpcrt_pyobj;
1667
1668 #define MPCRT_PY(o) (&((mpcrt_pyobj *)(o))->c)
1669
1670 static PyObject *mcmeth_solve(PyObject *me, PyObject *arg)
1671 {
1672   mpcrt *c = MPCRT_PY(me);
1673   PyObject *q = 0, *x, *z = 0;
1674   mp *xx;
1675   mp **v = 0;
1676   int i = 0, n = c->k;
1677
1678   Py_INCREF(me);
1679   if (PyTuple_Size(arg) == n)
1680     q = arg;
1681   else if (!PyArg_ParseTuple(arg, "O:solve", &q))
1682     goto end;
1683   Py_INCREF(q);
1684   if (!PySequence_Check(q)) TYERR("want a sequence of residues");
1685   if (PySequence_Size(q) != n) VALERR("residue count mismatch");
1686   v = xmalloc(n * sizeof(*v));
1687   for (i = 0; i < n; i++) {
1688     if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1689     xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1690     v[i] = xx;
1691   }
1692   z = mp_pywrap(mpcrt_solve(c, MP_NEW, v));
1693 end:
1694   if (v) {
1695     n = i;
1696     for (i = 0; i < n; i++)
1697       MP_DROP(v[i]);
1698     xfree(v);
1699   }
1700   Py_DECREF(me);
1701   Py_XDECREF(q);
1702   return (z);
1703 }
1704
1705 static void mpcrt_pydealloc(PyObject *me)
1706 {
1707   mpcrt *c = MPCRT_PY(me);
1708   mpcrt_destroy(c);
1709   xfree(c->v);
1710 }
1711
1712 static PyObject *mpcrt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1713 {
1714   mpcrt_mod *v = 0;
1715   int n, i = 0;
1716   char *kwlist[] = { "mv", 0 };
1717   PyObject *q = 0, *x;
1718   mp *xx;
1719   mpcrt_pyobj *c = 0;
1720
1721   if (PyTuple_Size(arg) > 1)
1722     q = arg;
1723   else if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &q))
1724     goto end;
1725   Py_INCREF(q);
1726   if (!PySequence_Check(q)) TYERR("want a sequence of moduli");
1727   n = PySequence_Size(q);
1728   if (PyErr_Occurred()) goto end;
1729   if (!n) VALERR("want at least one modulus");
1730   v = xmalloc(n * sizeof(*v));
1731   for (i = 0; i < n; i++) {
1732     if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1733     xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1734     v[i].m = xx; v[i].n = 0; v[i].ni = 0; v[i].nni = 0;
1735   }
1736   c = (mpcrt_pyobj *)ty->tp_alloc(ty, 0);
1737   mpcrt_create(&c->c, v, n, 0);
1738   Py_DECREF(q);
1739   return ((PyObject *)c);
1740
1741 end:
1742   if (v) {
1743     n = i;
1744     for (i = 0; i < n; i++)
1745       MP_DROP(v[i].m);
1746     xfree(v);
1747   }
1748   Py_XDECREF(q);
1749   return (0);
1750 }
1751
1752 static PyObject *mcget_product(PyObject *me, void *hunoz)
1753   { return (mp_pywrap(MP_COPY(MPCRT_PY(me)->mb.m))); }
1754
1755 static PyObject *mcget_moduli(PyObject *me, void *hunoz)
1756 {
1757   int i;
1758   PyObject *q;
1759   mpcrt *c = MPCRT_PY(me);
1760
1761   if ((q = PyList_New(c->k)) == 0) return (0);
1762   for (i = 0; i < c->k; i++)
1763     PyList_SetItem(q, i, mp_pywrap(c->v[i].m));
1764   return (q);
1765 }
1766
1767 static PyGetSetDef mpcrt_pygetset[] = {
1768 #define GETSETNAME(op, name) mc##op##_##name
1769   GET   (product,       "C.product -> product of moduli")
1770   GET   (moduli,        "C.moduli -> list of individual moduli")
1771 #undef GETSETNAME
1772   { 0 }
1773 };
1774
1775 static PyMethodDef mpcrt_pymethods[] = {
1776 #define METHNAME(name) mcmeth_##name
1777   METH  (solve,         "C.solve([R0, R1]) -> X mod C.product")
1778 #undef METHNAME
1779   { 0 }
1780 };
1781
1782 static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = {
1783   PyObject_HEAD_INIT(0) 0,              /* Header */
1784   "MPCRT",                              /* @tp_name@ */
1785   sizeof(mpcrt_pyobj),                  /* @tp_basicsize@ */
1786   0,                                    /* @tp_itemsize@ */
1787
1788   mpcrt_pydealloc,                      /* @tp_dealloc@ */
1789   0,                                    /* @tp_print@ */
1790   0,                                    /* @tp_getattr@ */
1791   0,                                    /* @tp_setattr@ */
1792   0,                                    /* @tp_compare@ */
1793   0,                                    /* @tp_repr@ */
1794   0,                                    /* @tp_as_number@ */
1795   0,                                    /* @tp_as_sequence@ */
1796   0,                                    /* @tp_as_mapping@ */
1797   0,                                    /* @tp_hash@ */
1798   0,                                    /* @tp_call@ */
1799   0,                                    /* @tp_str@ */
1800   0,                                    /* @tp_getattro@ */
1801   0,                                    /* @tp_setattro@ */
1802   0,                                    /* @tp_as_buffer@ */
1803   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
1804     Py_TPFLAGS_BASETYPE,
1805
1806   /* @tp_doc@ */
1807 "A context for the solution of Chinese Remainder Theorem problems.",
1808
1809   0,                                    /* @tp_traverse@ */
1810   0,                                    /* @tp_clear@ */
1811   0,                                    /* @tp_richcompare@ */
1812   0,                                    /* @tp_weaklistoffset@ */
1813   0,                                    /* @tp_iter@ */
1814   0,                                    /* @tp_iternext@ */
1815   mpcrt_pymethods,                      /* @tp_methods@ */
1816   0,                                    /* @tp_members@ */
1817   mpcrt_pygetset,                       /* @tp_getset@ */
1818   0,                                    /* @tp_base@ */
1819   0,                                    /* @tp_dict@ */
1820   0,                                    /* @tp_descr_get@ */
1821   0,                                    /* @tp_descr_set@ */
1822   0,                                    /* @tp_dictoffset@ */
1823   0,                                    /* @tp_init@ */
1824   PyType_GenericAlloc,                  /* @tp_alloc@ */
1825   mpcrt_pynew,                          /* @tp_new@ */
1826   0,                                    /* @tp_free@ */
1827   0                                     /* @tp_is_gc@ */
1828 };
1829
1830 /*----- Binary polynomials ------------------------------------------------*/
1831
1832 static PyObject *gf_pyrepr(PyObject *o)
1833   { return mp_topystring(MP_X(o), 16, "GF(", "0x", "L)"); }
1834
1835 static PyObject *gf_pyrichcompare(PyObject *x, PyObject *y, int op)
1836 {
1837   mp *xx, *yy;
1838   int xl, yl;
1839   int b;
1840
1841   if (gfbinop(x, y, &xx, &yy)) RETURN_NOTIMPL;
1842   switch (op) {
1843     case Py_EQ: b = MP_EQ(xx, yy); break;
1844     case Py_NE: b = !MP_EQ(xx, yy); break;
1845     default:
1846       xl = mp_bits(xx);
1847       yl = mp_bits(yy);
1848       switch (op) {
1849         case Py_LT: b = xl < yl; break;
1850         case Py_LE: b = xl <= yl; break;
1851         case Py_GT: b = xl > yl; break;
1852         case Py_GE: b = xl >= yl; break;
1853         default: abort();
1854       }
1855       break;
1856   }
1857   MP_DROP(xx); MP_DROP(yy);
1858   return (getbool(b));
1859 }
1860
1861 static PyObject *gf_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1862 {
1863   PyObject *x;
1864   mp *z;
1865   mp_pyobj *zz = 0;
1866   int radix = 0;
1867   char *kwlist[] = { "x", "radix", 0 };
1868
1869   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:gf", kwlist, &x, &radix))
1870     goto end;
1871   if (GF_PYCHECK(x)) RETURN_OBJ(x);
1872   if (!good_radix_p(radix, 1)) VALERR("radix out of range");
1873   if ((z = mp_frompyobject(x, radix)) == 0) {
1874     PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
1875                  x->ob_type->tp_name);
1876     goto end;
1877   }
1878   if (MP_NEGP(z)) {
1879     MP_DROP(z);
1880     VALERR("gf cannot be negative");
1881   }
1882   zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
1883   zz->x = z;
1884 end:
1885   return ((PyObject *)zz);
1886 }
1887
1888 static long gf_pyhash(PyObject *me)
1889 {
1890   long i = mp_tolong(MP_X(me));
1891   i ^= 0xc7ecd67c; /* random perturbance */
1892   if (i == -1)
1893     i = -2;
1894   return (i);
1895 }
1896
1897 static PyObject *gf_pyexp(PyObject *x, PyObject *y, PyObject *z)
1898 {
1899   mp *xx = 0, *yy = 0, *zz = 0;
1900   mp *r = 0;
1901   PyObject *rc = 0;
1902
1903   if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 ||
1904       (z && z != Py_None && (zz = tomp(z)) == 0)) {
1905     mp_drop(xx); mp_drop(yy); mp_drop(zz);
1906     RETURN_NOTIMPL;
1907   }
1908   if (!z || z == Py_None) {
1909     if (MP_NEGP(yy)) VALERR("negative exponent");
1910     r = gf_exp(MP_NEW, xx, yy);
1911   } else {
1912     gfreduce gr;
1913     if (MP_ZEROP(zz)) ZDIVERR("zero modulus");
1914     if (MP_NEGP(yy)) {
1915       if ((xx = gf_modinv_checked(xx, xx, zz)) == 0) goto end;
1916       yy = mp_neg(yy, yy);
1917     }
1918     gfreduce_create(&gr, zz);
1919     r = gfreduce_exp(&gr, MP_NEW, xx, yy);
1920     gfreduce_destroy(&gr);
1921   }
1922   rc = gf_pywrap(r);
1923 end:
1924   mp_drop(xx); mp_drop(yy); mp_drop(zz);
1925   return (rc);
1926 }
1927
1928 static PyObject *gfmeth_sqr(PyObject *me, PyObject *arg)
1929 {
1930   if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
1931   return (gf_pywrap(gf_sqr(MP_NEW, MP_X(me))));
1932 }
1933
1934 static PyObject *gfmeth_gcd(PyObject *me, PyObject *arg)
1935 {
1936   PyObject *z = 0;
1937   mp *yy = 0, *zz = MP_NEW;
1938
1939   if (!PyArg_ParseTuple(arg, "O&:gcd", convgf, &yy)) goto end;
1940   gf_gcd(&zz, 0, 0, MP_X(me), yy);
1941   z = gf_pywrap(zz);
1942 end:
1943   if (yy) MP_DROP(yy);
1944   return (z);
1945 }
1946
1947 static PyObject *gfmeth_gcdx(PyObject *me, PyObject *arg)
1948 {
1949   PyObject *z = 0;
1950   mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
1951
1952   if (!PyArg_ParseTuple(arg, "O&:gcdx", convgf, &yy))
1953     goto end;
1954   gf_gcd(&zz, &uu, &vv, MP_X(me), yy);
1955   z = Py_BuildValue("(NNN)",
1956                     gf_pywrap(zz), gf_pywrap(uu), gf_pywrap(vv));
1957 end:
1958   if (yy) MP_DROP(yy);
1959   return (z);
1960 }
1961
1962 static PyObject *gfmeth_modinv(PyObject *me, PyObject *arg)
1963 {
1964   PyObject *z = 0;
1965   mp *yy = 0, *zz = MP_NEW;
1966
1967   if (!PyArg_ParseTuple(arg, "O&:modinv", convgf, &yy) ||
1968       (zz = gf_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
1969     goto end;
1970   z = gf_pywrap(zz);
1971 end:
1972   if (yy) MP_DROP(yy);
1973   return (z);
1974 }
1975
1976 static PyObject *gfmeth_irreduciblep(PyObject *me, PyObject *arg)
1977 {
1978   if (!PyArg_ParseTuple(arg, ":irreduciblep")) return (0);
1979   return getbool(gf_irreduciblep(MP_X(me)));
1980 }
1981
1982 static PyObject *gfget_degree(PyObject *me, void *hunoz)
1983   { return (PyInt_FromLong(mp_bits(MP_X(me)) - 1)); }
1984
1985 static PyGetSetDef gf_pygetset[] = {
1986 #define GETSETNAME(op, name) gf##op##_##name
1987   GET   (degree,        "X.degree -> polynomial degree of X")
1988 #undef GETSETNAME
1989 #define GETSETNAME(op, name) mp##op##_##name
1990   GET   (nbits,         "X.nbits -> bit length of X")
1991   GET   (noctets,       "X.noctets -> octet length of X")
1992 #undef GETSETNAME
1993   { 0 }
1994 };
1995
1996 static PyMethodDef gf_pymethods[] = {
1997 #define METHNAME(func) gfmeth_##func
1998   METH  (setbit,        "X.setbit(N) -> X with bit N set")
1999   METH  (clearbit,      "X.clearbit(N) -> X with bit N clear")
2000   METH  (testbit,       "X.testbit(N) -> true/false if bit N set/clear in X")
2001   METH  (sqr,           "X.sqr() -> X^2")
2002   METH  (gcd,           "X.gcd(Y) -> gcd(X, Y)")
2003   METH  (gcdx,
2004          "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
2005   METH  (modinv,        "X.modinv(Y) -> multiplicative inverse of Y mod X")
2006   METH  (irreduciblep,  "X.irreduciblep() -> true/false")
2007 #undef METHNAME
2008 #define METHNAME(func) mpmeth_##func
2009   KWMETH(tostring,      "X.tostring(radix = 10) -> STR")
2010   KWMETH(storel,        "X.storel(len = -1) -> little-endian bytes")
2011   KWMETH(storeb,        "X.storeb(len = -1) -> big-endian bytes")
2012   KWMETH(storel2c,
2013          "X.storel2c(len = -1) -> little-endian bytes, two's complement")
2014   KWMETH(storeb2c,
2015          "X.storeb2c(len = -1) -> big-endian bytes, two's complement")
2016   METH  (tobuf,         "X.tobuf() -> buffer format")
2017 #undef METHNAME
2018   { 0 }
2019 };
2020
2021 static PyNumberMethods gf_pynumber = {
2022   gf_pyadd,                             /* @nb_add@ */
2023   gf_pysub,                             /* @nb_subtract@ */
2024   gf_pymul,                             /* @nb_multiply@ */
2025   0,                                    /* @nb_divide@ */
2026   gf_pymod,                             /* @nb_remainder@ */
2027   gf_pydivmod,                          /* @nb_divmod@ */
2028   gf_pyexp,                             /* @nb_power@ */
2029   mp_pyid,                              /* @nb_negative@ */
2030   mp_pyid,                              /* @nb_positive@ */
2031   mp_pyid,                              /* @nb_absolute@ */
2032   mp_pynonzerop,                        /* @nb_nonzero@ */
2033   0 /* doesn't make any sense */,       /* @nb_invert@ */
2034   gf_pylsl,                             /* @nb_lshift@ */
2035   gf_pylsr,                             /* @nb_rshift@ */
2036   gf_pyand,                             /* @nb_and@ */
2037   gf_pyxor,                             /* @nb_xor@ */
2038   gf_pyor,                              /* @nb_or@ */
2039   gf_pycoerce,                          /* @nb_coerce@ */
2040   mp_pyint,                             /* @nb_int@ */
2041   mp_pylong,                            /* @nb_long@ */
2042   0 /* doesn't make any sense */,       /* @nb_float@ */
2043   mp_pyoct,                             /* @nb_oct@ */
2044   mp_pyhex,                             /* @nb_hex@ */
2045
2046   0,                                    /* @nb_inplace_add@ */
2047   0,                                    /* @nb_inplace_subtract@ */
2048   0,                                    /* @nb_inplace_multiply@ */
2049   0,                                    /* @nb_inplace_divide@ */
2050   0,                                    /* @nb_inplace_remainder@ */
2051   0,                                    /* @nb_inplace_power@ */
2052   0,                                    /* @nb_inplace_lshift@ */
2053   0,                                    /* @nb_inplace_rshift@ */
2054   0,                                    /* @nb_inplace_and@ */
2055   0,                                    /* @nb_inplace_xor@ */
2056   0,                                    /* @nb_inplace_or@ */
2057
2058   gf_pydiv,                             /* @nb_floor_divide@ */
2059   0,                                    /* @nb_true_divide@ */
2060   0,                                    /* @nb_inplace_floor_divide@ */
2061   0,                                    /* @nb_inplace_true_divide@ */
2062 };
2063
2064 static PyTypeObject gf_pytype_skel = {
2065   PyObject_HEAD_INIT(0) 0,              /* Header */
2066   "GF",                                 /* @tp_name@ */
2067   sizeof(mp_pyobj),                     /* @tp_basicsize@ */
2068   0,                                    /* @tp_itemsize@ */
2069
2070   mp_pydealloc,                         /* @tp_dealloc@ */
2071   0,                                    /* @tp_print@ */
2072   0,                                    /* @tp_getattr@ */
2073   0,                                    /* @tp_setattr@ */
2074   0,                                    /* @tp_compare@ */
2075   gf_pyrepr,                            /* @tp_repr@ */
2076   &gf_pynumber,                         /* @tp_as_number@ */
2077   0,                                    /* @tp_as_sequence@ */
2078   0,                                    /* @tp_as_mapping@ */
2079   gf_pyhash,                            /* @tp_hash@ */
2080   0,                                    /* @tp_call@ */
2081   mp_pyhex,                             /* @tp_str@ */
2082   0,                                    /* @tp_getattro@ */
2083   0,                                    /* @tp_setattro@ */
2084   0,                                    /* @tp_as_buffer@ */
2085   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
2086     Py_TPFLAGS_CHECKTYPES |
2087     Py_TPFLAGS_BASETYPE,
2088
2089   /* @tp_doc@ */
2090 "Binary polynomials.  Support almost all the standard arithmetic\n\
2091 operations.\n\
2092 \n\
2093 Constructor gf(X, radix = R) attempts to convert X to a `gf'.  If\n\
2094 X is a string, it's read in radix-R form, or we look for a prefix\n\
2095 if R = 0.  Other acceptable things are ints and longs.\n\
2096 \n\
2097 The name is hopelessly wrong from a technical point of view, but\n\
2098 but it's much easier to type than `p2' or `c2' or whatever.\n\
2099 \n\
2100 Notes:\n\
2101 \n\
2102   * Use `//' for division.  GFs don't have `/' division.",
2103
2104   0,                                    /* @tp_traverse@ */
2105   0,                                    /* @tp_clear@ */
2106   gf_pyrichcompare,                     /* @tp_richcompare@ */
2107   0,                                    /* @tp_weaklistoffset@ */
2108   0,                                    /* @tp_iter@ */
2109   0,                                    /* @tp_iternext@ */
2110   gf_pymethods,                         /* @tp_methods@ */
2111   0,                                    /* @tp_members@ */
2112   gf_pygetset,                          /* @tp_getset@ */
2113   0,                                    /* @tp_base@ */
2114   0,                                    /* @tp_dict@ */
2115   0,                                    /* @tp_descr_get@ */
2116   0,                                    /* @tp_descr_set@ */
2117   0,                                    /* @tp_dictoffset@ */
2118   0,                                    /* @tp_init@ */
2119   PyType_GenericAlloc,                  /* @tp_alloc@ */
2120   gf_pynew,                             /* @tp_new@ */
2121   0,                                    /* @tp_free@ */
2122   0                                     /* @tp_is_gc@ */
2123 };
2124
2125 static PyObject *meth__GF_fromstring(PyObject *me,
2126                                     PyObject *arg, PyObject *kw)
2127 {
2128   int r = 0;
2129   char *p;
2130   Py_ssize_t len;
2131   PyObject *z = 0;
2132   mp *zz;
2133   mptext_stringctx sc;
2134   char *kwlist[] = { "class", "x", "radix", 0 };
2135
2136   if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
2137                                    kwlist, &me, &p, &len, &r))
2138     goto end;
2139   if (!good_radix_p(r, 1)) VALERR("bad radix");
2140   sc.buf = p; sc.lim = p + len;
2141   if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0 ||
2142       MP_NEGP(zz)) {
2143     if (zz) MP_DROP(zz);
2144     VALERR("bad binary polynomial");
2145   }
2146   z = Py_BuildValue("(Ns#)", gf_pywrap(zz),
2147                     sc.buf, (Py_ssize_t)(sc.lim - sc.buf));
2148 end:
2149   return (z);
2150 }
2151
2152 /*----- Sparse poly reduction ---------------------------------------------*/
2153
2154 typedef struct gfreduce_pyobj {
2155   PyObject_HEAD
2156   gfreduce mr;
2157 } gfreduce_pyobj;
2158
2159 #define GFREDUCE_PY(o) (&((gfreduce_pyobj *)(o))->mr)
2160
2161 static PyObject *grmeth_exp(PyObject *me, PyObject *arg)
2162 {
2163   PyObject *rc = 0;
2164   mp *yy = 0, *zz = 0;
2165
2166   if (!PyArg_ParseTuple(arg, "O&O&:exp", convgf, &yy, convgf, &zz))
2167     goto end;
2168   if (MP_NEGP(zz)) {
2169     if ((yy = gf_modinv_checked(yy, yy, GFREDUCE_PY(me)->p)) == 0) goto end;
2170     zz = mp_neg(zz, zz);
2171   }
2172   rc = gf_pywrap(gfreduce_exp(GFREDUCE_PY(me), MP_NEW, yy, zz));
2173 end:
2174   if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
2175   return (rc);
2176 }
2177
2178 static PyObject *grmeth_trace(PyObject *me, PyObject *arg)
2179 {
2180   PyObject *rc = 0;
2181   mp *xx = 0;
2182
2183   if (!PyArg_ParseTuple(arg, "O&:trace", convgf, &xx)) goto end;
2184   rc = PyInt_FromLong(gfreduce_trace(GFREDUCE_PY(me), xx));
2185 end:
2186   if (xx) MP_DROP(xx);
2187   return (rc);
2188 }
2189
2190 static PyObject *grmeth_halftrace(PyObject *me, PyObject *arg)
2191 {
2192   PyObject *rc = 0;
2193   mp *xx = 0;
2194
2195   if (!PyArg_ParseTuple(arg, "O&:halftrace", convgf, &xx)) goto end;
2196   rc = gf_pywrap(gfreduce_halftrace(GFREDUCE_PY(me), MP_NEW, xx));
2197 end:
2198   if (xx) MP_DROP(xx);
2199   return (rc);
2200 }
2201
2202 static PyObject *grmeth_sqrt(PyObject *me, PyObject *arg)
2203 {
2204   PyObject *rc = 0;
2205   mp *xx = 0, *yy;
2206
2207   if (!PyArg_ParseTuple(arg, "O&:sqrt", convgf, &xx)) goto end;
2208   if ((yy = gfreduce_sqrt(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
2209     VALERR("no modular square root");
2210   rc = gf_pywrap(yy);
2211 end:
2212   if (xx) MP_DROP(xx);
2213   return (rc);
2214 }
2215
2216 static PyObject *grmeth_quadsolve(PyObject *me, PyObject *arg)
2217 {
2218   PyObject *rc = 0;
2219   mp *xx = 0, *yy;
2220
2221   if (!PyArg_ParseTuple(arg, "O&:quadsolve", convgf, &xx)) goto end;
2222   if ((yy = gfreduce_quadsolve(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
2223     VALERR("no solution found");
2224   rc = gf_pywrap(yy);
2225 end:
2226   if (xx) MP_DROP(xx);
2227   return (rc);
2228 }
2229
2230 static PyObject *grmeth_reduce(PyObject *me, PyObject *arg)
2231 {
2232   PyObject *z = 0;
2233   mp *yy = 0;
2234
2235   if (!PyArg_ParseTuple(arg, "O&:reduce", convgf, &yy)) goto end;
2236   z = gf_pywrap(gfreduce_do(GFREDUCE_PY(me), MP_NEW, yy));
2237 end:
2238   return (z);
2239 }
2240
2241 static void gfreduce_pydealloc(PyObject *me)
2242 {
2243   gfreduce_destroy(GFREDUCE_PY(me));
2244   FREEOBJ(me);
2245 }
2246
2247 static PyObject *gfreduce_pynew(PyTypeObject *ty,
2248                                  PyObject *arg, PyObject *kw)
2249 {
2250   gfreduce_pyobj *mr = 0;
2251   gfreduce r;
2252   char *kwlist[] = { "m", 0 };
2253   mp *xx = 0;
2254
2255   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convgf, &xx))
2256     goto end;
2257   if (MP_ZEROP(xx)) ZDIVERR("modulus is zero!");
2258   gfreduce_create(&r, xx);
2259   mr = (gfreduce_pyobj *)ty->tp_alloc(ty, 0);
2260   mr->mr = r;
2261 end:
2262   if (xx) MP_DROP(xx);
2263   return ((PyObject *)mr);
2264 }
2265
2266 static PyObject *grget_m(PyObject *me, void *hunoz)
2267   { return (gf_pywrap(MP_COPY(GFREDUCE_PY(me)->p))); }
2268
2269 static PyGetSetDef gfreduce_pygetset[] = {
2270 #define GETSETNAME(op, name) gr##op##_##name
2271   GET   (m,             "R.m -> reduction polynomial")
2272 #undef GETSETNAME
2273   { 0 }
2274 };
2275
2276 static PyMethodDef gfreduce_pymethods[] = {
2277 #define METHNAME(name) grmeth_##name
2278   METH  (reduce,        "R.reduce(X) -> X mod B.m")
2279   METH  (trace,        "R.trace(X) -> Tr(X) = x + x^2 + ... + x^{2^{m - 1}}")
2280   METH  (halftrace,   "R.halftrace(X) -> x + x^{2^2} + ... + x^{2^{m - 1}}")
2281   METH  (sqrt,          "R.sqrt(X) -> Y where Y^2 = X mod R")
2282   METH  (quadsolve,     "R.quadsolve(X) -> Y where Y^2 + Y = X mod R")
2283   METH  (exp,           "R.exp(X, N) -> X^N mod B.m")
2284 #undef METHNAME
2285   { 0 }
2286 };
2287
2288 static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = {
2289   PyObject_HEAD_INIT(0) 0,              /* Header */
2290   "GFReduce",                           /* @tp_name@ */
2291   sizeof(gfreduce_pyobj),               /* @tp_basicsize@ */
2292   0,                                    /* @tp_itemsize@ */
2293
2294   gfreduce_pydealloc,                   /* @tp_dealloc@ */
2295   0,                                    /* @tp_print@ */
2296   0,                                    /* @tp_getattr@ */
2297   0,                                    /* @tp_setattr@ */
2298   0,                                    /* @tp_compare@ */
2299   0,                                    /* @tp_repr@ */
2300   0,                                    /* @tp_as_number@ */
2301   0,                                    /* @tp_as_sequence@ */
2302   0,                                    /* @tp_as_mapping@ */
2303   0,                                    /* @tp_hash@ */
2304   0,                                    /* @tp_call@ */
2305   0,                                    /* @tp_str@ */
2306   0,                                    /* @tp_getattro@ */
2307   0,                                    /* @tp_setattro@ */
2308   0,                                    /* @tp_as_buffer@ */
2309   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
2310     Py_TPFLAGS_BASETYPE,
2311
2312   /* @tp_doc@ */
2313 "A reduction context for reduction modulo sparse irreducible polynomials.",
2314
2315   0,                                    /* @tp_traverse@ */
2316   0,                                    /* @tp_clear@ */
2317   0,                                    /* @tp_richcompare@ */
2318   0,                                    /* @tp_weaklistoffset@ */
2319   0,                                    /* @tp_iter@ */
2320   0,                                    /* @tp_iternext@ */
2321   gfreduce_pymethods,                   /* @tp_methods@ */
2322   0,                                    /* @tp_members@ */
2323   gfreduce_pygetset,                    /* @tp_getset@ */
2324   0,                                    /* @tp_base@ */
2325   0,                                    /* @tp_dict@ */
2326   0,                                    /* @tp_descr_get@ */
2327   0,                                    /* @tp_descr_set@ */
2328   0,                                    /* @tp_dictoffset@ */
2329   0,                                    /* @tp_init@ */
2330   PyType_GenericAlloc,                  /* @tp_alloc@ */
2331   gfreduce_pynew,                       /* @tp_new@ */
2332   0,                                    /* @tp_free@ */
2333   0                                     /* @tp_is_gc@ */
2334 };
2335
2336 /*----- Normal/poly transformation ----------------------------------------*/
2337
2338 typedef struct gfn_pyobj {
2339   PyObject_HEAD
2340   mp *p;
2341   gfn ntop, pton;
2342 } gfn_pyobj;
2343
2344 static PyTypeObject *gfn_pytype, gfn_pytype_skel;
2345
2346 #define GFN_P(o) (((gfn_pyobj *)(o))->p)
2347 #define GFN_PTON(o) (&((gfn_pyobj *)(o))->pton)
2348 #define GFN_NTOP(o) (&((gfn_pyobj *)(o))->ntop)
2349
2350 static PyObject *gfn_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
2351 {
2352   mp *p = 0, *beta = 0;
2353   gfn_pyobj *gg = 0;
2354   char *kwlist[] = { "p", "beta", 0 };
2355
2356   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", kwlist,
2357                                    convgf, &p, convgf, &beta))
2358     goto end;
2359   gg = PyObject_New(gfn_pyobj, ty);
2360   if (gfn_create(p, beta, &gg->ntop, &gg->pton)) {
2361     FREEOBJ(gg);
2362     gg = 0;
2363     VALERR("can't invert transformation matrix");
2364   }
2365   gg->p = MP_COPY(p);
2366 end:
2367   mp_drop(p);
2368   mp_drop(beta);
2369   return ((PyObject *)gg);
2370 }
2371
2372 static PyObject *gfnget_p(PyObject *me, void *hunoz)
2373   { return (gf_pywrap(MP_COPY(GFN_P(me)))); }
2374
2375 static PyObject *gfnget_beta(PyObject *me, void *hunoz)
2376 {
2377   gfn *n = GFN_NTOP(me);
2378   mp *x = n->r[n->n - 1];
2379   return (gf_pywrap(MP_COPY(x)));
2380 }
2381
2382 #define XFORMOP(name, NAME)                                             \
2383   static PyObject *gfnmeth_##name(PyObject *me, PyObject *arg)          \
2384   {                                                                     \
2385     mp *xx = 0;                                                         \
2386     mp *z = 0;                                                          \
2387                                                                         \
2388     if (!PyArg_ParseTuple(arg, "O&:" #name, convgf, &xx)) goto end;     \
2389     z = gfn_transform(GFN_##NAME(me), MP_NEW, xx);                      \
2390   end:                                                                  \
2391     mp_drop(xx);                                                        \
2392     if (!z) return (0);                                                 \
2393     return (mp_pywrap(z));                                              \
2394   }
2395 XFORMOP(pton, PTON)
2396 XFORMOP(ntop, NTOP)
2397 #undef XFORMOP
2398
2399 static void gfn_pydealloc(PyObject *me)
2400 {
2401   gfn_destroy(GFN_PTON(me));
2402   gfn_destroy(GFN_NTOP(me));
2403   FREEOBJ(me);
2404 }
2405
2406 static PyGetSetDef gfn_pygetset[] = {
2407 #define GETSETNAME(op, name) gfn##op##_##name
2408   GET   (p,             "X.p -> polynomial basis, as polynomial")
2409   GET   (beta,          "X.beta -> normal basis element, in poly form")
2410 #undef GETSETNAME
2411   { 0 }
2412 };
2413
2414 static PyMethodDef gfn_pymethods[] = {
2415 #define METHNAME(name) gfnmeth_##name
2416   METH  (pton,          "X.pton(A) -> normal-basis representation of A")
2417   METH  (ntop,          "X.ntop(A) -> polynomial-basis representation of A")
2418 #undef METHNAME
2419   { 0 }
2420 };
2421
2422 static PyTypeObject gfn_pytype_skel = {
2423   PyObject_HEAD_INIT(0) 0,              /* Header */
2424   "GFN",                                /* @tp_name@ */
2425   sizeof(gfn_pyobj),                    /* @tp_basicsize@ */
2426   0,                                    /* @tp_itemsize@ */
2427
2428   gfn_pydealloc,                        /* @tp_dealloc@ */
2429   0,                                    /* @tp_print@ */
2430   0,                                    /* @tp_getattr@ */
2431   0,                                    /* @tp_setattr@ */
2432   0,                                    /* @tp_compare@ */
2433   0,                                    /* @tp_repr@ */
2434   0,                                    /* @tp_as_number@ */
2435   0,                                    /* @tp_as_sequence@ */
2436   0,                                    /* @tp_as_mapping@ */
2437   0,                                    /* @tp_hash@ */
2438   0,                                    /* @tp_call@ */
2439   0,                                    /* @tp_str@ */
2440   0,                                    /* @tp_getattro@ */
2441   0,                                    /* @tp_setattro@ */
2442   0,                                    /* @tp_as_buffer@ */
2443   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
2444     Py_TPFLAGS_BASETYPE,
2445
2446   /* @tp_doc@ */
2447 "An object for transforming elements of binary fields between polynomial\n\
2448 and normal basis representations.",
2449
2450   0,                                    /* @tp_traverse@ */
2451   0,                                    /* @tp_clear@ */
2452   0,                                    /* @tp_richcompare@ */
2453   0,                                    /* @tp_weaklistoffset@ */
2454   0,                                    /* @tp_iter@ */
2455   0,                                    /* @tp_iternext@ */
2456   gfn_pymethods,                        /* @tp_methods@ */
2457   0,                                    /* @tp_members@ */
2458   gfn_pygetset,                         /* @tp_getset@ */
2459   0,                                    /* @tp_base@ */
2460   0,                                    /* @tp_dict@ */
2461   0,                                    /* @tp_descr_get@ */
2462   0,                                    /* @tp_descr_set@ */
2463   0,                                    /* @tp_dictoffset@ */
2464   0,                                    /* @tp_init@ */
2465   PyType_GenericAlloc,                  /* @tp_alloc@ */
2466   gfn_pynew,                            /* @tp_new@ */
2467   0,                                    /* @tp_free@ */
2468   0                                     /* @tp_is_gc@ */
2469 };
2470
2471 /*----- Glue --------------------------------------------------------------*/
2472
2473 static PyMethodDef methods[] = {
2474 #define METHNAME(func) meth_##func
2475   KWMETH(_MP_fromstring,        "\
2476 fromstring(STR, radix = 0) -> (X, REST)\n\
2477 \n\
2478 Parse STR as a large integer, according to radix.  If radix is zero,\n\
2479 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2480 or `R_' for other radix R.")
2481   KWMETH(_GF_fromstring,        "\
2482 fromstring(STR, radix = 0) -> (X, REST)\n\
2483 \n\
2484 Parse STR as a binary polynomial, according to radix.  If radix is zero,\n\
2485 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2486 or `R_' for other radix R.")
2487   METH  (_MP_factorial,         "\
2488 factorial(I) -> I!: compute factorial")
2489   METH  (_MP_fibonacci,         "\
2490 fibonacci(I) -> F(I): compute Fibonacci number")
2491   METH  (_MP_loadl,             "\
2492 loadl(STR) -> X: read little-endian bytes")
2493   METH  (_MP_loadb,             "\
2494 loadb(STR) -> X: read big-endian bytes")
2495   METH  (_MP_loadl2c,           "\
2496 loadl2c(STR) -> X: read little-endian bytes, two's complement")
2497   METH  (_MP_loadb2c,           "\
2498 loadb2c(STR) -> X: read big-endian bytes, two's complement")
2499   METH  (_MP_frombuf,           "\
2500 frombuf(STR) -> (X, REST): read buffer format")
2501   METH  (_GF_loadl,             "\
2502 loadl(STR) -> X: read little-endian bytes")
2503   METH  (_GF_loadb,             "\
2504 loadb(STR) -> X: read big-endian bytes")
2505   METH  (_GF_frombuf,           "\
2506 frombuf(STR) -> (X, REST): read buffer format")
2507 #undef METHNAME
2508   { 0 }
2509 };
2510
2511 void mp_pyinit(void)
2512 {
2513   INITTYPE(mp, root);
2514   INITTYPE(gf, root);
2515   INITTYPE(mpmul, root);
2516   INITTYPE(mpmont, root);
2517   INITTYPE(mpbarrett, root);
2518   INITTYPE(mpreduce, root);
2519   INITTYPE(mpcrt, root);
2520   INITTYPE(gfreduce, root);
2521   INITTYPE(gfn, root);
2522   addmethods(methods);
2523 }
2524
2525 void mp_pyinsert(PyObject *mod)
2526 {
2527   INSERT("MP", mp_pytype);
2528   INSERT("MPMul", mpmul_pytype);
2529   INSERT("MPMont", mpmont_pytype);
2530   INSERT("MPBarrett", mpbarrett_pytype);
2531   INSERT("MPReduce", mpreduce_pytype);
2532   INSERT("MPCRT", mpcrt_pytype);
2533   INSERT("GF", gf_pytype);
2534   INSERT("GFReduce", gfreduce_pytype);
2535   INSERT("GFN", gfn_pytype);
2536 }
2537
2538 /*----- That's all, folks -------------------------------------------------*/