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