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