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 static const char *const 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
*pfmeth_smallfactor(PyObject
*me
, PyObject
*arg
)
108 if (!PyArg_ParseTuple(arg
, "O&:smallfactor", 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
);
129 static PyObject
*pfilt_pylong(PyObject
*me
)
130 { return (mp_topylong(PFILT_F(me
)->m
)); }
133 static PyObject
*pfget_x(PyObject
*me
, void *hunoz
)
134 { return (mp_pywrap(MP_COPY(PFILT_F(me
)->m
))); }
136 static PyObject
*pfget_status(PyObject
*me
, void *hunoz
)
137 { return (PyInt_FromLong(PFILT_ST(me
))); }
139 static const PyGetSetDef pfilt_pygetset
[] = {
140 #define GETSETNAME(op, name) pf##op##_##name
141 GET (x
, "F.x -> current position of filter")
142 GET (status
, "F.status -> primality status of filter")
147 static const PyMethodDef pfilt_pymethods
[] = {
148 #define METHNAME(name) pfmeth_##name
149 METH (step
, "F.step(N)")
150 METH (muladd
, "F.muladd(M, A)")
151 METH (jump
, "F.jump(FF)")
152 SMTH (smallfactor
, "smallfactor(X) -> PGST")
157 static const PyNumberMethods pfilt_pynumber
= {
159 0, /* @nb_subtract@ */
160 0, /* @nb_multiply@ */
164 0, /* @nb_remainder@ */
167 0, /* @nb_negative@ */
168 0, /* @nb_positive@ */
169 0, /* @nb_absolute@ */
170 pfilt_pynonzerop
, /* @nb_nonzero@ */
180 pfilt_pyint
, /* @nb_int@ */
181 PY23(pfilt_pylong
, 0), /* @nb_long@ */
188 0, /* @nb_inplace_add@ */
189 0, /* @nb_inplace_subtract@ */
190 0, /* @nb_inplace_multiply@ */
192 0, /* @nb_inplace_divide@ */
194 0, /* @nb_inplace_remainder@ */
195 0, /* @nb_inplace_power@ */
196 0, /* @nb_inplace_lshift@ */
197 0, /* @nb_inplace_rshift@ */
198 0, /* @nb_inplace_and@ */
199 0, /* @nb_inplace_xor@ */
200 0, /* @nb_inplace_or@ */
202 0, /* @nb_floor_divide@ */
203 0, /* @nb_true_divide@ */
204 0, /* @nb_inplace_floor_divide@ */
205 0, /* @nb_inplace_true_divide@ */
208 static const PyTypeObject pfilt_pytype_skel
= {
209 PyVarObject_HEAD_INIT(0, 0) /* Header */
210 "PrimeFilter", /* @tp_name@ */
211 sizeof(pfilt_pyobj
), /* @tp_basicsize@ */
212 0, /* @tp_itemsize@ */
214 pfilt_pydealloc
, /* @tp_dealloc@ */
216 0, /* @tp_getattr@ */
217 0, /* @tp_setattr@ */
218 0, /* @tp_compare@ */
220 PYNUMBER(pfilt
), /* @tp_as_number@ */
221 0, /* @tp_as_sequence@ */
222 0, /* @tp_as_mapping@ */
226 0, /* @tp_getattro@ */
227 0, /* @tp_setattro@ */
228 0, /* @tp_as_buffer@ */
229 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
233 "PrimeFilter(X): small-primes filter.",
235 0, /* @tp_traverse@ */
237 0, /* @tp_richcompare@ */
238 0, /* @tp_weaklistoffset@ */
240 0, /* @tp_iternext@ */
241 PYMETHODS(pfilt
), /* @tp_methods@ */
242 0, /* @tp_members@ */
243 PYGETSET(pfilt
), /* @tp_getset@ */
246 0, /* @tp_descr_get@ */
247 0, /* @tp_descr_set@ */
248 0, /* @tp_dictoffset@ */
250 PyType_GenericAlloc
, /* @tp_alloc@ */
251 pfilt_pynew
, /* @tp_new@ */
256 /*----- Rabin-Miller testing ----------------------------------------------*/
258 typedef struct rabin_pyobj
{
263 static PyTypeObject
*rabin_pytype
;
264 #define RABIN_R(o) (&((rabin_pyobj *)(o))->r)
266 static PyObject
*rabin_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
270 static const char *const kwlist
[] = { "x", 0 };
272 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&:new", KWLIST
, convmp
, &x
))
274 if (!MP_POSP(x
) || MP_EVENP(x
)) VALERR("must be positive and odd");
275 o
= (rabin_pyobj
*)ty
->tp_alloc(ty
, 0);
276 rabin_create(&o
->r
, x
);
278 return ((PyObject
*)o
);
281 static void rabin_pydealloc(PyObject
*me
)
283 rabin_destroy(RABIN_R(me
));
287 static PyObject
*rmeth_test(PyObject
*me
, PyObject
*arg
)
292 if (!PyArg_ParseTuple(arg
, "O&:test", convmp
, &w
)) goto end
;
293 rc
= PyInt_FromLong(rabin_test(RABIN_R(me
), w
));
299 static PyObject
*rmeth_rtest(PyObject
*me
, PyObject
*arg
)
304 if (!PyArg_ParseTuple(arg
, "O&:rtest", convmp
, &w
)) goto end
;
305 rc
= PyInt_FromLong(rabin_rtest(RABIN_R(me
), w
));
311 static PyObject
*rget_niters(PyObject
*me
, void *hunoz
)
312 { return (PyInt_FromLong(rabin_iters(mp_bits(RABIN_R(me
)->mm
.m
)))); }
314 static PyObject
*rget_x(PyObject
*me
, void *hunoz
)
315 { return (mp_pywrap(MP_COPY(RABIN_R(me
)->mm
.m
))); }
317 static PyObject
*rmeth_iters(PyObject
*me
, PyObject
*arg
)
321 if (!PyArg_ParseTuple(arg
, "O&:iters", convuint
, &n
)) return (0);
322 return (PyInt_FromLong(rabin_iters(n
)));
325 static const PyGetSetDef rabin_pygetset
[] = {
326 #define GETSETNAME(op, name) r##op##_##name
327 GET (x
, "R.x -> number under test")
328 GET (niters
, "R.niters -> suggested number of tests")
333 static const PyMethodDef rabin_pymethods
[] = {
334 #define METHNAME(name) rmeth_##name
335 METH (test
, "R.test(W) -> PGST")
336 METH (rtest
, "R.rtest(W) -> PGST")
337 SMTH (iters
, "iters(NBITS) -> NITERS")
342 static const PyTypeObject rabin_pytype_skel
= {
343 PyVarObject_HEAD_INIT(0, 0) /* Header */
344 "RabinMiller", /* @tp_name@ */
345 sizeof(rabin_pyobj
), /* @tp_basicsize@ */
346 0, /* @tp_itemsize@ */
348 rabin_pydealloc
, /* @tp_dealloc@ */
350 0, /* @tp_getattr@ */
351 0, /* @tp_setattr@ */
352 0, /* @tp_compare@ */
354 0, /* @tp_as_number@ */
355 0, /* @tp_as_sequence@ */
356 0, /* @tp_as_mapping@ */
360 0, /* @tp_getattro@ */
361 0, /* @tp_setattro@ */
362 0, /* @tp_as_buffer@ */
363 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
367 "RabinMiller(X): Rabin-Miller strong primality test.",
369 0, /* @tp_traverse@ */
371 0, /* @tp_richcompare@ */
372 0, /* @tp_weaklistoffset@ */
374 0, /* @tp_iternext@ */
375 PYMETHODS(rabin
), /* @tp_methods@ */
376 0, /* @tp_members@ */
377 PYGETSET(rabin
), /* @tp_getset@ */
380 0, /* @tp_descr_get@ */
381 0, /* @tp_descr_set@ */
382 0, /* @tp_dictoffset@ */
384 PyType_GenericAlloc
, /* @tp_alloc@ */
385 rabin_pynew
, /* @tp_new@ */
390 /*----- Events ------------------------------------------------------------*/
392 typedef struct pgevent_pyobj
{
398 static PyTypeObject
*pgevent_pytype
;
399 #define PGEVENT_EV(o) (((pgevent_pyobj *)(o))->ev)
401 static PyObject
*pgevent_pywrap(pgen_event
*ev
)
403 pgevent_pyobj
*o
= PyObject_New(pgevent_pyobj
, pgevent_pytype
);
404 o
->ev
= ev
; o
->r
= 0;
405 return ((PyObject
*)o
);
408 static CONVFUNC(pgevent
, pgen_event
*, PGEVENT_EV
)
410 static void pgevent_kill(PyObject
*me
)
412 pgevent_pyobj
*ev
= (pgevent_pyobj
*)me
;
415 if (ev
->r
) GRAND_R(ev
->r
) = 0;
418 static void pgevent_pydealloc(PyObject
*me
)
420 pgevent_pyobj
*ev
= (pgevent_pyobj
*)me
;
421 Py_XDECREF(ev
->r
); FREEOBJ(me
);
424 #define PGEVENT_CHECK(me) do { \
425 if (!PGEVENT_EV(me)) { \
426 PyErr_SetString(PyExc_ValueError, "event object is no longer valid"); \
431 static PyObject
*peget_name(PyObject
*me
, void *hunoz
)
432 { PGEVENT_CHECK(me
); return (TEXT_FROMSTR(PGEVENT_EV(me
)->name
)); }
434 static PyObject
*peget_x(PyObject
*me
, void *hunoz
)
435 { PGEVENT_CHECK(me
); return (mp_pywrap(MP_COPY(PGEVENT_EV(me
)->m
))); }
437 static PyObject
*peget_steps(PyObject
*me
, void *hunoz
)
438 { PGEVENT_CHECK(me
); return (PyInt_FromLong(PGEVENT_EV(me
)->steps
)); }
440 static PyObject
*peget_tests(PyObject
*me
, void *hunoz
)
441 { PGEVENT_CHECK(me
); return (PyInt_FromLong(PGEVENT_EV(me
)->tests
)); }
443 static PyObject
*peget_rng(PyObject
*me
, void *hunoz
)
445 pgevent_pyobj
*ev
= (pgevent_pyobj
*)me
;
448 if (!ev
->r
) ev
->r
= grand_pywrap(ev
->ev
->r
, 0);
449 Py_INCREF(ev
->r
); return ((PyObject
*)ev
->r
);
452 static int peset_x(PyObject
*me
, PyObject
*xobj
, void *hunoz
)
455 pgen_event
*ev
= PGEVENT_EV(me
);
457 if (!xobj
) NIERR("__del__");
459 if ((x
= getmp(xobj
)) == 0) goto end
;
468 static const PyGetSetDef pgevent_pygetset
[] = {
469 #define GETSETNAME(op, name) pe##op##_##name
470 GET (name
, "EV.name -> value being generated")
471 GETSET(x
, "EV.x -> value under test")
472 GET (steps
, "EV.steps -> number of steps left")
473 GET (tests
, "EV.tests -> tests before passing")
474 GET (rng
, "EV.rng -> (noncrypto) random number generator")
479 static const PyTypeObject pgevent_pytype_skel
= {
480 PyVarObject_HEAD_INIT(0, 0) /* Header */
481 "PrimeGenEvent", /* @tp_name@ */
482 sizeof(pgevent_pyobj
), /* @tp_basicsize@ */
483 0, /* @tp_itemsize@ */
485 pgevent_pydealloc
, /* @tp_dealloc@ */
487 0, /* @tp_getattr@ */
488 0, /* @tp_setattr@ */
489 0, /* @tp_compare@ */
491 0, /* @tp_as_number@ */
492 0, /* @tp_as_sequence@ */
493 0, /* @tp_as_mapping@ */
497 0, /* @tp_getattro@ */
498 0, /* @tp_setattro@ */
499 0, /* @tp_as_buffer@ */
500 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
504 "Prime-generation event.",
506 0, /* @tp_traverse@ */
508 0, /* @tp_richcompare@ */
509 0, /* @tp_weaklistoffset@ */
511 0, /* @tp_iternext@ */
512 0, /* @tp_methods@ */
513 0, /* @tp_members@ */
514 PYGETSET(pgevent
), /* @tp_getset@ */
517 0, /* @tp_descr_get@ */
518 0, /* @tp_descr_set@ */
519 0, /* @tp_dictoffset@ */
521 PyType_GenericAlloc
, /* @tp_alloc@ */
522 abstract_pynew
, /* @tp_new@ */
527 /*----- Event handlers ----------------------------------------------------*/
529 PyTypeObject
*pgev_pytype
;
531 typedef struct pgstep_pyobj
{
536 static PyTypeObject
*pgstep_pytype
;
537 #define PGSTEP_STEP(o) (((pgstep_pyobj *)(o))->f.step)
539 typedef struct pgjump_pyobj
{
545 static PyTypeObject
*pgjump_pytype
;
546 #define PGJUMP_FOBJ(o) (((pgjump_pyobj *)(o))->fobj)
547 #define PGJUMP_J(o) (&((pgjump_pyobj *)(o))->j)
549 typedef struct pgtest_pyobj
{
554 static PyTypeObject
*pgtest_pytype
;
556 static int pgev_python(int rq
, pgen_event
*ev
, void *p
)
563 static const char *const meth
[] =
564 { "pg_abort", "pg_done", "pg_begin", "pg_try", "pg_fail", "pg_pass" };
567 if (rq
> N(meth
)) SYSERR("event code out of range");
568 pyev
= pgevent_pywrap(ev
);
569 if ((rc
= PyObject_CallMethod(pg
->obj
, (/*unconst*/ char *)meth
[rq
],
574 else if ((l
= PyInt_AsLong(rc
)) == -1 && PyErr_Occurred())
576 else if (l
< PGEN_ABORT
|| l
> PGEN_PASS
)
577 VALERR("return code out of range");
581 if (PyErr_Occurred())
582 stash_exception(pg
->exc
, "exception from `pgen' handler");
591 static PyObject
*pgev_pywrap(const pgev
*pg
)
595 o
= PyObject_New(pgev_pyobj
, pgev_pytype
);
597 return ((PyObject
*)o
);
600 int convpgev(PyObject
*o
, void *p
)
605 pg
->ev
= *PGEV_PG(o
);
607 pg
->ev
.proc
= pgev_python
;
609 pg
->obj
= o
; Py_INCREF(o
);
614 void droppgev(pypgev
*pg
)
616 if (pg
->ev
.proc
== pgev_python
)
617 { assert(pg
->ev
.ctx
== pg
); Py_DECREF(pg
->obj
); }
620 static PyObject
*pgmeth_common(PyObject
*me
, PyObject
*arg
, int rq
)
623 pgev
*pg
= PGEV_PG(me
);
626 if (!PyArg_ParseTuple(arg
, "O&", convpgevent
, &ev
)) goto end
;
627 rc
= PyInt_FromLong(!pg
->proc ? rq
: pg
->proc(rq
, ev
, pg
->ctx
));
632 #define PGMETH(lc, uc) \
633 static PyObject *pgmeth_pg_##lc(PyObject *me, PyObject *arg) \
634 { return pgmeth_common(me, arg, PGEN_##uc); }
643 static PyObject
*pgev_stdev(pgen_proc
*proc
)
644 { pgev pg
; pg
.proc
= proc
; pg
.ctx
= 0; return (pgev_pywrap(&pg
)); }
646 static const PyMethodDef pgev_pymethods
[] = {
647 #define METHNAME(name) pgmeth_##name
648 METH (pg_abort
, "E.pg_abort(EV) -> PGST -- prime generation aborted")
649 METH (pg_done
, "E.pg_done(EV) -> PGST -- prime generation finished")
650 METH (pg_begin
, "E.pg_begin(EV) -> PGST -- commence stepping/testing")
651 METH (pg_try
, "E.pg_try(EV) -> PGST -- found new candidate")
652 METH (pg_pass
, "E.pg_pass(EV) -> PGST -- passed primality test")
653 METH (pg_fail
, "E.pg_fail(EV) -> PGST -- failed primality test")
658 static const PyTypeObject pgev_pytype_skel
= {
659 PyVarObject_HEAD_INIT(0, 0) /* Header */
660 "PrimeGenBuiltinHandler", /* @tp_name@ */
661 sizeof(pgev_pyobj
), /* @tp_basicsize@ */
662 0, /* @tp_itemsize@ */
664 0, /* @tp_dealloc@ */
666 0, /* @tp_getattr@ */
667 0, /* @tp_setattr@ */
668 0, /* @tp_compare@ */
670 0, /* @tp_as_number@ */
671 0, /* @tp_as_sequence@ */
672 0, /* @tp_as_mapping@ */
676 0, /* @tp_getattro@ */
677 0, /* @tp_setattro@ */
678 0, /* @tp_as_buffer@ */
679 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
683 "Built-in prime-generation event handler, base class.",
685 0, /* @tp_traverse@ */
687 0, /* @tp_richcompare@ */
688 0, /* @tp_weaklistoffset@ */
690 0, /* @tp_iternext@ */
691 PYMETHODS(pgev
), /* @tp_methods@ */
692 0, /* @tp_members@ */
696 0, /* @tp_descr_get@ */
697 0, /* @tp_descr_set@ */
698 0, /* @tp_dictoffset@ */
700 PyType_GenericAlloc
, /* @tp_alloc@ */
701 abstract_pynew
, /* @tp_new@ */
706 static PyObject
*pgstep_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
709 pgstep_pyobj
*rc
= 0;
710 static const char *const kwlist
[] = { "step", 0 };
712 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&:new", KWLIST
, convmpw
, &s
))
714 rc
= (pgstep_pyobj
*)ty
->tp_alloc(ty
, 0);
716 rc
->pg
.proc
= pgen_filter
;
719 return ((PyObject
*)rc
);
722 static PyObject
*psget_step(PyObject
*me
, void *hunoz
)
723 { return (PyInt_FromLong(PGSTEP_STEP(me
))); }
725 static const PyGetSetDef pgstep_pygetset
[] = {
726 #define GETSETNAME(op, name) ps##op##_##name
727 GET (step
, "S.step -> step size for the stepper")
732 static const PyTypeObject pgstep_pytype_skel
= {
733 PyVarObject_HEAD_INIT(0, 0) /* Header */
734 "PrimeGenStepper", /* @tp_name@ */
735 sizeof(pgstep_pyobj
), /* @tp_basicsize@ */
736 0, /* @tp_itemsize@ */
738 0, /* @tp_dealloc@ */
740 0, /* @tp_getattr@ */
741 0, /* @tp_setattr@ */
742 0, /* @tp_compare@ */
744 0, /* @tp_as_number@ */
745 0, /* @tp_as_sequence@ */
746 0, /* @tp_as_mapping@ */
750 0, /* @tp_getattro@ */
751 0, /* @tp_setattro@ */
752 0, /* @tp_as_buffer@ */
753 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
757 "PrimeGenStepper(STEP): simple stepper with small-factors filter.",
759 0, /* @tp_traverse@ */
761 0, /* @tp_richcompare@ */
762 0, /* @tp_weaklistoffset@ */
764 0, /* @tp_iternext@ */
765 0, /* @tp_methods@ */
766 0, /* @tp_members@ */
767 PYGETSET(pgstep
), /* @tp_getset@ */
770 0, /* @tp_descr_get@ */
771 0, /* @tp_descr_set@ */
772 0, /* @tp_dictoffset@ */
774 PyType_GenericAlloc
, /* @tp_alloc@ */
775 pgstep_pynew
, /* @tp_new@ */
780 static PyObject
*pgjump_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
783 pgjump_pyobj
*rc
= 0;
784 static const char *const kwlist
[] = { "jump", 0 };
786 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O:new", KWLIST
, &o
) ||
787 (fobj
= pfilt_pymake(pfilt_pytype
, o
)) == 0)
789 rc
= (pgjump_pyobj
*)ty
->tp_alloc(ty
, 0);
791 rc
->j
.j
= PFILT_F(fobj
);
792 rc
->pg
.proc
= pgen_jump
;
795 return ((PyObject
*)rc
);
798 static void pgjump_pydealloc(PyObject
*me
)
800 Py_DECREF(PGJUMP_FOBJ(me
));
804 static PyObject
*pjget_jump(PyObject
*me
, void *hunoz
)
805 { RETURN_OBJ(PGJUMP_FOBJ(me
)); }
807 static const PyGetSetDef pgjump_pygetset
[] = {
808 #define GETSETNAME(op, name) pj##op##_##name
809 GET (jump
, "S.jump -> jump size for the stepper")
814 static const PyTypeObject pgjump_pytype_skel
= {
815 PyVarObject_HEAD_INIT(0, 0) /* Header */
816 "PrimeGenJumper", /* @tp_name@ */
817 sizeof(pgjump_pyobj
), /* @tp_basicsize@ */
818 0, /* @tp_itemsize@ */
820 pgjump_pydealloc
, /* @tp_dealloc@ */
822 0, /* @tp_getattr@ */
823 0, /* @tp_setattr@ */
824 0, /* @tp_compare@ */
826 0, /* @tp_as_number@ */
827 0, /* @tp_as_sequence@ */
828 0, /* @tp_as_mapping@ */
832 0, /* @tp_getattro@ */
833 0, /* @tp_setattro@ */
834 0, /* @tp_as_buffer@ */
835 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
839 "PrimeGenJumper(JUMP): "
840 "stepper for larger steps with small-factors filter.",
842 0, /* @tp_traverse@ */
844 0, /* @tp_richcompare@ */
845 0, /* @tp_weaklistoffset@ */
847 0, /* @tp_iternext@ */
848 0, /* @tp_methods@ */
849 0, /* @tp_members@ */
850 PYGETSET(pgjump
), /* @tp_getset@ */
853 0, /* @tp_descr_get@ */
854 0, /* @tp_descr_set@ */
855 0, /* @tp_dictoffset@ */
857 PyType_GenericAlloc
, /* @tp_alloc@ */
858 pgjump_pynew
, /* @tp_new@ */
863 static PyObject
*pgtest_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
865 pgtest_pyobj
*rc
= 0;
866 static const char *const kwlist
[] = { 0 };
868 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, ":new", KWLIST
)) goto end
;
869 rc
= (pgtest_pyobj
*)ty
->tp_alloc(ty
, 0);
870 rc
->pg
.proc
= pgen_test
;
873 return ((PyObject
*)rc
);
876 static const PyTypeObject pgtest_pytype_skel
= {
877 PyVarObject_HEAD_INIT(0, 0) /* Header */
878 "PrimeGenTester", /* @tp_name@ */
879 sizeof(pgtest_pyobj
), /* @tp_basicsize@ */
880 0, /* @tp_itemsize@ */
882 0, /* @tp_dealloc@ */
884 0, /* @tp_getattr@ */
885 0, /* @tp_setattr@ */
886 0, /* @tp_compare@ */
888 0, /* @tp_as_number@ */
889 0, /* @tp_as_sequence@ */
890 0, /* @tp_as_mapping@ */
894 0, /* @tp_getattro@ */
895 0, /* @tp_setattro@ */
896 0, /* @tp_as_buffer@ */
897 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
901 "PrimeGenTester(): Rabin-Miller tester.",
903 0, /* @tp_traverse@ */
905 0, /* @tp_richcompare@ */
906 0, /* @tp_weaklistoffset@ */
908 0, /* @tp_iternext@ */
909 0, /* @tp_methods@ */
910 0, /* @tp_members@ */
914 0, /* @tp_descr_get@ */
915 0, /* @tp_descr_set@ */
916 0, /* @tp_dictoffset@ */
918 PyType_GenericAlloc
, /* @tp_alloc@ */
919 pgtest_pynew
, /* @tp_new@ */
924 /*----- Prime generation functions ----------------------------------------*/
926 void pgenerr(struct excinfo
*exc
)
928 if (exc
->ty
) RESTORE_EXCINFO(exc
);
929 else PyErr_SetString(PyExc_ValueError
, "prime generation failed");
932 static PyObject
*meth_pgen(PyObject
*me
, PyObject
*arg
, PyObject
*kw
)
938 pgen_filterctx fc
= { 2 };
940 struct excinfo exc
= EXCINFO_INIT
;
941 pypgev step
= { { 0 } }, test
= { { 0 } }, evt
= { { 0 } };
942 unsigned nsteps
= 0, ntests
= 0;
943 static const char *const kwlist
[] =
944 { "start", "name", "stepper", "tester", "event", "nsteps", "ntests", 0 };
946 step
.exc
= &exc
; step
.ev
.proc
= pgen_filter
; step
.ev
.ctx
= &fc
;
947 test
.exc
= &exc
; test
.ev
.proc
= pgen_test
; test
.ev
.ctx
= &tc
;
949 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&|sO&O&O&O&O&:pgen", KWLIST
,
950 convmp
, &x
, &p
, convpgev
, &step
,
951 convpgev
, &test
, convpgev
, &evt
,
952 convuint
, &nsteps
, convuint
, &ntests
))
954 if (!ntests
) ntests
= rabin_iters(mp_bits(x
));
955 if ((r
= pgen(p
, MP_NEW
, x
, evt
.ev
.proc
, evt
.ev
.ctx
,
956 nsteps
, step
.ev
.proc
, step
.ev
.ctx
,
957 ntests
, test
.ev
.proc
, test
.ev
.ctx
)) == 0)
959 rc
= mp_pywrap(r
); r
= 0;
961 mp_drop(r
); mp_drop(x
);
962 droppgev(&step
); droppgev(&test
); droppgev(&evt
);
966 static PyObject
*meth_strongprime_setup(PyObject
*me
,
967 PyObject
*arg
, PyObject
*kw
)
971 grand
*r
= &rand_global
;
975 struct excinfo exc
= EXCINFO_INIT
;
976 pypgev evt
= { { 0 } };
978 static const char *const kwlist
[] =
979 { "nbits", "name", "event", "rng", "nsteps", 0 };
982 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&|sO&O&O&", KWLIST
,
983 convuint
, &nbits
, &name
,
984 convpgev
, &evt
, convgrand
, &r
,
987 if ((x
= strongprime_setup(name
, MP_NEW
, &f
, nbits
,
988 r
, n
, evt
.ev
.proc
, evt
.ev
.ctx
)) == 0)
990 rc
= Py_BuildValue("(NN)", mp_pywrap(x
), pfilt_pywrap(&f
));
998 static PyObject
*meth_strongprime(PyObject
*me
, PyObject
*arg
, PyObject
*kw
)
1001 grand
*r
= &rand_global
;
1005 struct excinfo exc
= EXCINFO_INIT
;
1006 pypgev evt
= { { 0 } };
1008 static const char *const kwlist
[] =
1009 { "nbits", "name", "event", "rng", "nsteps", 0 };
1012 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&|sO&O&O&", KWLIST
,
1013 convuint
, &nbits
, &name
,
1014 convpgev
, &evt
, convgrand
, &r
,
1017 if ((x
= strongprime(name
, MP_NEW
, nbits
,
1018 r
, n
, evt
.ev
.proc
, evt
.ev
.ctx
)) == 0)
1028 static PyObject
*meth_limlee(PyObject
*me
, PyObject
*arg
, PyObject
*kw
)
1031 struct excinfo exc
= EXCINFO_INIT
;
1032 pypgev ie
= { { 0 } }, oe
= { { 0 } };
1034 grand
*r
= &rand_global
;
1037 PyObject
*rc
= 0, *vec
;
1038 static const char *const kwlist
[] =
1039 { "pbits", "qbits", "name", "event", "ievent", "rng", "nsteps", 0 };
1042 ie
.exc
= oe
.exc
= &exc
;
1043 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&O&|sO&O&O&O&:limlee", KWLIST
,
1044 convuint
, &pl
, convuint
, &ql
,
1045 &p
, convpgev
, &oe
, convpgev
, &ie
,
1046 convgrand
, &r
, convuint
, &on
))
1048 if ((x
= limlee(p
, MP_NEW
, MP_NEW
, ql
, pl
, r
, on
,
1049 oe
.ev
.proc
, oe
.ev
.ctx
, ie
.ev
.proc
, ie
.ev
.ctx
,
1052 vec
= PyList_New(nf
);
1053 for (i
= 0; i
< nf
; i
++)
1054 PyList_SET_ITEM(vec
, i
, mp_pywrap(v
[i
]));
1056 rc
= Py_BuildValue("(NN)", mp_pywrap(x
), vec
);
1058 droppgev(&oe
); droppgev(&ie
);
1062 /*----- Global stuff ------------------------------------------------------*/
1064 static const struct nameval consts
[] = {
1065 CONST(PGEN_PASS
), CONST(PGEN_FAIL
), CONST(PGEN_BEGIN
), CONST(PGEN_TRY
),
1066 CONST(PGEN_DONE
), CONST(PGEN_ABORT
),
1070 static const PyMethodDef methods
[] = {
1071 #define METHNAME(name) meth_##name
1073 "pgen(START, [name = 'p'], [stepper = PrimeGenStepper(2)],\n"
1074 " [tester = PrimeGenTester()], [event = pgen_nullev],\n"
1075 " [nsteps = 0], [ntests = RabinMiller.iters(START.nbits)]) -> P")
1076 KWMETH(strongprime_setup
,
1077 "strongprime_setup(NBITS, [name = 'p'], [event = pgen_nullev],\n"
1078 " [rng = rand], [nsteps = 0]) -> (START, JUMP)")
1080 "strongprime(NBITS, [name = 'p'], [event = pgen_nullev],\n"
1081 " [rng = rand], [nsteps = 0]) -> P")
1083 "limlee(PBITS, QBITS, [name = 'p'], [event = pgen_nullev],\n"
1084 " [ievent = pgen_nullev], [rng = rand], [nsteps = 0]) "
1090 void pgen_pyinit(void)
1092 INITTYPE(pfilt
, root
);
1093 INITTYPE(rabin
, root
);
1094 INITTYPE(pgevent
, root
);
1095 INITTYPE(pgev
, root
);
1096 INITTYPE(pgstep
, pgev
);
1097 INITTYPE(pgjump
, pgev
);
1098 INITTYPE(pgtest
, pgev
);
1099 addmethods(methods
);
1102 static PyObject
*obj
;
1104 void pgen_pyinsert(PyObject
*mod
)
1106 INSERT("PrimeFilter", pfilt_pytype
);
1107 INSERT("RabinMiller", rabin_pytype
);
1108 INSERT("PrimeGenEvent", pgevent_pytype
);
1109 INSERT("PrimeGenBuiltinHandler", pgev_pytype
);
1110 INSERT("PrimeGenStepper", pgstep_pytype
);
1111 INSERT("PrimeGenJumper", pgjump_pytype
);
1112 INSERT("PrimeGenTester", pgtest_pytype
);
1113 INSERT("pgen_nullev", obj
= pgev_stdev(0));
1114 INSERT("pgen_stdev", pgev_stdev(pgen_ev
));
1115 INSERT("pgen_spinev", pgev_stdev(pgen_evspin
));
1116 INSERT("pgen_subev", pgev_stdev(pgen_subev
));
1117 setconstants(mod
, consts
);
1120 /*----- That's all, folks -------------------------------------------------*/