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

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