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