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