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