3 * Prime number generation
5 * (c) 2005 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of the Python interface to Catacomb.
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.
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.
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.
27 /*----- Header files ------------------------------------------------------*/
29 #include "catacomb-python.h"
31 /*----- Filters -----------------------------------------------------------*/
33 PyTypeObject *pfilt_pytype;
35 static PyObject *pfilt_pywrap(pfilt *f)
38 o = PyObject_New(pfilt_pyobj, pfilt_pytype);
40 o->st = pfilt_step(f, 0);
41 return ((PyObject *)o);
44 static PyObject *pfilt_pymake(PyTypeObject *ty, PyObject *xobj)
49 if (PFILT_PYCHECK(xobj)) RETURN_OBJ(xobj);
50 if ((x = getmp(xobj)) == 0) goto end;
51 o = (pfilt_pyobj *)ty->tp_alloc(ty, 0);
52 o->st = pfilt_create(&o->f, x);
55 return ((PyObject *)o);
58 static PyObject *pfilt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
60 char *kwlist[] = { "x", 0 };
63 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &xobj))
65 return (pfilt_pymake(ty, xobj));
68 static void pfilt_pydealloc(PyObject *me)
69 { pfilt_destroy(PFILT_F(me)); FREEOBJ(me); }
71 static PyObject *pfmeth_step(PyObject *me, PyObject *arg)
75 if (!PyArg_ParseTuple(arg, "O&:step", convmpw, &x)) return (0);
76 PFILT_ST(me) = pfilt_step(PFILT_F(me), x);
80 static PyObject *pfmeth_muladd(PyObject *me, PyObject *arg)
85 if (!PyArg_ParseTuple(arg, "O&O&:muladd", convmpw, &m, convmpw, &a))
87 o = PyObject_New(pfilt_pyobj, pfilt_pytype);
88 o->st = pfilt_muladd(&o->f, PFILT_F(me), m, a);
89 return ((PyObject *)o);
92 static CONVFUNC(pfilt, pfilt *, PFILT_F)
94 static PyObject *pfmeth_jump(PyObject *me, PyObject *arg)
98 if (!PyArg_ParseTuple(arg, "O&:jump", convpfilt, &f)) return (0);
99 PFILT_ST(me) = pfilt_jump(PFILT_F(me), f);
103 static PyObject *meth__PrimeFilter_smallfactor(PyObject *me, PyObject *arg)
108 if (!PyArg_ParseTuple(arg, "OO&:smallfactor", &me, convmp, &x)) goto end;
109 rc = PyInt_FromLong(pfilt_smallfactor(x));
115 static int pfilt_pynonzerop(PyObject *me)
116 { return (PFILT_ST(me) != PGEN_FAIL); }
118 static PyObject *pfilt_pyint(PyObject *me)
123 if (!mp_tolong_checked(PFILT_F(me)->m, &l, 0)) rc = PyInt_FromLong(l);
124 else rc = mp_topylong(PFILT_F(me)->m);
128 static PyObject *pfilt_pylong(PyObject *me)
129 { return (mp_topylong(PFILT_F(me)->m)); }
131 static PyObject *pfget_x(PyObject *me, void *hunoz)
132 { return (mp_pywrap(MP_COPY(PFILT_F(me)->m))); }
134 static PyObject *pfget_status(PyObject *me, void *hunoz)
135 { return (PyInt_FromLong(PFILT_ST(me))); }
137 static PyGetSetDef pfilt_pygetset[] = {
138 #define GETSETNAME(op, name) pf##op##_##name
139 GET (x, "F.x -> current position of filter")
140 GET (status, "F.status -> primality status of filter")
145 static PyMethodDef pfilt_pymethods[] = {
146 #define METHNAME(name) pfmeth_##name
147 METH (step, "F.step(N)")
148 METH (muladd, "F.muladd(M, A)")
149 METH (jump, "F.jump(FF)")
154 static PyNumberMethods pfilt_pynumber = {
156 0, /* @nb_subtract@ */
157 0, /* @nb_multiply@ */
159 0, /* @nb_remainder@ */
162 0, /* @nb_negative@ */
163 0, /* @nb_positive@ */
164 0, /* @nb_absolute@ */
165 pfilt_pynonzerop, /* @nb_nonzero@ */
173 pfilt_pyint, /* @nb_int@ */
174 pfilt_pylong, /* @nb_long@ */
179 0, /* @nb_inplace_add@ */
180 0, /* @nb_inplace_subtract@ */
181 0, /* @nb_inplace_multiply@ */
182 0, /* @nb_inplace_divide@ */
183 0, /* @nb_inplace_remainder@ */
184 0, /* @nb_inplace_power@ */
185 0, /* @nb_inplace_lshift@ */
186 0, /* @nb_inplace_rshift@ */
187 0, /* @nb_inplace_and@ */
188 0, /* @nb_inplace_xor@ */
189 0, /* @nb_inplace_or@ */
191 0, /* @nb_floor_divide@ */
192 0, /* @nb_true_divide@ */
193 0, /* @nb_inplace_floor_divide@ */
194 0, /* @nb_inplace_true_divide@ */
197 static PyTypeObject pfilt_pytype_skel = {
198 PyObject_HEAD_INIT(0) 0, /* Header */
199 "PrimeFilter", /* @tp_name@ */
200 sizeof(pfilt_pyobj), /* @tp_basicsize@ */
201 0, /* @tp_itemsize@ */
203 pfilt_pydealloc, /* @tp_dealloc@ */
205 0, /* @tp_getattr@ */
206 0, /* @tp_setattr@ */
207 0, /* @tp_compare@ */
209 &pfilt_pynumber, /* @tp_as_number@ */
210 0, /* @tp_as_sequence@ */
211 0, /* @tp_as_mapping@ */
215 0, /* @tp_getattro@ */
216 0, /* @tp_setattro@ */
217 0, /* @tp_as_buffer@ */
218 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
222 "Small-primes filter.",
224 0, /* @tp_traverse@ */
226 0, /* @tp_richcompare@ */
227 0, /* @tp_weaklistoffset@ */
229 0, /* @tp_iternext@ */
230 pfilt_pymethods, /* @tp_methods@ */
231 0, /* @tp_members@ */
232 pfilt_pygetset, /* @tp_getset@ */
235 0, /* @tp_descr_get@ */
236 0, /* @tp_descr_set@ */
237 0, /* @tp_dictoffset@ */
239 PyType_GenericAlloc, /* @tp_alloc@ */
240 pfilt_pynew, /* @tp_new@ */
245 /*----- Rabin-Miller testing ----------------------------------------------*/
247 typedef struct rabin_pyobj {
252 static PyTypeObject *rabin_pytype;
253 #define RABIN_R(o) (&((rabin_pyobj *)(o))->r)
255 static PyObject *rabin_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
259 char *kwlist[] = { "x", 0 };
261 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &x))
263 if (!MP_POSP(x) || MP_EVENP(x)) VALERR("must be positive and odd");
264 o = (rabin_pyobj *)ty->tp_alloc(ty, 0);
265 rabin_create(&o->r, x);
267 return ((PyObject *)o);
270 static void rabin_pydealloc(PyObject *me)
272 rabin_destroy(RABIN_R(me));
276 static PyObject *rmeth_test(PyObject *me, PyObject *arg)
281 if (!PyArg_ParseTuple(arg, "O&:test", convmp, &w)) goto end;
282 rc = PyInt_FromLong(rabin_test(RABIN_R(me), w));
288 static PyObject *rmeth_rtest(PyObject *me, PyObject *arg)
293 if (!PyArg_ParseTuple(arg, "O&:rtest", convmp, &w)) goto end;
294 rc = PyInt_FromLong(rabin_rtest(RABIN_R(me), w));
300 static PyObject *rget_niters(PyObject *me, void *hunoz)
301 { return (PyInt_FromLong(rabin_iters(mp_bits(RABIN_R(me)->mm.m)))); }
303 static PyObject *rget_x(PyObject *me, void *hunoz)
304 { return (mp_pywrap(MP_COPY(RABIN_R(me)->mm.m))); }
306 static PyObject *meth__RabinMiller_iters(PyObject *me, PyObject *arg)
310 if (!PyArg_ParseTuple(arg, "OO&:iters", &me, convuint, &n)) return (0);
311 return (PyInt_FromLong(rabin_iters(n)));
314 static PyGetSetDef rabin_pygetset[] = {
315 #define GETSETNAME(op, name) r##op##_##name
316 GET (x, "R.x -> number under test")
317 GET (niters, "R.niters -> suggested number of tests")
322 static PyMethodDef rabin_pymethods[] = {
323 #define METHNAME(name) rmeth_##name
324 METH (test, "R.test(W) -> PGST")
325 METH (rtest, "R.rtest(W) -> PGST")
330 static PyTypeObject rabin_pytype_skel = {
331 PyObject_HEAD_INIT(0) 0, /* Header */
332 "RabinMiller", /* @tp_name@ */
333 sizeof(rabin_pyobj), /* @tp_basicsize@ */
334 0, /* @tp_itemsize@ */
336 rabin_pydealloc, /* @tp_dealloc@ */
338 0, /* @tp_getattr@ */
339 0, /* @tp_setattr@ */
340 0, /* @tp_compare@ */
342 0, /* @tp_as_number@ */
343 0, /* @tp_as_sequence@ */
344 0, /* @tp_as_mapping@ */
348 0, /* @tp_getattro@ */
349 0, /* @tp_setattro@ */
350 0, /* @tp_as_buffer@ */
351 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
355 "Rabin-Miller strong primality test.",
357 0, /* @tp_traverse@ */
359 0, /* @tp_richcompare@ */
360 0, /* @tp_weaklistoffset@ */
362 0, /* @tp_iternext@ */
363 rabin_pymethods, /* @tp_methods@ */
364 0, /* @tp_members@ */
365 rabin_pygetset, /* @tp_getset@ */
368 0, /* @tp_descr_get@ */
369 0, /* @tp_descr_set@ */
370 0, /* @tp_dictoffset@ */
372 PyType_GenericAlloc, /* @tp_alloc@ */
373 rabin_pynew, /* @tp_new@ */
378 /*----- Events ------------------------------------------------------------*/
380 typedef struct pgevent_pyobj {
386 static PyTypeObject *pgevent_pytype;
387 #define PGEVENT_EV(o) (((pgevent_pyobj *)(o))->ev)
389 static PyObject *pgevent_pywrap(pgen_event *ev)
391 pgevent_pyobj *o = PyObject_New(pgevent_pyobj, pgevent_pytype);
392 o->ev = ev; o->r = 0;
393 return ((PyObject *)o);
396 static CONVFUNC(pgevent, pgen_event *, PGEVENT_EV)
398 static void pgevent_kill(PyObject *me)
400 pgevent_pyobj *ev = (pgevent_pyobj *)me;
403 if (ev->r) GRAND_R(ev->r) = 0;
406 static void pgevent_pydealloc(PyObject *me)
408 pgevent_pyobj *ev = (pgevent_pyobj *)me;
409 if (ev->r) Py_DECREF(ev->r);
413 #define PGEVENT_CHECK(me) do { \
414 if (!PGEVENT_EV(me)) { \
415 PyErr_SetString(PyExc_ValueError, "event object is no longer valid"); \
420 static PyObject *peget_name(PyObject *me, void *hunoz)
421 { PGEVENT_CHECK(me); return (PyString_FromString(PGEVENT_EV(me)->name)); }
423 static PyObject *peget_x(PyObject *me, void *hunoz)
424 { PGEVENT_CHECK(me); return (mp_pywrap(MP_COPY(PGEVENT_EV(me)->m))); }
426 static PyObject *peget_steps(PyObject *me, void *hunoz)
427 { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->steps)); }
429 static PyObject *peget_tests(PyObject *me, void *hunoz)
430 { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->tests)); }
432 static PyObject *peget_rng(PyObject *me, void *hunoz)
434 pgevent_pyobj *ev = (pgevent_pyobj *)me;
437 if (!ev->r) ev->r = grand_pywrap(ev->ev->r, 0);
438 Py_INCREF(ev->r); return ((PyObject *)ev->r);
441 static int peset_x(PyObject *me, PyObject *xobj, void *hunoz)
444 pgen_event *ev = PGEVENT_EV(me);
446 if (!xobj) NIERR("__del__");
448 if ((x = getmp(xobj)) == 0) goto end;
457 static PyGetSetDef pgevent_pygetset[] = {
458 #define GETSETNAME(op, name) pe##op##_##name
459 GET (name, "EV.name -> value being generated")
460 GETSET(x, "EV.x -> value under test")
461 GET (steps, "EV.steps -> number of steps left")
462 GET (tests, "EV.tests -> tests before passing")
463 GET (rng, "EV.rng -> (noncrypto) random number generator")
468 static PyTypeObject pgevent_pytype_skel = {
469 PyObject_HEAD_INIT(0) 0, /* Header */
470 "PrimeGenEvent", /* @tp_name@ */
471 sizeof(pgevent_pyobj), /* @tp_basicsize@ */
472 0, /* @tp_itemsize@ */
474 pgevent_pydealloc, /* @tp_dealloc@ */
476 0, /* @tp_getattr@ */
477 0, /* @tp_setattr@ */
478 0, /* @tp_compare@ */
480 0, /* @tp_as_number@ */
481 0, /* @tp_as_sequence@ */
482 0, /* @tp_as_mapping@ */
486 0, /* @tp_getattro@ */
487 0, /* @tp_setattro@ */
488 0, /* @tp_as_buffer@ */
489 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
493 "Prime-generation event.",
495 0, /* @tp_traverse@ */
497 0, /* @tp_richcompare@ */
498 0, /* @tp_weaklistoffset@ */
500 0, /* @tp_iternext@ */
501 0, /* @tp_methods@ */
502 0, /* @tp_members@ */
503 pgevent_pygetset, /* @tp_getset@ */
506 0, /* @tp_descr_get@ */
507 0, /* @tp_descr_set@ */
508 0, /* @tp_dictoffset@ */
510 PyType_GenericAlloc, /* @tp_alloc@ */
511 abstract_pynew, /* @tp_new@ */
516 /*----- Event handlers ----------------------------------------------------*/
518 PyTypeObject *pgev_pytype;
520 typedef struct pgstep_pyobj {
525 static PyTypeObject *pgstep_pytype;
526 #define PGSTEP_STEP(o) (((pgstep_pyobj *)(o))->f.step)
528 typedef struct pgjump_pyobj {
534 static PyTypeObject *pgjump_pytype;
535 #define PGJUMP_FOBJ(o) (((pgjump_pyobj *)(o))->fobj)
536 #define PGJUMP_J(o) (&((pgjump_pyobj *)(o))->j)
538 typedef struct pgtest_pyobj {
543 static PyTypeObject *pgtest_pytype;
545 static int pgev_python(int rq, pgen_event *ev, void *p)
553 "pg_abort", "pg_done", "pg_begin", "pg_try", "pg_fail", "pg_pass"
557 if (rq > N(meth)) SYSERR("event code out of range");
558 pyev = pgevent_pywrap(ev);
559 if ((rc = PyObject_CallMethod(pg->obj, meth[rq], "(O)", pyev)) == 0)
563 else if ((l = PyInt_AsLong(rc)) == -1 && PyErr_Occurred())
565 else if (l < PGEN_ABORT || l > PGEN_PASS)
566 VALERR("return code out of range");
570 if (PyErr_Occurred())
571 stash_exception(pg->exc, "exception from `pgen' handler");
580 static PyObject *pgev_pywrap(const pgev *pg)
584 o = PyObject_New(pgev_pyobj, pgev_pytype);
586 return ((PyObject *)o);
589 int convpgev(PyObject *o, void *p)
594 pg->ev = *PGEV_PG(o);
596 pg->ev.proc = pgev_python;
598 pg->obj = o; Py_INCREF(o);
603 void droppgev(pypgev *pg)
605 if (pg->ev.proc == pgev_python)
606 { assert(pg->ev.ctx == pg); Py_DECREF(pg->obj); }
609 static PyObject *pgmeth_common(PyObject *me, PyObject *arg, int rq)
612 pgev *pg = PGEV_PG(me);
615 if (!PyArg_ParseTuple(arg, "O&", convpgevent, &ev)) goto end;
616 rc = PyInt_FromLong(!pg->proc ? rq : pg->proc(rq, ev, pg->ctx));
621 #define PGMETH(lc, uc) \
622 static PyObject *pgmeth_pg_##lc(PyObject *me, PyObject *arg) \
623 { return pgmeth_common(me, arg, PGEN_##uc); }
632 static PyObject *pgev_stdev(pgen_proc *proc)
633 { pgev pg; pg.proc = proc; pg.ctx = 0; return (pgev_pywrap(&pg)); }
635 static PyMethodDef pgev_pymethods[] = {
636 #define METHNAME(name) pgmeth_##name
637 METH (pg_abort, "E.pg_abort(EV) -> PGRC -- prime generation aborted")
638 METH (pg_done, "E.pg_done(EV) -> PGRC -- prime generation finished")
639 METH (pg_begin, "E.pg_begin(EV) -> PGRC -- commence stepping/testing")
640 METH (pg_try, "E.pg_try(EV) -> PGRC -- found new candidate")
641 METH (pg_pass, "E.pg_pass(EV) -> PGRC -- passed primality test")
642 METH (pg_fail, "E.pg_fail(EV) -> PGRC -- failed primality test")
647 static PyTypeObject pgev_pytype_skel = {
648 PyObject_HEAD_INIT(0) 0, /* Header */
649 "PrimeGenBuiltinHandler", /* @tp_name@ */
650 sizeof(pgev_pyobj), /* @tp_basicsize@ */
651 0, /* @tp_itemsize@ */
653 0, /* @tp_dealloc@ */
655 0, /* @tp_getattr@ */
656 0, /* @tp_setattr@ */
657 0, /* @tp_compare@ */
659 0, /* @tp_as_number@ */
660 0, /* @tp_as_sequence@ */
661 0, /* @tp_as_mapping@ */
665 0, /* @tp_getattro@ */
666 0, /* @tp_setattro@ */
667 0, /* @tp_as_buffer@ */
668 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
672 "Built-in prime-generation event handler, base class.",
674 0, /* @tp_traverse@ */
676 0, /* @tp_richcompare@ */
677 0, /* @tp_weaklistoffset@ */
679 0, /* @tp_iternext@ */
680 pgev_pymethods, /* @tp_methods@ */
681 0, /* @tp_members@ */
685 0, /* @tp_descr_get@ */
686 0, /* @tp_descr_set@ */
687 0, /* @tp_dictoffset@ */
689 PyType_GenericAlloc, /* @tp_alloc@ */
690 abstract_pynew, /* @tp_new@ */
695 static PyObject *pgstep_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
698 pgstep_pyobj *rc = 0;
699 char *kwlist[] = { "step", 0 };
701 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmpw, &s))
703 rc = (pgstep_pyobj *)ty->tp_alloc(ty, 0);
705 rc->pg.proc = pgen_filter;
708 return ((PyObject *)rc);
711 static PyObject *psget_step(PyObject *me, void *hunoz)
712 { return (PyInt_FromLong(PGSTEP_STEP(me))); }
714 static PyGetSetDef pgstep_pygetset[] = {
715 #define GETSETNAME(op, name) ps##op##_##name
716 GET (step, "S.step -> step size for the stepper")
721 static PyTypeObject pgstep_pytype_skel = {
722 PyObject_HEAD_INIT(0) 0, /* Header */
723 "PrimeGenStepper", /* @tp_name@ */
724 sizeof(pgstep_pyobj), /* @tp_basicsize@ */
725 0, /* @tp_itemsize@ */
727 0, /* @tp_dealloc@ */
729 0, /* @tp_getattr@ */
730 0, /* @tp_setattr@ */
731 0, /* @tp_compare@ */
733 0, /* @tp_as_number@ */
734 0, /* @tp_as_sequence@ */
735 0, /* @tp_as_mapping@ */
739 0, /* @tp_getattro@ */
740 0, /* @tp_setattro@ */
741 0, /* @tp_as_buffer@ */
742 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
746 "Simple prime-number stepper with small-factors filter.",
748 0, /* @tp_traverse@ */
750 0, /* @tp_richcompare@ */
751 0, /* @tp_weaklistoffset@ */
753 0, /* @tp_iternext@ */
754 0, /* @tp_methods@ */
755 0, /* @tp_members@ */
756 pgstep_pygetset, /* @tp_getset@ */
759 0, /* @tp_descr_get@ */
760 0, /* @tp_descr_set@ */
761 0, /* @tp_dictoffset@ */
763 PyType_GenericAlloc, /* @tp_alloc@ */
764 pgstep_pynew, /* @tp_new@ */
769 static PyObject *pgjump_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
772 pgjump_pyobj *rc = 0;
773 char *kwlist[] = { "jump", 0 };
775 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &o) ||
776 (fobj = pfilt_pymake(pfilt_pytype, o)) == 0)
778 rc = (pgjump_pyobj *)ty->tp_alloc(ty, 0);
780 rc->j.j = PFILT_F(fobj);
781 rc->pg.proc = pgen_jump;
784 return ((PyObject *)rc);
787 static void pgjump_pydealloc(PyObject *me)
789 Py_DECREF(PGJUMP_FOBJ(me));
793 static PyObject *pjget_jump(PyObject *me, void *hunoz)
794 { RETURN_OBJ(PGJUMP_FOBJ(me)); }
796 static PyGetSetDef pgjump_pygetset[] = {
797 #define GETSETNAME(op, name) pj##op##_##name
798 GET (jump, "S.jump -> jump size for the stepper")
803 static PyTypeObject pgjump_pytype_skel = {
804 PyObject_HEAD_INIT(0) 0, /* Header */
805 "PrimeGenJumper", /* @tp_name@ */
806 sizeof(pgjump_pyobj), /* @tp_basicsize@ */
807 0, /* @tp_itemsize@ */
809 pgjump_pydealloc, /* @tp_dealloc@ */
811 0, /* @tp_getattr@ */
812 0, /* @tp_setattr@ */
813 0, /* @tp_compare@ */
815 0, /* @tp_as_number@ */
816 0, /* @tp_as_sequence@ */
817 0, /* @tp_as_mapping@ */
821 0, /* @tp_getattro@ */
822 0, /* @tp_setattro@ */
823 0, /* @tp_as_buffer@ */
824 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
828 "Stepper for larger steps, with small-factors filter.",
830 0, /* @tp_traverse@ */
832 0, /* @tp_richcompare@ */
833 0, /* @tp_weaklistoffset@ */
835 0, /* @tp_iternext@ */
836 0, /* @tp_methods@ */
837 0, /* @tp_members@ */
838 pgjump_pygetset, /* @tp_getset@ */
841 0, /* @tp_descr_get@ */
842 0, /* @tp_descr_set@ */
843 0, /* @tp_dictoffset@ */
845 PyType_GenericAlloc, /* @tp_alloc@ */
846 pgjump_pynew, /* @tp_new@ */
851 static PyObject *pgtest_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
853 pgtest_pyobj *rc = 0;
854 char *kwlist[] = { 0 };
856 if (!PyArg_ParseTupleAndKeywords(arg, kw, ":new", kwlist)) goto end;
857 rc = (pgtest_pyobj *)ty->tp_alloc(ty, 0);
858 rc->pg.proc = pgen_test;
861 return ((PyObject *)rc);
864 static PyTypeObject pgtest_pytype_skel = {
865 PyObject_HEAD_INIT(0) 0, /* Header */
866 "PrimeGenTester", /* @tp_name@ */
867 sizeof(pgtest_pyobj), /* @tp_basicsize@ */
868 0, /* @tp_itemsize@ */
870 0, /* @tp_dealloc@ */
872 0, /* @tp_getattr@ */
873 0, /* @tp_setattr@ */
874 0, /* @tp_compare@ */
876 0, /* @tp_as_number@ */
877 0, /* @tp_as_sequence@ */
878 0, /* @tp_as_mapping@ */
882 0, /* @tp_getattro@ */
883 0, /* @tp_setattro@ */
884 0, /* @tp_as_buffer@ */
885 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
889 "Rabin-Miller tester.",
891 0, /* @tp_traverse@ */
893 0, /* @tp_richcompare@ */
894 0, /* @tp_weaklistoffset@ */
896 0, /* @tp_iternext@ */
897 0, /* @tp_methods@ */
898 0, /* @tp_members@ */
902 0, /* @tp_descr_get@ */
903 0, /* @tp_descr_set@ */
904 0, /* @tp_dictoffset@ */
906 PyType_GenericAlloc, /* @tp_alloc@ */
907 pgtest_pynew, /* @tp_new@ */
912 /*----- Prime generation functions ----------------------------------------*/
914 void pgenerr(struct excinfo *exc)
916 if (exc->ty) RESTORE_EXCINFO(exc);
917 else PyErr_SetString(PyExc_ValueError, "prime generation failed");
920 static PyObject *meth_pgen(PyObject *me, PyObject *arg, PyObject *kw)
926 pgen_filterctx fc = { 2 };
928 struct excinfo exc = EXCINFO_INIT;
929 pypgev step = { { 0 } }, test = { { 0 } }, evt = { { 0 } };
930 unsigned nsteps = 0, ntests = 0;
931 char *kwlist[] = { "start", "name", "stepper", "tester", "event",
932 "nsteps", "ntests", 0 };
934 step.exc = &exc; step.ev.proc = pgen_filter; step.ev.ctx = &fc;
935 test.exc = &exc; test.ev.proc = pgen_test; test.ev.ctx = &tc;
937 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&O&O&:pgen", kwlist,
938 convmp, &x, &p, convpgev, &step,
939 convpgev, &test, convpgev, &evt,
940 convuint, &nsteps, convuint, &ntests))
942 if (!ntests) ntests = rabin_iters(mp_bits(x));
943 if ((r = pgen(p, MP_NEW, x, evt.ev.proc, evt.ev.ctx,
944 nsteps, step.ev.proc, step.ev.ctx,
945 ntests, test.ev.proc, test.ev.ctx)) == 0)
947 rc = mp_pywrap(r); r = 0;
949 mp_drop(r); mp_drop(x);
950 droppgev(&step); droppgev(&test); droppgev(&evt);
954 static PyObject *meth_strongprime_setup(PyObject *me,
955 PyObject *arg, PyObject *kw)
959 grand *r = &rand_global;
963 struct excinfo exc = EXCINFO_INIT;
964 pypgev evt = { { 0 } };
966 char *kwlist[] = { "nbits", "name", "event", "rng", "nsteps", 0 };
969 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&", kwlist,
970 convuint, &nbits, &name,
971 convpgev, &evt, convgrand, &r,
974 if ((x = strongprime_setup(name, MP_NEW, &f, nbits,
975 r, n, evt.ev.proc, evt.ev.ctx)) == 0)
977 rc = Py_BuildValue("(NN)", mp_pywrap(x), pfilt_pywrap(&f));
985 static PyObject *meth_strongprime(PyObject *me, PyObject *arg, PyObject *kw)
988 grand *r = &rand_global;
992 struct excinfo exc = EXCINFO_INIT;
993 pypgev evt = { { 0 } };
995 char *kwlist[] = { "nbits", "name", "event", "rng", "nsteps", 0 };
998 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&", kwlist,
999 convuint, &nbits, &name,
1000 convpgev, &evt, convgrand, &r,
1003 if ((x = strongprime(name, MP_NEW, nbits,
1004 r, n, evt.ev.proc, evt.ev.ctx)) == 0)
1014 static PyObject *meth_limlee(PyObject *me, PyObject *arg, PyObject *kw)
1017 struct excinfo exc = EXCINFO_INIT;
1018 pypgev ie = { { 0 } }, oe = { { 0 } };
1020 grand *r = &rand_global;
1023 PyObject *rc = 0, *vec;
1024 char *kwlist[] = { "pbits", "qbits", "name", "event", "ievent",
1025 "rng", "nsteps", 0 };
1028 ie.exc = oe.exc = &exc;
1029 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&|sO&O&O&O&:limlee", kwlist,
1030 convuint, &pl, convuint, &ql,
1031 &p, convpgev, &oe, convpgev, &ie,
1032 convgrand, &r, convuint, &on))
1034 if ((x = limlee(p, MP_NEW, MP_NEW, ql, pl, r, on,
1035 oe.ev.proc, oe.ev.ctx, ie.ev.proc, ie.ev.ctx,
1038 vec = PyList_New(nf);
1039 for (i = 0; i < nf; i++)
1040 PyList_SetItem(vec, i, mp_pywrap(v[i]));
1042 rc = Py_BuildValue("(NN)", mp_pywrap(x), vec);
1044 droppgev(&oe); droppgev(&ie);
1048 /*----- Global stuff ------------------------------------------------------*/
1050 static PyMethodDef methods[] = {
1051 #define METHNAME(name) meth_##name
1052 METH (_PrimeFilter_smallfactor, "smallfactor(X) -> PGRC")
1053 METH (_RabinMiller_iters, "iters(NBITS) -> NITERS")
1055 pgen(START, [name = 'p'[, [stepper = PrimeGenStepper(2)],\n\
1056 [tester = PrimeGenTester()], [event = pgen_nullev],\n\
1057 [nsteps = 0], [ntests = RabinMiller.iters(START.nbits)]) -> P")
1058 KWMETH(strongprime_setup, "\
1059 strongprime_setup(NBITS, [name = 'p'], [event = pgen_nullev],\n\
1060 [rng = rand], [nsteps = 0]) -> (START, JUMP)")
1061 KWMETH(strongprime, "\
1062 strongprime(NBITS, [name = 'p'], [event = pgen_nullev],\n\
1063 [rng = rand], [nsteps = 0]) -> P")
1065 limlee(PBITS, QBITS, [name = 'p'], [event = pgen_nullev],\n\
1066 [ievent = pgen_nullev], [rng = rand], [nsteps = 0]) -> (P, [Q, ...])")
1071 void pgen_pyinit(void)
1073 INITTYPE(pfilt, root);
1074 INITTYPE(rabin, root);
1075 INITTYPE(pgevent, root);
1076 INITTYPE(pgev, root);
1077 INITTYPE(pgstep, pgev);
1078 INITTYPE(pgjump, pgev);
1079 INITTYPE(pgtest, pgev);
1080 addmethods(methods);
1083 static PyObject *obj;
1085 void pgen_pyinsert(PyObject *mod)
1087 INSERT("PrimeFilter", pfilt_pytype);
1088 INSERT("RabinMiller", rabin_pytype);
1089 INSERT("PrimeGenEvent", pgevent_pytype);
1090 INSERT("PrimeGenBuiltinHandler", pgev_pytype);
1091 INSERT("PrimeGenStepper", pgstep_pytype);
1092 INSERT("PrimeGenJumper", pgjump_pytype);
1093 INSERT("PrimeGenTester", pgtest_pytype);
1094 INSERT("pgen_nullev", obj = pgev_stdev(0));
1095 INSERT("pgen_stdev", pgev_stdev(pgen_ev));
1096 INSERT("pgen_spinev", pgev_stdev(pgen_evspin));
1097 INSERT("pgen_subev", pgev_stdev(pgen_subev));
1100 /*----- That's all, folks -------------------------------------------------*/