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