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