~mdw / catacomb-python / blob
? search:


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