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