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