~mdw / catacomb-python / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
mp.c: Check that CRT moduli are actually positive.
[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 if (MP_CMP(xx, <=, MP_ZERO)) VALERR("moduli must be positive");
1741 v[i].m = xx; v[i].n = 0; v[i].ni = 0; v[i].nni = 0;
1742 }
1743 c = (mpcrt_pyobj *)ty->tp_alloc(ty, 0);
1744 mpcrt_create(&c->c, v, n, 0);
1745 Py_DECREF(q);
1746 return ((PyObject *)c);
1747
1748 end:
1749 if (v) {
1750 n = i;
1751 for (i = 0; i < n; i++)
1752 MP_DROP(v[i].m);
1753 xfree(v);
1754 }
1755 Py_XDECREF(q);
1756 return (0);
1757 }
1758
1759 static PyObject *mcget_product(PyObject *me, void *hunoz)
1760 { return (mp_pywrap(MP_COPY(MPCRT_PY(me)->mb.m))); }
1761
1762 static PyObject *mcget_moduli(PyObject *me, void *hunoz)
1763 {
1764 int i;
1765 PyObject *q;
1766 mpcrt *c = MPCRT_PY(me);
1767
1768 if ((q = PyList_New(c->k)) == 0) return (0);
1769 for (i = 0; i < c->k; i++)
1770 PyList_SetItem(q, i, mp_pywrap(c->v[i].m));
1771 return (q);
1772 }
1773
1774 static PyGetSetDef mpcrt_pygetset[] = {
1775 #define GETSETNAME(op, name) mc##op##_##name
1776 GET (product, "C.product -> product of moduli")
1777 GET (moduli, "C.moduli -> list of individual moduli")
1778 #undef GETSETNAME
1779 { 0 }
1780 };
1781
1782 static PyMethodDef mpcrt_pymethods[] = {
1783 #define METHNAME(name) mcmeth_##name
1784 METH (solve, "C.solve([R0, R1]) -> X mod C.product")
1785 #undef METHNAME
1786 { 0 }
1787 };
1788
1789 static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = {
1790 PyObject_HEAD_INIT(0) 0, /* Header */
1791 "MPCRT", /* @tp_name@ */
1792 sizeof(mpcrt_pyobj), /* @tp_basicsize@ */
1793 0, /* @tp_itemsize@ */
1794
1795 mpcrt_pydealloc, /* @tp_dealloc@ */
1796 0, /* @tp_print@ */
1797 0, /* @tp_getattr@ */
1798 0, /* @tp_setattr@ */
1799 0, /* @tp_compare@ */
1800 0, /* @tp_repr@ */
1801 0, /* @tp_as_number@ */
1802 0, /* @tp_as_sequence@ */
1803 0, /* @tp_as_mapping@ */
1804 0, /* @tp_hash@ */
1805 0, /* @tp_call@ */
1806 0, /* @tp_str@ */
1807 0, /* @tp_getattro@ */
1808 0, /* @tp_setattro@ */
1809 0, /* @tp_as_buffer@ */
1810 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1811 Py_TPFLAGS_BASETYPE,
1812
1813 /* @tp_doc@ */
1814 "A context for the solution of Chinese Remainder Theorem problems.",
1815
1816 0, /* @tp_traverse@ */
1817 0, /* @tp_clear@ */
1818 0, /* @tp_richcompare@ */
1819 0, /* @tp_weaklistoffset@ */
1820 0, /* @tp_iter@ */
1821 0, /* @tp_iternext@ */
1822 mpcrt_pymethods, /* @tp_methods@ */
1823 0, /* @tp_members@ */
1824 mpcrt_pygetset, /* @tp_getset@ */
1825 0, /* @tp_base@ */
1826 0, /* @tp_dict@ */
1827 0, /* @tp_descr_get@ */
1828 0, /* @tp_descr_set@ */
1829 0, /* @tp_dictoffset@ */
1830 0, /* @tp_init@ */
1831 PyType_GenericAlloc, /* @tp_alloc@ */
1832 mpcrt_pynew, /* @tp_new@ */
1833 0, /* @tp_free@ */
1834 0 /* @tp_is_gc@ */
1835 };
1836
1837 /*----- Binary polynomials ------------------------------------------------*/
1838
1839 static PyObject *gf_pyrepr(PyObject *o)
1840 { return mp_topystring(MP_X(o), 16, "GF(", "0x", "L)"); }
1841
1842 static PyObject *gf_pyrichcompare(PyObject *x, PyObject *y, int op)
1843 {
1844 mp *xx, *yy;
1845 int xl, yl;
1846 int b;
1847
1848 if (gfbinop(x, y, &xx, &yy)) RETURN_NOTIMPL;
1849 switch (op) {
1850 case Py_EQ: b = MP_EQ(xx, yy); break;
1851 case Py_NE: b = !MP_EQ(xx, yy); break;
1852 default:
1853 xl = mp_bits(xx);
1854 yl = mp_bits(yy);
1855 switch (op) {
1856 case Py_LT: b = xl < yl; break;
1857 case Py_LE: b = xl <= yl; break;
1858 case Py_GT: b = xl > yl; break;
1859 case Py_GE: b = xl >= yl; break;
1860 default: abort();
1861 }
1862 break;
1863 }
1864 MP_DROP(xx); MP_DROP(yy);
1865 return (getbool(b));
1866 }
1867
1868 static PyObject *gf_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1869 {
1870 PyObject *x;
1871 mp *z;
1872 mp_pyobj *zz = 0;
1873 int radix = 0;
1874 char *kwlist[] = { "x", "radix", 0 };
1875
1876 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:gf", kwlist, &x, &radix))
1877 goto end;
1878 if (GF_PYCHECK(x)) RETURN_OBJ(x);
1879 if (!good_radix_p(radix, 1)) VALERR("radix out of range");
1880 if ((z = mp_frompyobject(x, radix)) == 0) {
1881 PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
1882 x->ob_type->tp_name);
1883 goto end;
1884 }
1885 if (MP_NEGP(z)) {
1886 MP_DROP(z);
1887 VALERR("gf cannot be negative");
1888 }
1889 zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
1890 zz->x = z;
1891 end:
1892 return ((PyObject *)zz);
1893 }
1894
1895 static PyObject *gf_pyexp(PyObject *x, PyObject *y, PyObject *z)
1896 {
1897 mp *xx = 0, *yy = 0, *zz = 0;
1898 mp *r = 0;
1899 PyObject *rc = 0;
1900
1901 if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 ||
1902 (z && z != Py_None && (zz = tomp(z)) == 0)) {
1903 mp_drop(xx); mp_drop(yy); mp_drop(zz);
1904 RETURN_NOTIMPL;
1905 }
1906 if (!z || z == Py_None) {
1907 if (MP_NEGP(yy)) VALERR("negative exponent");
1908 r = gf_exp(MP_NEW, xx, yy);
1909 } else {
1910 gfreduce gr;
1911 if (MP_ZEROP(zz)) ZDIVERR("zero modulus");
1912 if (MP_NEGP(yy)) {
1913 if ((xx = gf_modinv_checked(xx, xx, zz)) == 0) goto end;
1914 yy = mp_neg(yy, yy);
1915 }
1916 gfreduce_create(&gr, zz);
1917 r = gfreduce_exp(&gr, MP_NEW, xx, yy);
1918 gfreduce_destroy(&gr);
1919 }
1920 rc = gf_pywrap(r);
1921 end:
1922 mp_drop(xx); mp_drop(yy); mp_drop(zz);
1923 return (rc);
1924 }
1925
1926 static PyObject *gfmeth_sqr(PyObject *me, PyObject *arg)
1927 {
1928 if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
1929 return (gf_pywrap(gf_sqr(MP_NEW, MP_X(me))));
1930 }
1931
1932 static PyObject *gfmeth_gcd(PyObject *me, PyObject *arg)
1933 {
1934 PyObject *z = 0;
1935 mp *yy = 0, *zz = MP_NEW;
1936
1937 if (!PyArg_ParseTuple(arg, "O&:gcd", convgf, &yy)) goto end;
1938 gf_gcd(&zz, 0, 0, MP_X(me), yy);
1939 z = gf_pywrap(zz);
1940 end:
1941 if (yy) MP_DROP(yy);
1942 return (z);
1943 }
1944
1945 static PyObject *gfmeth_gcdx(PyObject *me, PyObject *arg)
1946 {
1947 PyObject *z = 0;
1948 mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
1949
1950 if (!PyArg_ParseTuple(arg, "O&:gcdx", convgf, &yy))
1951 goto end;
1952 gf_gcd(&zz, &uu, &vv, MP_X(me), yy);
1953 z = Py_BuildValue("(NNN)",
1954 gf_pywrap(zz), gf_pywrap(uu), gf_pywrap(vv));
1955 end:
1956 if (yy) MP_DROP(yy);
1957 return (z);
1958 }
1959
1960 static PyObject *gfmeth_modinv(PyObject *me, PyObject *arg)
1961 {
1962 PyObject *z = 0;
1963 mp *yy = 0, *zz = MP_NEW;
1964
1965 if (!PyArg_ParseTuple(arg, "O&:modinv", convgf, &yy) ||
1966 (zz = gf_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
1967 goto end;
1968 z = gf_pywrap(zz);
1969 end:
1970 if (yy) MP_DROP(yy);
1971 return (z);
1972 }
1973
1974 static PyObject *gfmeth_irreduciblep(PyObject *me, PyObject *arg)
1975 {
1976 if (!PyArg_ParseTuple(arg, ":irreduciblep")) return (0);
1977 return getbool(gf_irreduciblep(MP_X(me)));
1978 }
1979
1980 static PyObject *gfget_degree(PyObject *me, void *hunoz)
1981 { return (PyInt_FromLong(mp_bits(MP_X(me)) - 1)); }
1982
1983 static PyGetSetDef gf_pygetset[] = {
1984 #define GETSETNAME(op, name) gf##op##_##name
1985 GET (degree, "X.degree -> polynomial degree of X")
1986 #undef GETSETNAME
1987 #define GETSETNAME(op, name) mp##op##_##name
1988 GET (nbits, "X.nbits -> bit length of X")
1989 GET (noctets, "X.noctets -> octet length of X")
1990 #undef GETSETNAME
1991 { 0 }
1992 };
1993
1994 static PyMethodDef gf_pymethods[] = {
1995 #define METHNAME(func) gfmeth_##func
1996 METH (setbit, "X.setbit(N) -> X with bit N set")
1997 METH (clearbit, "X.clearbit(N) -> X with bit N clear")
1998 METH (testbit, "X.testbit(N) -> true/false if bit N set/clear in X")
1999 METH (sqr, "X.sqr() -> X^2")
2000 METH (gcd, "X.gcd(Y) -> gcd(X, Y)")
2001 METH (gcdx,
2002 "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
2003 METH (modinv, "X.modinv(Y) -> multiplicative inverse of Y mod X")
2004 METH (irreduciblep, "X.irreduciblep() -> true/false")
2005 #undef METHNAME
2006 #define METHNAME(func) mpmeth_##func
2007 KWMETH(tostring, "X.tostring([radix = 10]) -> STR")
2008 KWMETH(storel, "X.storel([len = -1]) -> little-endian bytes")
2009 KWMETH(storeb, "X.storeb([len = -1]) -> big-endian bytes")
2010 KWMETH(storel2c,
2011 "X.storel2c([len = -1]) -> little-endian bytes, two's complement")
2012 KWMETH(storeb2c,
2013 "X.storeb2c([len = -1]) -> big-endian bytes, two's complement")
2014 METH (tobuf, "X.tobuf() -> buffer format")
2015 #undef METHNAME
2016 { 0 }
2017 };
2018
2019 static PyNumberMethods gf_pynumber = {
2020 gf_pyadd, /* @nb_add@ */
2021 gf_pysub, /* @nb_subtract@ */
2022 gf_pymul, /* @nb_multiply@ */
2023 0, /* @nb_divide@ */
2024 gf_pymod, /* @nb_remainder@ */
2025 gf_pydivmod, /* @nb_divmod@ */
2026 gf_pyexp, /* @nb_power@ */
2027 mp_pyid, /* @nb_negative@ */
2028 mp_pyid, /* @nb_positive@ */
2029 mp_pyid, /* @nb_absolute@ */
2030 mp_pynonzerop, /* @nb_nonzero@ */
2031 0 /* doesn't make any sense */, /* @nb_invert@ */
2032 gf_pylsl, /* @nb_lshift@ */
2033 gf_pylsr, /* @nb_rshift@ */
2034 gf_pyand, /* @nb_and@ */
2035 gf_pyxor, /* @nb_xor@ */
2036 gf_pyor, /* @nb_or@ */
2037 gf_pycoerce, /* @nb_coerce@ */
2038 mp_pyint, /* @nb_int@ */
2039 mp_pylong, /* @nb_long@ */
2040 0 /* doesn't make any sense */, /* @nb_float@ */
2041 mp_pyoct, /* @nb_oct@ */
2042 mp_pyhex, /* @nb_hex@ */
2043
2044 0, /* @nb_inplace_add@ */
2045 0, /* @nb_inplace_subtract@ */
2046 0, /* @nb_inplace_multiply@ */
2047 0, /* @nb_inplace_divide@ */
2048 0, /* @nb_inplace_remainder@ */
2049 0, /* @nb_inplace_power@ */
2050 0, /* @nb_inplace_lshift@ */
2051 0, /* @nb_inplace_rshift@ */
2052 0, /* @nb_inplace_and@ */
2053 0, /* @nb_inplace_xor@ */
2054 0, /* @nb_inplace_or@ */
2055
2056 gf_pydiv, /* @nb_floor_divide@ */
2057 0, /* @nb_true_divide@ */
2058 0, /* @nb_inplace_floor_divide@ */
2059 0, /* @nb_inplace_true_divide@ */
2060 };
2061
2062 static PyTypeObject gf_pytype_skel = {
2063 PyObject_HEAD_INIT(0) 0, /* Header */
2064 "GF", /* @tp_name@ */
2065 sizeof(mp_pyobj), /* @tp_basicsize@ */
2066 0, /* @tp_itemsize@ */
2067
2068 mp_pydealloc, /* @tp_dealloc@ */
2069 0, /* @tp_print@ */
2070 0, /* @tp_getattr@ */
2071 0, /* @tp_setattr@ */
2072 0, /* @tp_compare@ */
2073 gf_pyrepr, /* @tp_repr@ */
2074 &gf_pynumber, /* @tp_as_number@ */
2075 0, /* @tp_as_sequence@ */
2076 0, /* @tp_as_mapping@ */
2077 mp_pyhash, /* @tp_hash@ */
2078 0, /* @tp_call@ */
2079 mp_pyhex, /* @tp_str@ */
2080 0, /* @tp_getattro@ */
2081 0, /* @tp_setattro@ */
2082 0, /* @tp_as_buffer@ */
2083 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2084 Py_TPFLAGS_CHECKTYPES |
2085 Py_TPFLAGS_BASETYPE,
2086
2087 /* @tp_doc@ */
2088 "Binary polynomials. Support almost all the standard arithmetic\n\
2089 operations.\n\
2090 \n\
2091 Constructor GF(X, [radix = R]) attempts to convert X to a `GF'. If\n\
2092 X is a string, it's read in radix-R form, or we look for a prefix\n\
2093 if R = 0. Other acceptable things are field elements, elliptic curve\n\
2094 points, group elements, Python `int' and `long' objects, and anything\n\
2095 with an integer conversion.\n\
2096 \n\
2097 The name is hopelessly wrong from a technical point of view, but\n\
2098 but it's much easier to type than `p2' or `c2' or whatever.\n\
2099 \n\
2100 Notes:\n\
2101 \n\
2102 * Use `//' for division. GFs don't have `/' division.",
2103
2104 0, /* @tp_traverse@ */
2105 0, /* @tp_clear@ */
2106 gf_pyrichcompare, /* @tp_richcompare@ */
2107 0, /* @tp_weaklistoffset@ */
2108 0, /* @tp_iter@ */
2109 0, /* @tp_iternext@ */
2110 gf_pymethods, /* @tp_methods@ */
2111 0, /* @tp_members@ */
2112 gf_pygetset, /* @tp_getset@ */
2113 0, /* @tp_base@ */
2114 0, /* @tp_dict@ */
2115 0, /* @tp_descr_get@ */
2116 0, /* @tp_descr_set@ */
2117 0, /* @tp_dictoffset@ */
2118 0, /* @tp_init@ */
2119 PyType_GenericAlloc, /* @tp_alloc@ */
2120 gf_pynew, /* @tp_new@ */
2121 0, /* @tp_free@ */
2122 0 /* @tp_is_gc@ */
2123 };
2124
2125 static PyObject *meth__GF_fromstring(PyObject *me,
2126 PyObject *arg, PyObject *kw)
2127 {
2128 int r = 0;
2129 char *p;
2130 Py_ssize_t len;
2131 PyObject *z = 0;
2132 mp *zz;
2133 mptext_stringctx sc;
2134 char *kwlist[] = { "class", "x", "radix", 0 };
2135
2136 if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
2137 kwlist, &me, &p, &len, &r))
2138 goto end;
2139 if (!good_radix_p(r, 1)) VALERR("bad radix");
2140 sc.buf = p; sc.lim = p + len;
2141 if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0 ||
2142 MP_NEGP(zz)) {
2143 if (zz) MP_DROP(zz);
2144 VALERR("bad binary polynomial");
2145 }
2146 z = Py_BuildValue("(Ns#)", gf_pywrap(zz),
2147 sc.buf, (Py_ssize_t)(sc.lim - sc.buf));
2148 end:
2149 return (z);
2150 }
2151
2152 /*----- Sparse poly reduction ---------------------------------------------*/
2153
2154 typedef struct gfreduce_pyobj {
2155 PyObject_HEAD
2156 gfreduce mr;
2157 } gfreduce_pyobj;
2158
2159 #define GFREDUCE_PY(o) (&((gfreduce_pyobj *)(o))->mr)
2160
2161 static PyObject *grmeth_exp(PyObject *me, PyObject *arg)
2162 {
2163 PyObject *rc = 0;
2164 mp *yy = 0, *zz = 0;
2165
2166 if (!PyArg_ParseTuple(arg, "O&O&:exp", convgf, &yy, convgf, &zz))
2167 goto end;
2168 if (MP_NEGP(zz)) {
2169 if ((yy = gf_modinv_checked(yy, yy, GFREDUCE_PY(me)->p)) == 0) goto end;
2170 zz = mp_neg(zz, zz);
2171 }
2172 rc = gf_pywrap(gfreduce_exp(GFREDUCE_PY(me), MP_NEW, yy, zz));
2173 end:
2174 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
2175 return (rc);
2176 }
2177
2178 static PyObject *grmeth_trace(PyObject *me, PyObject *arg)
2179 {
2180 PyObject *rc = 0;
2181 mp *xx = 0;
2182
2183 if (!PyArg_ParseTuple(arg, "O&:trace", convgf, &xx)) goto end;
2184 rc = PyInt_FromLong(gfreduce_trace(GFREDUCE_PY(me), xx));
2185 end:
2186 if (xx) MP_DROP(xx);
2187 return (rc);
2188 }
2189
2190 static PyObject *grmeth_halftrace(PyObject *me, PyObject *arg)
2191 {
2192 PyObject *rc = 0;
2193 mp *xx = 0;
2194
2195 if (!PyArg_ParseTuple(arg, "O&:halftrace", convgf, &xx)) goto end;
2196 rc = gf_pywrap(gfreduce_halftrace(GFREDUCE_PY(me), MP_NEW, xx));
2197 end:
2198 if (xx) MP_DROP(xx);
2199 return (rc);
2200 }
2201
2202 static PyObject *grmeth_sqrt(PyObject *me, PyObject *arg)
2203 {
2204 PyObject *rc = 0;
2205 mp *xx = 0, *yy;
2206
2207 if (!PyArg_ParseTuple(arg, "O&:sqrt", convgf, &xx)) goto end;
2208 if ((yy = gfreduce_sqrt(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
2209 VALERR("no modular square root");
2210 rc = gf_pywrap(yy);
2211 end:
2212 if (xx) MP_DROP(xx);
2213 return (rc);
2214 }
2215
2216 static PyObject *grmeth_quadsolve(PyObject *me, PyObject *arg)
2217 {
2218 PyObject *rc = 0;
2219 mp *xx = 0, *yy;
2220
2221 if (!PyArg_ParseTuple(arg, "O&:quadsolve", convgf, &xx)) goto end;
2222 if ((yy = gfreduce_quadsolve(GFREDUCE_PY(me), MP_NEW, xx)) == 0)
2223 VALERR("no solution found");
2224 rc = gf_pywrap(yy);
2225 end:
2226 if (xx) MP_DROP(xx);
2227 return (rc);
2228 }
2229
2230 static PyObject *grmeth_reduce(PyObject *me, PyObject *arg)
2231 {
2232 PyObject *z = 0;
2233 mp *yy = 0;
2234
2235 if (!PyArg_ParseTuple(arg, "O&:reduce", convgf, &yy)) goto end;
2236 z = gf_pywrap(gfreduce_do(GFREDUCE_PY(me), MP_NEW, yy));
2237 end:
2238 return (z);
2239 }
2240
2241 static void gfreduce_pydealloc(PyObject *me)
2242 {
2243 gfreduce_destroy(GFREDUCE_PY(me));
2244 FREEOBJ(me);
2245 }
2246
2247 static PyObject *gfreduce_pynew(PyTypeObject *ty,
2248 PyObject *arg, PyObject *kw)
2249 {
2250 gfreduce_pyobj *mr = 0;
2251 gfreduce r;
2252 char *kwlist[] = { "m", 0 };
2253 mp *xx = 0;
2254
2255 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convgf, &xx))
2256 goto end;
2257 if (MP_ZEROP(xx)) ZDIVERR("modulus is zero!");
2258 gfreduce_create(&r, xx);
2259 mr = (gfreduce_pyobj *)ty->tp_alloc(ty, 0);
2260 mr->mr = r;
2261 end:
2262 if (xx) MP_DROP(xx);
2263 return ((PyObject *)mr);
2264 }
2265
2266 static PyObject *grget_m(PyObject *me, void *hunoz)
2267 { return (gf_pywrap(MP_COPY(GFREDUCE_PY(me)->p))); }
2268
2269 static PyGetSetDef gfreduce_pygetset[] = {
2270 #define GETSETNAME(op, name) gr##op##_##name
2271 GET (m, "R.m -> reduction polynomial")
2272 #undef GETSETNAME
2273 { 0 }
2274 };
2275
2276 static PyMethodDef gfreduce_pymethods[] = {
2277 #define METHNAME(name) grmeth_##name
2278 METH (reduce, "R.reduce(X) -> X mod B.m")
2279 METH (trace, "R.trace(X) -> Tr(X) = x + x^2 + ... + x^{2^{m - 1}}")
2280 METH (halftrace, "R.halftrace(X) -> x + x^{2^2} + ... + x^{2^{m - 1}}")
2281 METH (sqrt, "R.sqrt(X) -> Y where Y^2 = X mod R")
2282 METH (quadsolve, "R.quadsolve(X) -> Y where Y^2 + Y = X mod R")
2283 METH (exp, "R.exp(X, N) -> X^N mod B.m")
2284 #undef METHNAME
2285 { 0 }
2286 };
2287
2288 static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = {
2289 PyObject_HEAD_INIT(0) 0, /* Header */
2290 "GFReduce", /* @tp_name@ */
2291 sizeof(gfreduce_pyobj), /* @tp_basicsize@ */
2292 0, /* @tp_itemsize@ */
2293
2294 gfreduce_pydealloc, /* @tp_dealloc@ */
2295 0, /* @tp_print@ */
2296 0, /* @tp_getattr@ */
2297 0, /* @tp_setattr@ */
2298 0, /* @tp_compare@ */
2299 0, /* @tp_repr@ */
2300 0, /* @tp_as_number@ */
2301 0, /* @tp_as_sequence@ */
2302 0, /* @tp_as_mapping@ */
2303 0, /* @tp_hash@ */
2304 0, /* @tp_call@ */
2305 0, /* @tp_str@ */
2306 0, /* @tp_getattro@ */
2307 0, /* @tp_setattro@ */
2308 0, /* @tp_as_buffer@ */
2309 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2310 Py_TPFLAGS_BASETYPE,
2311
2312 /* @tp_doc@ */
2313 "A reduction context for reduction modulo sparse irreducible polynomials.",
2314
2315 0, /* @tp_traverse@ */
2316 0, /* @tp_clear@ */
2317 0, /* @tp_richcompare@ */
2318 0, /* @tp_weaklistoffset@ */
2319 0, /* @tp_iter@ */
2320 0, /* @tp_iternext@ */
2321 gfreduce_pymethods, /* @tp_methods@ */
2322 0, /* @tp_members@ */
2323 gfreduce_pygetset, /* @tp_getset@ */
2324 0, /* @tp_base@ */
2325 0, /* @tp_dict@ */
2326 0, /* @tp_descr_get@ */
2327 0, /* @tp_descr_set@ */
2328 0, /* @tp_dictoffset@ */
2329 0, /* @tp_init@ */
2330 PyType_GenericAlloc, /* @tp_alloc@ */
2331 gfreduce_pynew, /* @tp_new@ */
2332 0, /* @tp_free@ */
2333 0 /* @tp_is_gc@ */
2334 };
2335
2336 /*----- Normal/poly transformation ----------------------------------------*/
2337
2338 typedef struct gfn_pyobj {
2339 PyObject_HEAD
2340 mp *p;
2341 gfn ntop, pton;
2342 } gfn_pyobj;
2343
2344 static PyTypeObject *gfn_pytype, gfn_pytype_skel;
2345
2346 #define GFN_P(o) (((gfn_pyobj *)(o))->p)
2347 #define GFN_PTON(o) (&((gfn_pyobj *)(o))->pton)
2348 #define GFN_NTOP(o) (&((gfn_pyobj *)(o))->ntop)
2349
2350 static PyObject *gfn_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
2351 {
2352 mp *p = 0, *beta = 0;
2353 gfn_pyobj *gg = 0;
2354 char *kwlist[] = { "p", "beta", 0 };
2355
2356 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", kwlist,
2357 convgf, &p, convgf, &beta))
2358 goto end;
2359 gg = PyObject_New(gfn_pyobj, ty);
2360 if (gfn_create(p, beta, &gg->ntop, &gg->pton)) {
2361 FREEOBJ(gg);
2362 gg = 0;
2363 VALERR("can't invert transformation matrix");
2364 }
2365 gg->p = MP_COPY(p);
2366 end:
2367 mp_drop(p);
2368 mp_drop(beta);
2369 return ((PyObject *)gg);
2370 }
2371
2372 static PyObject *gfnget_p(PyObject *me, void *hunoz)
2373 { return (gf_pywrap(MP_COPY(GFN_P(me)))); }
2374
2375 static PyObject *gfnget_beta(PyObject *me, void *hunoz)
2376 {
2377 gfn *n = GFN_NTOP(me);
2378 mp *x = n->r[n->n - 1];
2379 return (gf_pywrap(MP_COPY(x)));
2380 }
2381
2382 #define XFORMOP(name, NAME) \
2383 static PyObject *gfnmeth_##name(PyObject *me, PyObject *arg) \
2384 { \
2385 mp *xx = 0; \
2386 mp *z = 0; \
2387 \
2388 if (!PyArg_ParseTuple(arg, "O&:" #name, convgf, &xx)) goto end; \
2389 z = gfn_transform(GFN_##NAME(me), MP_NEW, xx); \
2390 end: \
2391 mp_drop(xx); \
2392 if (!z) return (0); \
2393 return (mp_pywrap(z)); \
2394 }
2395 XFORMOP(pton, PTON)
2396 XFORMOP(ntop, NTOP)
2397 #undef XFORMOP
2398
2399 static void gfn_pydealloc(PyObject *me)
2400 {
2401 gfn_destroy(GFN_PTON(me));
2402 gfn_destroy(GFN_NTOP(me));
2403 FREEOBJ(me);
2404 }
2405
2406 static PyGetSetDef gfn_pygetset[] = {
2407 #define GETSETNAME(op, name) gfn##op##_##name
2408 GET (p, "X.p -> polynomial basis, as polynomial")
2409 GET (beta, "X.beta -> normal basis element, in poly form")
2410 #undef GETSETNAME
2411 { 0 }
2412 };
2413
2414 static PyMethodDef gfn_pymethods[] = {
2415 #define METHNAME(name) gfnmeth_##name
2416 METH (pton, "X.pton(A) -> normal-basis representation of A")
2417 METH (ntop, "X.ntop(A) -> polynomial-basis representation of A")
2418 #undef METHNAME
2419 { 0 }
2420 };
2421
2422 static PyTypeObject gfn_pytype_skel = {
2423 PyObject_HEAD_INIT(0) 0, /* Header */
2424 "GFN", /* @tp_name@ */
2425 sizeof(gfn_pyobj), /* @tp_basicsize@ */
2426 0, /* @tp_itemsize@ */
2427
2428 gfn_pydealloc, /* @tp_dealloc@ */
2429 0, /* @tp_print@ */
2430 0, /* @tp_getattr@ */
2431 0, /* @tp_setattr@ */
2432 0, /* @tp_compare@ */
2433 0, /* @tp_repr@ */
2434 0, /* @tp_as_number@ */
2435 0, /* @tp_as_sequence@ */
2436 0, /* @tp_as_mapping@ */
2437 0, /* @tp_hash@ */
2438 0, /* @tp_call@ */
2439 0, /* @tp_str@ */
2440 0, /* @tp_getattro@ */
2441 0, /* @tp_setattro@ */
2442 0, /* @tp_as_buffer@ */
2443 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2444 Py_TPFLAGS_BASETYPE,
2445
2446 /* @tp_doc@ */
2447 "An object for transforming elements of binary fields between polynomial\n\
2448 and normal basis representations.",
2449
2450 0, /* @tp_traverse@ */
2451 0, /* @tp_clear@ */
2452 0, /* @tp_richcompare@ */
2453 0, /* @tp_weaklistoffset@ */
2454 0, /* @tp_iter@ */
2455 0, /* @tp_iternext@ */
2456 gfn_pymethods, /* @tp_methods@ */
2457 0, /* @tp_members@ */
2458 gfn_pygetset, /* @tp_getset@ */
2459 0, /* @tp_base@ */
2460 0, /* @tp_dict@ */
2461 0, /* @tp_descr_get@ */
2462 0, /* @tp_descr_set@ */
2463 0, /* @tp_dictoffset@ */
2464 0, /* @tp_init@ */
2465 PyType_GenericAlloc, /* @tp_alloc@ */
2466 gfn_pynew, /* @tp_new@ */
2467 0, /* @tp_free@ */
2468 0 /* @tp_is_gc@ */
2469 };
2470
2471 /*----- Glue --------------------------------------------------------------*/
2472
2473 static PyMethodDef methods[] = {
2474 #define METHNAME(func) meth_##func
2475 KWMETH(_MP_fromstring, "\
2476 fromstring(STR, [radix = 0]) -> (X, REST)\n\
2477 \n\
2478 Parse STR as a large integer, according to radix. If radix is zero,\n\
2479 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2480 or `R_' for other radix R.")
2481 KWMETH(_GF_fromstring, "\
2482 fromstring(STR, [radix = 0]) -> (X, REST)\n\
2483 \n\
2484 Parse STR as a binary polynomial, according to radix. If radix is zero,\n\
2485 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2486 or `R_' for other radix R.")
2487 METH (_MP_factorial, "\
2488 factorial(I) -> I!: compute factorial")
2489 METH (_MP_fibonacci, "\
2490 fibonacci(I) -> F(I): compute Fibonacci number")
2491 METH (_MP_loadl, "\
2492 loadl(STR) -> X: read little-endian bytes")
2493 METH (_MP_loadb, "\
2494 loadb(STR) -> X: read big-endian bytes")
2495 METH (_MP_loadl2c, "\
2496 loadl2c(STR) -> X: read little-endian bytes, two's complement")
2497 METH (_MP_loadb2c, "\
2498 loadb2c(STR) -> X: read big-endian bytes, two's complement")
2499 METH (_MP_frombuf, "\
2500 frombuf(STR) -> (X, REST): read buffer format")
2501 METH (_GF_loadl, "\
2502 loadl(STR) -> X: read little-endian bytes")
2503 METH (_GF_loadb, "\
2504 loadb(STR) -> X: read big-endian bytes")
2505 METH (_GF_frombuf, "\
2506 frombuf(STR) -> (X, REST): read buffer format")
2507 #undef METHNAME
2508 { 0 }
2509 };
2510
2511 void mp_pyinit(void)
2512 {
2513 INITTYPE(mp, root);
2514 INITTYPE(gf, root);
2515 INITTYPE(mpmul, root);
2516 INITTYPE(mpmont, root);
2517 INITTYPE(mpbarrett, root);
2518 INITTYPE(mpreduce, root);
2519 INITTYPE(mpcrt, root);
2520 INITTYPE(gfreduce, root);
2521 INITTYPE(gfn, root);
2522 addmethods(methods);
2523 }
2524
2525 void mp_pyinsert(PyObject *mod)
2526 {
2527 INSERT("MP", mp_pytype);
2528 INSERT("MPMul", mpmul_pytype);
2529 INSERT("MPMont", mpmont_pytype);
2530 INSERT("MPBarrett", mpbarrett_pytype);
2531 INSERT("MPReduce", mpreduce_pytype);
2532 INSERT("MPCRT", mpcrt_pytype);
2533 INSERT("GF", gf_pytype);
2534 INSERT("GFReduce", gfreduce_pytype);
2535 INSERT("GFN", gfn_pytype);
2536 }
2537
2538 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library -- Python bindings