~mdw / catacomb-python / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
rand.c: Add missing return-value mnemonic in docstring.
[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 long mphash(mp *x)
548 {
549 PyObject *l = mp_topylong(x);
550 long h = PyObject_Hash(l);
551 Py_DECREF(l); return (h);
552 }
553
554 static long mp_pyhash(PyObject *me) { return (mphash(MP_X(me))); }
555
556 static PyObject *mpmeth_jacobi(PyObject *me, PyObject *arg)
557 {
558 mp *y = 0;
559 PyObject *z = 0;
560
561 if (!PyArg_ParseTuple(arg, "O&:jacobi", convmp, &y)) goto end;
562 z = PyInt_FromLong(mp_jacobi(y, MP_X(me)));
563 end:
564 if (y) MP_DROP(y);
565 return (z);
566 }
567
568 #define BITOP(pre, name, c) \
569 static PyObject *pre##meth_##name(PyObject *me, PyObject *arg) \
570 { \
571 unsigned long i; \
572 if (!PyArg_ParseTuple(arg, "O&:" #name, convulong, &i)) return (0); \
573 return (pre##_pywrap(mp_##name##c(MP_NEW, MP_X(me), i))); \
574 }
575 BITOP(mp, setbit, 2c);
576 BITOP(mp, clearbit, 2c);
577 BITOP(gf, setbit, );
578 BITOP(gf, clearbit, );
579 #undef BITOP
580
581 static PyObject *mpmeth_testbit(PyObject *me, PyObject *arg)
582 {
583 unsigned long i;
584 if (!PyArg_ParseTuple(arg, "O&:testbit", convulong, &i)) return (0);
585 return (getbool(mp_testbit2c(MP_X(me), i)));
586 }
587
588 static PyObject *gfmeth_testbit(PyObject *me, PyObject *arg)
589 {
590 unsigned long i;
591 if (!PyArg_ParseTuple(arg, "O&:testbit", convulong, &i)) return (0);
592 return (getbool(mp_testbit(MP_X(me), i)));
593 }
594
595 static PyObject *mpmeth_odd(PyObject *me, PyObject *arg)
596 {
597 mp *t;
598 size_t s;
599
600 if (!PyArg_ParseTuple(arg, ":odd")) return (0);
601 t = mp_odd(MP_NEW, MP_X(me), &s);
602 return (Py_BuildValue("(lN)", (long)s, mp_pywrap(t)));
603 }
604
605 static PyObject *mpmeth_sqr(PyObject *me, PyObject *arg)
606 {
607 if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
608 return (mp_pywrap(mp_sqr(MP_NEW, MP_X(me))));
609 }
610
611 static PyObject *mpmeth_sqrt(PyObject *me, PyObject *arg)
612 {
613 if (!PyArg_ParseTuple(arg, ":sqrt")) return (0);
614 if (MP_NEGP(MP_X(me))) VALERR("negative root");
615 return (mp_pywrap(mp_sqrt(MP_NEW, MP_X(me))));
616 end:
617 return (0);
618 }
619
620 static PyObject *mpmeth_gcd(PyObject *me, PyObject *arg)
621 {
622 mp *y = 0, *zz = MP_NEW;
623 PyObject *z = 0;
624
625 if (!PyArg_ParseTuple(arg, "O&:gcd", convmp, &y)) goto end;
626 mp_gcd(&zz, 0, 0, MP_X(me), y);
627 z = mp_pywrap(zz);
628 end:
629 if (y) MP_DROP(y);
630 return (z);
631 }
632
633 static PyObject *mpmeth_gcdx(PyObject *me, PyObject *arg)
634 {
635 PyObject *z = 0;
636 mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
637
638 if (!PyArg_ParseTuple(arg, "O&:gcdx", convmp, &yy)) goto end;
639 mp_gcd(&zz, &uu, &vv, MP_X(me), yy);
640 z = Py_BuildValue("(NNN)",
641 mp_pywrap(zz), mp_pywrap(uu), mp_pywrap(vv));
642 end:
643 if (yy) MP_DROP(yy);
644 return (z);
645 }
646
647 static PyObject *mpmeth_modinv(PyObject *me, PyObject *arg)
648 {
649 PyObject *z = 0;
650 mp *yy = 0, *zz = MP_NEW;
651
652 if (!PyArg_ParseTuple(arg, "O&:modinv", convmp, &yy) ||
653 (zz = mp_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
654 goto end;
655 z = mp_pywrap(zz);
656 end:
657 if (yy) MP_DROP(yy);
658 return (z);
659 }
660
661 static PyObject *mpmeth_tostring(PyObject *me, PyObject *arg, PyObject *kw)
662 {
663 int radix = 10;
664 char *kwlist[] = { "radix", 0 };
665 if (!PyArg_ParseTupleAndKeywords(arg, kw, "|i:tostring", kwlist, &radix))
666 goto end;
667 if (!good_radix_p(radix, 0)) VALERR("bad radix");
668 return (mp_topystring(MP_X(me), radix, 0, 0, 0));
669 end:
670 return (0);
671 }
672
673 static PyObject *mpmeth_modsqrt(PyObject *me, PyObject *arg)
674 {
675 PyObject *z = 0;
676 mp *yy = 0, *zz = MP_NEW;
677
678 if (!PyArg_ParseTuple(arg, "O&:modsqrt", convmp, &yy)) goto end;
679 if ((zz = mp_modsqrt(MP_NEW, yy, MP_X(me))) == 0)
680 VALERR("no modular square root");
681 z = mp_pywrap(zz);
682 end:
683 if (yy) MP_DROP(yy);
684 return (z);
685 }
686
687 static PyObject *mpmeth_leastcongruent(PyObject *me, PyObject *arg)
688 {
689 mp *z, *b, *m;
690 PyObject *rc = 0;
691
692 if (!PyArg_ParseTuple(arg, "O&O&:leastcongruent", convmp, &b, convmp, &m))
693 goto end;
694 z = mp_leastcongruent(MP_NEW, b, MP_X(me), m);
695 rc = mp_pywrap(z);
696 end:
697 return (rc);
698 }
699
700 #define STOREOP(name, c) \
701 static PyObject *mpmeth_##name(PyObject *me, \
702 PyObject *arg, PyObject *kw) \
703 { \
704 long len = -1; \
705 char *kwlist[] = { "len", 0 }; \
706 PyObject *rc = 0; \
707 \
708 if (!PyArg_ParseTupleAndKeywords(arg, kw, "|l:" #name, \
709 kwlist, &len)) \
710 goto end; \
711 if (len < 0) { \
712 len = mp_octets##c(MP_X(me)); \
713 if (!len) len = 1; \
714 } \
715 rc = bytestring_pywrap(0, len); \
716 mp_##name(MP_X(me), PyString_AS_STRING(rc), len); \
717 end: \
718 return (rc); \
719 }
720 STOREOP(storel, )
721 STOREOP(storeb, )
722 STOREOP(storel2c, 2c)
723 STOREOP(storeb2c, 2c)
724 #undef STOREOP
725
726 #define BUFOP(ty, pyty) \
727 static PyObject *meth__##pyty##_frombuf(PyObject *me, PyObject *arg) \
728 { \
729 buf b; \
730 char *p; \
731 Py_ssize_t sz; \
732 PyObject *rc = 0; \
733 mp *x; \
734 \
735 if (!PyArg_ParseTuple(arg, "Os#:frombuf", &me, &p, &sz)) goto end; \
736 buf_init(&b, p, sz); \
737 if ((x = buf_getmp(&b)) == 0) VALERR("malformed data"); \
738 rc = Py_BuildValue("(NN)", ty##_pywrap(x), \
739 bytestring_pywrapbuf(&b)); \
740 end: \
741 return (rc); \
742 }
743 BUFOP(mp, MP)
744 BUFOP(gf, GF)
745 #undef BUFOP
746
747 static PyObject *mpmeth_tobuf(PyObject *me, PyObject *arg)
748 {
749 buf b;
750 PyObject *rc;
751 mp *x;
752 size_t n;
753
754 if (!PyArg_ParseTuple(arg, ":tobuf")) return (0);
755 x = MP_X(me);
756 n = mp_octets(x) + 3;
757 rc = bytestring_pywrap(0, n);
758 buf_init(&b, PyString_AS_STRING(rc), n);
759 buf_putmp(&b, x);
760 assert(BOK(&b));
761 _PyString_Resize(&rc, BLEN(&b));
762 return (rc);
763 }
764
765 static PyObject *mpmeth_primep(PyObject *me, PyObject *arg, PyObject *kw)
766 {
767 grand *r = &rand_global;
768 char *kwlist[] = { "rng", 0 };
769 PyObject *rc = 0;
770
771 if (!PyArg_ParseTupleAndKeywords(arg, kw, "|O&", kwlist, convgrand, &r))
772 goto end;
773 rc = getbool(pgen_primep(MP_X(me), r));
774 end:
775 return (rc);
776 }
777
778 static PyObject *mpget_nbits(PyObject *me, void *hunoz)
779 { return (PyInt_FromLong(mp_bits(MP_X(me)))); }
780
781 static PyObject *mpget_noctets(PyObject *me, void *hunoz)
782 { return (PyInt_FromLong(mp_octets(MP_X(me)))); }
783
784 static PyObject *mpget_noctets2c(PyObject *me, void *hunoz)
785 { return (PyInt_FromLong(mp_octets2c(MP_X(me)))); }
786
787 static PyGetSetDef mp_pygetset[] = {
788 #define GETSETNAME(op, func) mp##op##_##func
789 GET (nbits, "X.nbits -> bit length of X")
790 GET (noctets, "X.noctets -> octet length of X")
791 GET (noctets2c, "X.noctets2c -> two's complement octet length of X")
792 #undef GETSETNAME
793 { 0 }
794 };
795
796 static PyMethodDef mp_pymethods[] = {
797 #define METHNAME(func) mpmeth_##func
798 METH (jacobi, "X.jacobi(Y) -> Jacobi symbol (Y|X) (NB inversion!)")
799 METH (setbit, "X.setbit(N) -> X with bit N set")
800 METH (clearbit, "X.clearbit(N) -> X with bit N clear")
801 METH (testbit, "X.testbit(N) -> true/false if bit N set/clear in X")
802 METH (odd, "X.odd() -> S, T where X = 2^S T with T odd")
803 METH (sqr, "X.sqr() -> X^2")
804 METH (sqrt, "X.sqrt() -> largest integer <= sqrt(X)")
805 METH (gcd, "X.gcd(Y) -> gcd(X, Y)")
806 METH (gcdx,
807 "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
808 METH (modinv, "X.modinv(Y) -> multiplicative inverse of Y mod X")
809 METH (modsqrt, "X.modsqrt(Y) -> square root of Y mod X, if X prime")
810 METH (leastcongruent,
811 "X.leastcongruent(B, M) -> smallest Z >= B with Z == X (mod M)")
812 KWMETH(primep, "X.primep([rng = rand]) -> true/false if X is prime")
813 KWMETH(tostring, "X.tostring([radix = 10]) -> STR")
814 KWMETH(storel, "X.storel([len = -1]) -> little-endian bytes")
815 KWMETH(storeb, "X.storeb([len = -1]) -> big-endian bytes")
816 KWMETH(storel2c,
817 "X.storel2c([len = -1]) -> little-endian bytes, two's complement")
818 KWMETH(storeb2c,
819 "X.storeb2c([len = -1]) -> big-endian bytes, two's complement")
820 METH (tobuf, "X.tobuf() -> buffer format")
821 #undef METHNAME
822 { 0 }
823 };
824
825 static PyNumberMethods mp_pynumber = {
826 mp_pyadd, /* @nb_add@ */
827 mp_pysub, /* @nb_subtract@ */
828 mp_pymul, /* @nb_multiply@ */
829 0, /* @nb_divide@ */
830 mp_pymod, /* @nb_remainder@ */
831 mp_pydivmod, /* @nb_divmod@ */
832 mp_pyexp, /* @nb_power@ */
833 mp_pyneg, /* @nb_negative@ */
834 mp_pyid, /* @nb_positive@ */
835 mp_pyabs, /* @nb_absolute@ */
836 mp_pynonzerop, /* @nb_nonzero@ */
837 mp_pynot2c, /* @nb_invert@ */
838 mp_pylsl2c, /* @nb_lshift@ */
839 mp_pylsr2c, /* @nb_rshift@ */
840 mp_pyand2c, /* @nb_and@ */
841 mp_pyxor2c, /* @nb_xor@ */
842 mp_pyor2c, /* @nb_or@ */
843 mp_pycoerce, /* @nb_coerce@ */
844 mp_pyint, /* @nb_int@ */
845 mp_pylong, /* @nb_long@ */
846 mp_pyfloat, /* @nb_float@ */
847 mp_pyoct, /* @nb_oct@ */
848 mp_pyhex, /* @nb_hex@ */
849
850 0, /* @nb_inplace_add@ */
851 0, /* @nb_inplace_subtract@ */
852 0, /* @nb_inplace_multiply@ */
853 0, /* @nb_inplace_divide@ */
854 0, /* @nb_inplace_remainder@ */
855 0, /* @nb_inplace_power@ */
856 0, /* @nb_inplace_lshift@ */
857 0, /* @nb_inplace_rshift@ */
858 0, /* @nb_inplace_and@ */
859 0, /* @nb_inplace_xor@ */
860 0, /* @nb_inplace_or@ */
861
862 mp_pydiv, /* @nb_floor_divide@ */
863 0, /* @nb_true_divide@ */
864 0, /* @nb_inplace_floor_divide@ */
865 0, /* @nb_inplace_true_divide@ */
866 };
867
868 static PyTypeObject mp_pytype_skel = {
869 PyObject_HEAD_INIT(0) 0, /* Header */
870 "MP", /* @tp_name@ */
871 sizeof(mp_pyobj), /* @tp_basicsize@ */
872 0, /* @tp_itemsize@ */
873
874 mp_pydealloc, /* @tp_dealloc@ */
875 0, /* @tp_print@ */
876 0, /* @tp_getattr@ */
877 0, /* @tp_setattr@ */
878 mp_pycompare, /* @tp_compare@ */
879 mp_pyrepr, /* @tp_repr@ */
880 &mp_pynumber, /* @tp_as_number@ */
881 0, /* @tp_as_sequence@ */
882 0, /* @tp_as_mapping@ */
883 mp_pyhash, /* @tp_hash@ */
884 0, /* @tp_call@ */
885 mp_pystr, /* @tp_str@ */
886 0, /* @tp_getattro@ */
887 0, /* @tp_setattro@ */
888 0, /* @tp_as_buffer@ */
889 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
890 Py_TPFLAGS_CHECKTYPES |
891 Py_TPFLAGS_BASETYPE,
892
893 /* @tp_doc@ */
894 "Multiprecision integers, similar to `long' but more efficient and\n\
895 versatile. Support all the standard arithmetic operations, with\n\
896 implicit conversions from `PrimeFilter', and other objects which\n\
897 convert to `long'.\n\
898 \n\
899 Constructor MP(X, [radix = R]) attempts to convert X to an `MP'. If\n\
900 X is a string, it's read in radix-R form, or we look for a prefix\n\
901 if R = 0. Other acceptable things are field elements, elliptic curve\n\
902 points, group elements, Python `int' and `long' objects, and anything\n\
903 with an integer conversion.\n\
904 \n\
905 Notes:\n\
906 \n\
907 * Use `//' for division. MPs don't have `/' division.",
908
909 0, /* @tp_traverse@ */
910 0, /* @tp_clear@ */
911 0, /* @tp_richcompare@ */
912 0, /* @tp_weaklistoffset@ */
913 0, /* @tp_iter@ */
914 0, /* @tp_iternext@ */
915 mp_pymethods, /* @tp_methods@ */
916 0, /* @tp_members@ */
917 mp_pygetset, /* @tp_getset@ */
918 0, /* @tp_base@ */
919 0, /* @tp_dict@ */
920 0, /* @tp_descr_get@ */
921 0, /* @tp_descr_set@ */
922 0, /* @tp_dictoffset@ */
923 0, /* @tp_init@ */
924 PyType_GenericAlloc, /* @tp_alloc@ */
925 mp_pynew, /* @tp_new@ */
926 0, /* @tp_free@ */
927 0 /* @tp_is_gc@ */
928 };
929
930 static PyObject *meth__MP_fromstring(PyObject *me,
931 PyObject *arg, PyObject *kw)
932 {
933 int r = 0;
934 char *p;
935 Py_ssize_t len;
936 PyObject *z = 0;
937 mp *zz;
938 mptext_stringctx sc;
939 char *kwlist[] = { "class", "x", "radix", 0 };
940
941 if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
942 kwlist, &me, &p, &len, &r))
943 goto end;
944 if (!good_radix_p(r, 1)) VALERR("bad radix");
945 sc.buf = p; sc.lim = p + len;
946 if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0)
947 VALERR("bad integer");
948 z = Py_BuildValue("(Ns#)", mp_pywrap(zz),
949 sc.buf, (Py_ssize_t)(sc.lim - sc.buf));
950 end:
951 return (z);
952 }
953
954 static PyObject *meth__MP_factorial(PyObject *me, PyObject *arg)
955 {
956 unsigned long i;
957 mp *x;
958 if (!PyArg_ParseTuple(arg, "OO&:factorial", &me, convulong, &i))
959 return (0);
960 x = mp_factorial(i);
961 return mp_pywrap(x);
962 }
963
964 static PyObject *meth__MP_fibonacci(PyObject *me, PyObject *arg)
965 {
966 long i;
967 mp *x;
968 if (!PyArg_ParseTuple(arg, "Ol:fibonacci", &me, &i)) return (0);
969 x = mp_fibonacci(i);
970 return mp_pywrap(x);
971 }
972
973 #define LOADOP(pre, py, name) \
974 static PyObject *meth__##py##_##name(PyObject *me, PyObject *arg) \
975 { \
976 char *p; \
977 Py_ssize_t len; \
978 if (!PyArg_ParseTuple(arg, "Os#:" #name, &me, &p, &len)) return (0); \
979 return (pre##_pywrap(mp_##name(MP_NEW, p, len))); \
980 }
981 LOADOP(mp, MP, loadl)
982 LOADOP(mp, MP, loadb)
983 LOADOP(mp, MP, loadl2c)
984 LOADOP(mp, MP, loadb2c)
985 LOADOP(gf, GF, loadl)
986 LOADOP(gf, GF, loadb)
987 #undef LOADOP
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_Size(arg) != 1)
1014 i = PyObject_GetIter(arg);
1015 else {
1016 if ((q = PyTuple_GetItem(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 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 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 "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 mpmul_pymethods, /* @tp_methods@ */
1119 0, /* @tp_members@ */
1120 mpmul_pygetset, /* @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 char *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 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 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, "\
1340 M.mexpr([(XR0, N0), (XR1, N1), ...]) = ZR 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, "\
1346 M.mexp([(X0, N0), (X1, N1), ...]) = 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 "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 mpmont_pymethods, /* @tp_methods@ */
1386 0, /* @tp_members@ */
1387 mpmont_pygetset, /* @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 char *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 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 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, "\
1485 B.mexp([(X0, N0), (X1, N1), ...]) = 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 "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 mpbarrett_pymethods, /* @tp_methods@ */
1525 0, /* @tp_members@ */
1526 mpbarrett_pygetset, /* @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 char *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 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 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 "A reduction context for reduction modulo primes of special form.",
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 mpreduce_pymethods, /* @tp_methods@ */
1653 0, /* @tp_members@ */
1654 mpreduce_pygetset, /* @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 int i = 0, n = c->k;
1683
1684 Py_INCREF(me);
1685 if (PyTuple_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 if (PySequence_Size(q) != n) VALERR("residue count mismatch");
1692 v = xmalloc(n * sizeof(*v));
1693 for (i = 0; i < n; i++) {
1694 if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1695 xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1696 v[i] = xx;
1697 }
1698 z = mp_pywrap(mpcrt_solve(c, MP_NEW, v));
1699 end:
1700 if (v) {
1701 n = i;
1702 for (i = 0; i < n; i++)
1703 MP_DROP(v[i]);
1704 xfree(v);
1705 }
1706 Py_DECREF(me);
1707 Py_XDECREF(q);
1708 return (z);
1709 }
1710
1711 static void mpcrt_pydealloc(PyObject *me)
1712 {
1713 mpcrt *c = MPCRT_PY(me);
1714 mpcrt_destroy(c);
1715 xfree(c->v);
1716 }
1717
1718 static PyObject *mpcrt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1719 {
1720 mpcrt_mod *v = 0;
1721 int n, i = 0;
1722 char *kwlist[] = { "mv", 0 };
1723 PyObject *q = 0, *x;
1724 mp *xx;
1725 mpcrt_pyobj *c = 0;
1726
1727 if (PyTuple_Size(arg) > 1)
1728 q = arg;
1729 else if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &q))
1730 goto end;
1731 Py_INCREF(q);
1732 if (!PySequence_Check(q)) TYERR("want a sequence of moduli");
1733 n = PySequence_Size(q);
1734 if (PyErr_Occurred()) goto end;
1735 if (!n) VALERR("want at least one modulus");
1736 v = xmalloc(n * sizeof(*v));
1737 for (i = 0; i < n; i++) {
1738 if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1739 xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1740 v[i].m = xx; v[i].n = 0; v[i].ni = 0; v[i].nni = 0;
1741 }
1742 c = (mpcrt_pyobj *)ty->tp_alloc(ty, 0);
1743 mpcrt_create(&c->c, v, n, 0);
1744 Py_DECREF(q);
1745 return ((PyObject *)c);
1746
1747 end:
1748 if (v) {
1749 n = i;
1750 for (i = 0; i < n; i++)
1751 MP_DROP(v[i].m);
1752 xfree(v);
1753 }
1754 Py_XDECREF(q);
1755 return (0);
1756 }
1757
1758 static PyObject *mcget_product(PyObject *me, void *hunoz)
1759 { return (mp_pywrap(MP_COPY(MPCRT_PY(me)->mb.m))); }
1760
1761 static PyObject *mcget_moduli(PyObject *me, void *hunoz)
1762 {
1763 int i;
1764 PyObject *q;
1765 mpcrt *c = MPCRT_PY(me);
1766
1767 if ((q = PyList_New(c->k)) == 0) return (0);
1768 for (i = 0; i < c->k; i++)
1769 PyList_SetItem(q, i, mp_pywrap(c->v[i].m));
1770 return (q);
1771 }
1772
1773 static PyGetSetDef mpcrt_pygetset[] = {
1774 #define GETSETNAME(op, name) mc##op##_##name
1775 GET (product, "C.product -> product of moduli")
1776 GET (moduli, "C.moduli -> list of individual moduli")
1777 #undef GETSETNAME
1778 { 0 }
1779 };
1780
1781 static PyMethodDef mpcrt_pymethods[] = {
1782 #define METHNAME(name) mcmeth_##name
1783 METH (solve, "C.solve([R0, R1]) -> X mod C.product")
1784 #undef METHNAME
1785 { 0 }
1786 };
1787
1788 static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = {
1789 PyObject_HEAD_INIT(0) 0, /* Header */
1790 "MPCRT", /* @tp_name@ */
1791 sizeof(mpcrt_pyobj), /* @tp_basicsize@ */
1792 0, /* @tp_itemsize@ */
1793
1794 mpcrt_pydealloc, /* @tp_dealloc@ */
1795 0, /* @tp_print@ */
1796 0, /* @tp_getattr@ */
1797 0, /* @tp_setattr@ */
1798 0, /* @tp_compare@ */
1799 0, /* @tp_repr@ */
1800 0, /* @tp_as_number@ */
1801 0, /* @tp_as_sequence@ */
1802 0, /* @tp_as_mapping@ */
1803 0, /* @tp_hash@ */
1804 0, /* @tp_call@ */
1805 0, /* @tp_str@ */
1806 0, /* @tp_getattro@ */
1807 0, /* @tp_setattro@ */
1808 0, /* @tp_as_buffer@ */
1809 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1810 Py_TPFLAGS_BASETYPE,
1811
1812 /* @tp_doc@ */
1813 "A context for the solution of Chinese Remainder Theorem problems.",
1814
1815 0, /* @tp_traverse@ */
1816 0, /* @tp_clear@ */
1817 0, /* @tp_richcompare@ */
1818 0, /* @tp_weaklistoffset@ */
1819 0, /* @tp_iter@ */
1820 0, /* @tp_iternext@ */
1821 mpcrt_pymethods, /* @tp_methods@ */
1822 0, /* @tp_members@ */
1823 mpcrt_pygetset, /* @tp_getset@ */
1824 0, /* @tp_base@ */
1825 0, /* @tp_dict@ */
1826 0, /* @tp_descr_get@ */
1827 0, /* @tp_descr_set@ */
1828 0, /* @tp_dictoffset@ */
1829 0, /* @tp_init@ */
1830 PyType_GenericAlloc, /* @tp_alloc@ */
1831 mpcrt_pynew, /* @tp_new@ */
1832 0, /* @tp_free@ */
1833 0 /* @tp_is_gc@ */
1834 };
1835
1836 /*----- Binary polynomials ------------------------------------------------*/
1837
1838 static PyObject *gf_pyrepr(PyObject *o)
1839 { return mp_topystring(MP_X(o), 16, "GF(", "0x", "L)"); }
1840
1841 static PyObject *gf_pyrichcompare(PyObject *x, PyObject *y, int op)
1842 {
1843 mp *xx, *yy;
1844 int xl, yl;
1845 int b;
1846
1847 if (gfbinop(x, y, &xx, &yy)) RETURN_NOTIMPL;
1848 switch (op) {
1849 case Py_EQ: b = MP_EQ(xx, yy); break;
1850 case Py_NE: b = !MP_EQ(xx, yy); break;
1851 default:
1852 xl = mp_bits(xx);
1853 yl = mp_bits(yy);
1854 switch (op) {
1855 case Py_LT: b = xl < yl; break;
1856 case Py_LE: b = xl <= yl; break;
1857 case Py_GT: b = xl > yl; break;
1858 case Py_GE: b = xl >= yl; break;
1859 default: abort();
1860 }
1861 break;
1862 }
1863 MP_DROP(xx); MP_DROP(yy);
1864 return (getbool(b));
1865 }
1866
1867 static PyObject *gf_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1868 {
1869 PyObject *x;
1870 mp *z;
1871 mp_pyobj *zz = 0;
1872 int radix = 0;
1873 char *kwlist[] = { "x", "radix", 0 };
1874
1875 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:gf", kwlist, &x, &radix))
1876 goto end;
1877 if (GF_PYCHECK(x)) RETURN_OBJ(x);
1878 if (!good_radix_p(radix, 1)) VALERR("radix out of range");
1879 if ((z = mp_frompyobject(x, radix)) == 0) {
1880 PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
1881 x->ob_type->tp_name);
1882 goto end;
1883 }
1884 if (MP_NEGP(z)) {
1885 MP_DROP(z);
1886 VALERR("gf cannot be negative");
1887 }
1888 zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
1889 zz->x = z;
1890 end:
1891 return ((PyObject *)zz);
1892 }
1893
1894 static PyObject *gf_pyexp(PyObject *x, PyObject *y, PyObject *z)
1895 {
1896 mp *xx = 0, *yy = 0, *zz = 0;
1897 mp *r = 0;
1898 PyObject *rc = 0;
1899
1900 if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 ||
1901 (z && z != Py_None && (zz = tomp(z)) == 0)) {
1902 mp_drop(xx); mp_drop(yy); mp_drop(zz);
1903 RETURN_NOTIMPL;
1904 }
1905 if (!z || z == Py_None) {
1906 if (MP_NEGP(yy)) VALERR("negative exponent");
1907 r = gf_exp(MP_NEW, xx, yy);
1908 } else {
1909 gfreduce gr;
1910 if (MP_ZEROP(zz)) ZDIVERR("zero modulus");
1911 if (MP_NEGP(yy)) {
1912 if ((xx = gf_modinv_checked(xx, xx, zz)) == 0) goto end;
1913 yy = mp_neg(yy, yy);
1914 }
1915 gfreduce_create(&gr, zz);
1916 r = gfreduce_exp(&gr, MP_NEW, xx, yy);
1917 gfreduce_destroy(&gr);
1918 }
1919 rc = gf_pywrap(r);
1920 end:
1921 mp_drop(xx); mp_drop(yy); mp_drop(zz);
1922 return (rc);
1923 }
1924
1925 static PyObject *gfmeth_sqr(PyObject *me, PyObject *arg)
1926 {
1927 if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
1928 return (gf_pywrap(gf_sqr(MP_NEW, MP_X(me))));
1929 }
1930
1931 static PyObject *gfmeth_gcd(PyObject *me, PyObject *arg)
1932 {
1933 PyObject *z = 0;
1934 mp *yy = 0, *zz = MP_NEW;
1935
1936 if (!PyArg_ParseTuple(arg, "O&:gcd", convgf, &yy)) goto end;
1937 gf_gcd(&zz, 0, 0, MP_X(me), yy);
1938 z = gf_pywrap(zz);
1939 end:
1940 if (yy) MP_DROP(yy);
1941 return (z);
1942 }
1943
1944 static PyObject *gfmeth_gcdx(PyObject *me, PyObject *arg)
1945 {
1946 PyObject *z = 0;
1947 mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
1948
1949 if (!PyArg_ParseTuple(arg, "O&:gcdx", convgf, &yy))
1950 goto end;
1951 gf_gcd(&zz, &uu, &vv, MP_X(me), yy);
1952 z = Py_BuildValue("(NNN)",
1953 gf_pywrap(zz), gf_pywrap(uu), gf_pywrap(vv));
1954 end:
1955 if (yy) MP_DROP(yy);
1956 return (z);
1957 }
1958
1959 static PyObject *gfmeth_modinv(PyObject *me, PyObject *arg)
1960 {
1961 PyObject *z = 0;
1962 mp *yy = 0, *zz = MP_NEW;
1963
1964 if (!PyArg_ParseTuple(arg, "O&:modinv", convgf, &yy) ||
1965 (zz = gf_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
1966 goto end;
1967 z = gf_pywrap(zz);
1968 end:
1969 if (yy) MP_DROP(yy);
1970 return (z);
1971 }
1972
1973 static PyObject *gfmeth_irreduciblep(PyObject *me, PyObject *arg)
1974 {
1975 if (!PyArg_ParseTuple(arg, ":irreduciblep")) return (0);
1976 return getbool(gf_irreduciblep(MP_X(me)));
1977 }
1978
1979 static PyObject *gfget_degree(PyObject *me, void *hunoz)
1980 { return (PyInt_FromLong(mp_bits(MP_X(me)) - 1)); }
1981
1982 static PyGetSetDef gf_pygetset[] = {
1983 #define GETSETNAME(op, name) gf##op##_##name
1984 GET (degree, "X.degree -> polynomial degree of X")
1985 #undef GETSETNAME
1986 #define GETSETNAME(op, name) mp##op##_##name
1987 GET (nbits, "X.nbits -> bit length of X")
1988 GET (noctets, "X.noctets -> octet length of X")
1989 #undef GETSETNAME
1990 { 0 }
1991 };
1992
1993 static PyMethodDef gf_pymethods[] = {
1994 #define METHNAME(func) gfmeth_##func
1995 METH (setbit, "X.setbit(N) -> X with bit N set")
1996 METH (clearbit, "X.clearbit(N) -> X with bit N clear")
1997 METH (testbit, "X.testbit(N) -> true/false if bit N set/clear in X")
1998 METH (sqr, "X.sqr() -> X^2")
1999 METH (gcd, "X.gcd(Y) -> gcd(X, Y)")
2000 METH (gcdx,
2001 "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
2002 METH (modinv, "X.modinv(Y) -> multiplicative inverse of Y mod X")
2003 METH (irreduciblep, "X.irreduciblep() -> true/false")
2004 #undef METHNAME
2005 #define METHNAME(func) mpmeth_##func
2006 KWMETH(tostring, "X.tostring([radix = 10]) -> STR")
2007 KWMETH(storel, "X.storel([len = -1]) -> little-endian bytes")
2008 KWMETH(storeb, "X.storeb([len = -1]) -> big-endian bytes")
2009 KWMETH(storel2c,
2010 "X.storel2c([len = -1]) -> little-endian bytes, two's complement")
2011 KWMETH(storeb2c,
2012 "X.storeb2c([len = -1]) -> big-endian bytes, two's complement")
2013 METH (tobuf, "X.tobuf() -> buffer format")
2014 #undef METHNAME
2015 { 0 }
2016 };
2017
2018 static PyNumberMethods gf_pynumber = {
2019 gf_pyadd, /* @nb_add@ */
2020 gf_pysub, /* @nb_subtract@ */
2021 gf_pymul, /* @nb_multiply@ */
2022 0, /* @nb_divide@ */
2023 gf_pymod, /* @nb_remainder@ */
2024 gf_pydivmod, /* @nb_divmod@ */
2025 gf_pyexp, /* @nb_power@ */
2026 mp_pyid, /* @nb_negative@ */
2027 mp_pyid, /* @nb_positive@ */
2028 mp_pyid, /* @nb_absolute@ */
2029 mp_pynonzerop, /* @nb_nonzero@ */
2030 0 /* doesn't make any sense */, /* @nb_invert@ */
2031 gf_pylsl, /* @nb_lshift@ */
2032 gf_pylsr, /* @nb_rshift@ */
2033 gf_pyand, /* @nb_and@ */
2034 gf_pyxor, /* @nb_xor@ */
2035 gf_pyor, /* @nb_or@ */
2036 gf_pycoerce, /* @nb_coerce@ */
2037 mp_pyint, /* @nb_int@ */
2038 mp_pylong, /* @nb_long@ */
2039 0 /* doesn't make any sense */, /* @nb_float@ */
2040 mp_pyoct, /* @nb_oct@ */
2041 mp_pyhex, /* @nb_hex@ */
2042
2043 0, /* @nb_inplace_add@ */
2044 0, /* @nb_inplace_subtract@ */
2045 0, /* @nb_inplace_multiply@ */
2046 0, /* @nb_inplace_divide@ */
2047 0, /* @nb_inplace_remainder@ */
2048 0, /* @nb_inplace_power@ */
2049 0, /* @nb_inplace_lshift@ */
2050 0, /* @nb_inplace_rshift@ */
2051 0, /* @nb_inplace_and@ */
2052 0, /* @nb_inplace_xor@ */
2053 0, /* @nb_inplace_or@ */
2054
2055 gf_pydiv, /* @nb_floor_divide@ */
2056 0, /* @nb_true_divide@ */
2057 0, /* @nb_inplace_floor_divide@ */
2058 0, /* @nb_inplace_true_divide@ */
2059 };
2060
2061 static PyTypeObject gf_pytype_skel = {
2062 PyObject_HEAD_INIT(0) 0, /* Header */
2063 "GF", /* @tp_name@ */
2064 sizeof(mp_pyobj), /* @tp_basicsize@ */
2065 0, /* @tp_itemsize@ */
2066
2067 mp_pydealloc, /* @tp_dealloc@ */
2068 0, /* @tp_print@ */
2069 0, /* @tp_getattr@ */
2070 0, /* @tp_setattr@ */
2071 0, /* @tp_compare@ */
2072 gf_pyrepr, /* @tp_repr@ */
2073 &gf_pynumber, /* @tp_as_number@ */
2074 0, /* @tp_as_sequence@ */
2075 0, /* @tp_as_mapping@ */
2076 mp_pyhash, /* @tp_hash@ */
2077 0, /* @tp_call@ */
2078 mp_pyhex, /* @tp_str@ */
2079 0, /* @tp_getattro@ */
2080 0, /* @tp_setattro@ */
2081 0, /* @tp_as_buffer@ */
2082 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2083 Py_TPFLAGS_CHECKTYPES |
2084 Py_TPFLAGS_BASETYPE,
2085
2086 /* @tp_doc@ */
2087 "Binary polynomials. Support almost all the standard arithmetic\n\
2088 operations.\n\
2089 \n\
2090 Constructor GF(X, [radix = R]) attempts to convert X to a `GF'. If\n\
2091 X is a string, it's read in radix-R form, or we look for a prefix\n\
2092 if R = 0. Other acceptable things are field elements, elliptic curve\n\
2093 points, group elements, Python `int' and `long' objects, and anything\n\
2094 with an integer conversion.\n\
2095 \n\
2096 The name is hopelessly wrong from a technical point of view, but\n\
2097 but it's much easier to type than `p2' or `c2' or whatever.\n\
2098 \n\
2099 Notes:\n\
2100 \n\
2101 * Use `//' for division. GFs don't have `/' division.",
2102
2103 0, /* @tp_traverse@ */
2104 0, /* @tp_clear@ */
2105 gf_pyrichcompare, /* @tp_richcompare@ */
2106 0, /* @tp_weaklistoffset@ */
2107 0, /* @tp_iter@ */
2108 0, /* @tp_iternext@ */
2109 gf_pymethods, /* @tp_methods@ */
2110 0, /* @tp_members@ */
2111 gf_pygetset, /* @tp_getset@ */
2112 0, /* @tp_base@ */
2113 0, /* @tp_dict@ */
2114 0, /* @tp_descr_get@ */
2115 0, /* @tp_descr_set@ */
2116 0, /* @tp_dictoffset@ */
2117 0, /* @tp_init@ */
2118 PyType_GenericAlloc, /* @tp_alloc@ */
2119 gf_pynew, /* @tp_new@ */
2120 0, /* @tp_free@ */
2121 0 /* @tp_is_gc@ */
2122 };
2123
2124 static PyObject *meth__GF_fromstring(PyObject *me,
2125 PyObject *arg, PyObject *kw)
2126 {
2127 int r = 0;
2128 char *p;
2129 Py_ssize_t len;
2130 PyObject *z = 0;
2131 mp *zz;
2132 mptext_stringctx sc;
2133 char *kwlist[] = { "class", "x", "radix", 0 };
2134
2135 if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
2136 kwlist, &me, &p, &len, &r))
2137 goto end;
2138 if (!good_radix_p(r, 1)) VALERR("bad radix");
2139 sc.buf = p; sc.lim = p + len;
2140 if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0 ||
2141 MP_NEGP(zz)) {
2142 if (zz) MP_DROP(zz);
2143 VALERR("bad binary polynomial");
2144 }
2145 z = Py_BuildValue("(Ns#)", gf_pywrap(zz),
2146 sc.buf, (Py_ssize_t)(sc.lim - sc.buf));
2147 end:
2148 return (z);
2149 }
2150
2151 /*----- Sparse poly reduction ---------------------------------------------*/
2152
2153 typedef struct gfreduce_pyobj {
2154 PyObject_HEAD
2155 gfreduce mr;
2156 } gfreduce_pyobj;
2157
2158 #define GFREDUCE_PY(o) (&((gfreduce_pyobj *)(o))->mr)
2159
2160 static PyObject *grmeth_exp(PyObject *me, PyObject *arg)
2161 {
2162 PyObject *rc = 0;
2163 mp *yy = 0, *zz = 0;
2164
2165 if (!PyArg_ParseTuple(arg, "O&O&:exp", convgf, &yy, convgf, &zz))
2166 goto end;
2167 if (MP_NEGP(zz)) {
2168 if ((yy = gf_modinv_checked(yy, yy, GFREDUCE_PY(me)->p)) == 0) goto end;
2169 zz = mp_neg(zz, zz);
2170 }
2171 rc = gf_pywrap(gfreduce_exp(GFREDUCE_PY(me), MP_NEW, yy, zz));
2172 end:
2173 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
2174 return (rc);
2175 }
2176
2177 static PyObject *grmeth_trace(PyObject *me, PyObject *arg)
2178 {
2179 PyObject *rc = 0;
2180 mp *xx = 0;
2181
2182 if (!PyArg_ParseTuple(arg, "O&:trace", convgf, &xx)) goto end;
2183 rc = PyInt_FromLong(gfreduce_trace(GFREDUCE_PY(me), xx));
2184 end:
2185 if (xx) MP_DROP(xx);
2186 return (rc);
2187 }
2188
2189 static PyObject *grmeth_halftrace(PyObject *me, PyObject *arg)
2190 {
2191 PyObject *rc = 0;
2192 mp *xx = 0;
2193
2194 if (!PyArg_ParseTuple(arg, "O&:halftrace", convgf, &xx)) goto end;
2195 rc = gf_pywrap(gfreduce_halftrace(GFREDUCE_PY(me), MP_NEW, xx));
2196 end:
2197 if (xx) MP_DROP(xx);
2198 return (rc);
2199 }
2200
2201 static PyObject *grmeth_sqrt(PyObject *me, PyObject *arg)
2202 {
2203 PyObject *rc = 0;
2204 mp *xx = 0, *yy;
2205
2206 if (!PyArg_ParseTuple(arg, "O&:sqrt", convgf, &xx)) goto end;
2207 if ((yy = gfreduce_sqrt(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
2208 VALERR("no modular square root");
2209 rc = gf_pywrap(yy);
2210 end:
2211 if (xx) MP_DROP(xx);
2212 return (rc);
2213 }
2214
2215 static PyObject *grmeth_quadsolve(PyObject *me, PyObject *arg)
2216 {
2217 PyObject *rc = 0;
2218 mp *xx = 0, *yy;
2219
2220 if (!PyArg_ParseTuple(arg, "O&:quadsolve", convgf, &xx)) goto end;
2221 if ((yy = gfreduce_quadsolve(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
2222 VALERR("no solution found");
2223 rc = gf_pywrap(yy);
2224 end:
2225 if (xx) MP_DROP(xx);
2226 return (rc);
2227 }
2228
2229 static PyObject *grmeth_reduce(PyObject *me, PyObject *arg)
2230 {
2231 PyObject *z = 0;
2232 mp *yy = 0;
2233
2234 if (!PyArg_ParseTuple(arg, "O&:reduce", convgf, &yy)) goto end;
2235 z = gf_pywrap(gfreduce_do(GFREDUCE_PY(me), MP_NEW, yy));
2236 end:
2237 return (z);
2238 }
2239
2240 static void gfreduce_pydealloc(PyObject *me)
2241 {
2242 gfreduce_destroy(GFREDUCE_PY(me));
2243 FREEOBJ(me);
2244 }
2245
2246 static PyObject *gfreduce_pynew(PyTypeObject *ty,
2247 PyObject *arg, PyObject *kw)
2248 {
2249 gfreduce_pyobj *mr = 0;
2250 gfreduce r;
2251 char *kwlist[] = { "m", 0 };
2252 mp *xx = 0;
2253
2254 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convgf, &xx))
2255 goto end;
2256 if (MP_ZEROP(xx)) ZDIVERR("modulus is zero!");
2257 gfreduce_create(&r, xx);
2258 mr = (gfreduce_pyobj *)ty->tp_alloc(ty, 0);
2259 mr->mr = r;
2260 end:
2261 if (xx) MP_DROP(xx);
2262 return ((PyObject *)mr);
2263 }
2264
2265 static PyObject *grget_m(PyObject *me, void *hunoz)
2266 { return (gf_pywrap(MP_COPY(GFREDUCE_PY(me)->p))); }
2267
2268 static PyGetSetDef gfreduce_pygetset[] = {
2269 #define GETSETNAME(op, name) gr##op##_##name
2270 GET (m, "R.m -> reduction polynomial")
2271 #undef GETSETNAME
2272 { 0 }
2273 };
2274
2275 static PyMethodDef gfreduce_pymethods[] = {
2276 #define METHNAME(name) grmeth_##name
2277 METH (reduce, "R.reduce(X) -> X mod B.m")
2278 METH (trace, "R.trace(X) -> Tr(X) = x + x^2 + ... + x^{2^{m - 1}}")
2279 METH (halftrace, "R.halftrace(X) -> x + x^{2^2} + ... + x^{2^{m - 1}}")
2280 METH (sqrt, "R.sqrt(X) -> Y where Y^2 = X mod R")
2281 METH (quadsolve, "R.quadsolve(X) -> Y where Y^2 + Y = X mod R")
2282 METH (exp, "R.exp(X, N) -> X^N mod B.m")
2283 #undef METHNAME
2284 { 0 }
2285 };
2286
2287 static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = {
2288 PyObject_HEAD_INIT(0) 0, /* Header */
2289 "GFReduce", /* @tp_name@ */
2290 sizeof(gfreduce_pyobj), /* @tp_basicsize@ */
2291 0, /* @tp_itemsize@ */
2292
2293 gfreduce_pydealloc, /* @tp_dealloc@ */
2294 0, /* @tp_print@ */
2295 0, /* @tp_getattr@ */
2296 0, /* @tp_setattr@ */
2297 0, /* @tp_compare@ */
2298 0, /* @tp_repr@ */
2299 0, /* @tp_as_number@ */
2300 0, /* @tp_as_sequence@ */
2301 0, /* @tp_as_mapping@ */
2302 0, /* @tp_hash@ */
2303 0, /* @tp_call@ */
2304 0, /* @tp_str@ */
2305 0, /* @tp_getattro@ */
2306 0, /* @tp_setattro@ */
2307 0, /* @tp_as_buffer@ */
2308 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2309 Py_TPFLAGS_BASETYPE,
2310
2311 /* @tp_doc@ */
2312 "A reduction context for reduction modulo sparse irreducible polynomials.",
2313
2314 0, /* @tp_traverse@ */
2315 0, /* @tp_clear@ */
2316 0, /* @tp_richcompare@ */
2317 0, /* @tp_weaklistoffset@ */
2318 0, /* @tp_iter@ */
2319 0, /* @tp_iternext@ */
2320 gfreduce_pymethods, /* @tp_methods@ */
2321 0, /* @tp_members@ */
2322 gfreduce_pygetset, /* @tp_getset@ */
2323 0, /* @tp_base@ */
2324 0, /* @tp_dict@ */
2325 0, /* @tp_descr_get@ */
2326 0, /* @tp_descr_set@ */
2327 0, /* @tp_dictoffset@ */
2328 0, /* @tp_init@ */
2329 PyType_GenericAlloc, /* @tp_alloc@ */
2330 gfreduce_pynew, /* @tp_new@ */
2331 0, /* @tp_free@ */
2332 0 /* @tp_is_gc@ */
2333 };
2334
2335 /*----- Normal/poly transformation ----------------------------------------*/
2336
2337 typedef struct gfn_pyobj {
2338 PyObject_HEAD
2339 mp *p;
2340 gfn ntop, pton;
2341 } gfn_pyobj;
2342
2343 static PyTypeObject *gfn_pytype, gfn_pytype_skel;
2344
2345 #define GFN_P(o) (((gfn_pyobj *)(o))->p)
2346 #define GFN_PTON(o) (&((gfn_pyobj *)(o))->pton)
2347 #define GFN_NTOP(o) (&((gfn_pyobj *)(o))->ntop)
2348
2349 static PyObject *gfn_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
2350 {
2351 mp *p = 0, *beta = 0;
2352 gfn_pyobj *gg = 0;
2353 char *kwlist[] = { "p", "beta", 0 };
2354
2355 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", kwlist,
2356 convgf, &p, convgf, &beta))
2357 goto end;
2358 gg = PyObject_New(gfn_pyobj, ty);
2359 if (gfn_create(p, beta, &gg->ntop, &gg->pton)) {
2360 FREEOBJ(gg);
2361 gg = 0;
2362 VALERR("can't invert transformation matrix");
2363 }
2364 gg->p = MP_COPY(p);
2365 end:
2366 mp_drop(p);
2367 mp_drop(beta);
2368 return ((PyObject *)gg);
2369 }
2370
2371 static PyObject *gfnget_p(PyObject *me, void *hunoz)
2372 { return (gf_pywrap(MP_COPY(GFN_P(me)))); }
2373
2374 static PyObject *gfnget_beta(PyObject *me, void *hunoz)
2375 {
2376 gfn *n = GFN_NTOP(me);
2377 mp *x = n->r[n->n - 1];
2378 return (gf_pywrap(MP_COPY(x)));
2379 }
2380
2381 #define XFORMOP(name, NAME) \
2382 static PyObject *gfnmeth_##name(PyObject *me, PyObject *arg) \
2383 { \
2384 mp *xx = 0; \
2385 mp *z = 0; \
2386 \
2387 if (!PyArg_ParseTuple(arg, "O&:" #name, convgf, &xx)) goto end; \
2388 z = gfn_transform(GFN_##NAME(me), MP_NEW, xx); \
2389 end: \
2390 mp_drop(xx); \
2391 if (!z) return (0); \
2392 return (mp_pywrap(z)); \
2393 }
2394 XFORMOP(pton, PTON)
2395 XFORMOP(ntop, NTOP)
2396 #undef XFORMOP
2397
2398 static void gfn_pydealloc(PyObject *me)
2399 {
2400 gfn_destroy(GFN_PTON(me));
2401 gfn_destroy(GFN_NTOP(me));
2402 FREEOBJ(me);
2403 }
2404
2405 static PyGetSetDef gfn_pygetset[] = {
2406 #define GETSETNAME(op, name) gfn##op##_##name
2407 GET (p, "X.p -> polynomial basis, as polynomial")
2408 GET (beta, "X.beta -> normal basis element, in poly form")
2409 #undef GETSETNAME
2410 { 0 }
2411 };
2412
2413 static PyMethodDef gfn_pymethods[] = {
2414 #define METHNAME(name) gfnmeth_##name
2415 METH (pton, "X.pton(A) -> normal-basis representation of A")
2416 METH (ntop, "X.ntop(A) -> polynomial-basis representation of A")
2417 #undef METHNAME
2418 { 0 }
2419 };
2420
2421 static PyTypeObject gfn_pytype_skel = {
2422 PyObject_HEAD_INIT(0) 0, /* Header */
2423 "GFN", /* @tp_name@ */
2424 sizeof(gfn_pyobj), /* @tp_basicsize@ */
2425 0, /* @tp_itemsize@ */
2426
2427 gfn_pydealloc, /* @tp_dealloc@ */
2428 0, /* @tp_print@ */
2429 0, /* @tp_getattr@ */
2430 0, /* @tp_setattr@ */
2431 0, /* @tp_compare@ */
2432 0, /* @tp_repr@ */
2433 0, /* @tp_as_number@ */
2434 0, /* @tp_as_sequence@ */
2435 0, /* @tp_as_mapping@ */
2436 0, /* @tp_hash@ */
2437 0, /* @tp_call@ */
2438 0, /* @tp_str@ */
2439 0, /* @tp_getattro@ */
2440 0, /* @tp_setattro@ */
2441 0, /* @tp_as_buffer@ */
2442 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2443 Py_TPFLAGS_BASETYPE,
2444
2445 /* @tp_doc@ */
2446 "An object for transforming elements of binary fields between polynomial\n\
2447 and normal basis representations.",
2448
2449 0, /* @tp_traverse@ */
2450 0, /* @tp_clear@ */
2451 0, /* @tp_richcompare@ */
2452 0, /* @tp_weaklistoffset@ */
2453 0, /* @tp_iter@ */
2454 0, /* @tp_iternext@ */
2455 gfn_pymethods, /* @tp_methods@ */
2456 0, /* @tp_members@ */
2457 gfn_pygetset, /* @tp_getset@ */
2458 0, /* @tp_base@ */
2459 0, /* @tp_dict@ */
2460 0, /* @tp_descr_get@ */
2461 0, /* @tp_descr_set@ */
2462 0, /* @tp_dictoffset@ */
2463 0, /* @tp_init@ */
2464 PyType_GenericAlloc, /* @tp_alloc@ */
2465 gfn_pynew, /* @tp_new@ */
2466 0, /* @tp_free@ */
2467 0 /* @tp_is_gc@ */
2468 };
2469
2470 /*----- Glue --------------------------------------------------------------*/
2471
2472 static PyMethodDef methods[] = {
2473 #define METHNAME(func) meth_##func
2474 KWMETH(_MP_fromstring, "\
2475 fromstring(STR, [radix = 0]) -> (X, REST)\n\
2476 \n\
2477 Parse STR as a large integer, according to radix. If radix is zero,\n\
2478 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2479 or `R_' for other radix R.")
2480 KWMETH(_GF_fromstring, "\
2481 fromstring(STR, [radix = 0]) -> (X, REST)\n\
2482 \n\
2483 Parse STR as a binary polynomial, according to radix. If radix is zero,\n\
2484 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2485 or `R_' for other radix R.")
2486 METH (_MP_factorial, "\
2487 factorial(I) -> I!: compute factorial")
2488 METH (_MP_fibonacci, "\
2489 fibonacci(I) -> F(I): compute Fibonacci number")
2490 METH (_MP_loadl, "\
2491 loadl(STR) -> X: read little-endian bytes")
2492 METH (_MP_loadb, "\
2493 loadb(STR) -> X: read big-endian bytes")
2494 METH (_MP_loadl2c, "\
2495 loadl2c(STR) -> X: read little-endian bytes, two's complement")
2496 METH (_MP_loadb2c, "\
2497 loadb2c(STR) -> X: read big-endian bytes, two's complement")
2498 METH (_MP_frombuf, "\
2499 frombuf(STR) -> (X, REST): read buffer format")
2500 METH (_GF_loadl, "\
2501 loadl(STR) -> X: read little-endian bytes")
2502 METH (_GF_loadb, "\
2503 loadb(STR) -> X: read big-endian bytes")
2504 METH (_GF_frombuf, "\
2505 frombuf(STR) -> (X, REST): read buffer format")
2506 #undef METHNAME
2507 { 0 }
2508 };
2509
2510 void mp_pyinit(void)
2511 {
2512 INITTYPE(mp, root);
2513 INITTYPE(gf, root);
2514 INITTYPE(mpmul, root);
2515 INITTYPE(mpmont, root);
2516 INITTYPE(mpbarrett, root);
2517 INITTYPE(mpreduce, root);
2518 INITTYPE(mpcrt, root);
2519 INITTYPE(gfreduce, root);
2520 INITTYPE(gfn, root);
2521 addmethods(methods);
2522 }
2523
2524 void mp_pyinsert(PyObject *mod)
2525 {
2526 INSERT("MP", mp_pytype);
2527 INSERT("MPMul", mpmul_pytype);
2528 INSERT("MPMont", mpmont_pytype);
2529 INSERT("MPBarrett", mpbarrett_pytype);
2530 INSERT("MPReduce", mpreduce_pytype);
2531 INSERT("MPCRT", mpcrt_pytype);
2532 INSERT("GF", gf_pytype);
2533 INSERT("GFReduce", gfreduce_pytype);
2534 INSERT("GFN", gfn_pytype);
2535 }
2536
2537 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library -- Python bindings