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