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