5 * Prime number generation
7 * (c) 2005 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of the Python interface to Catacomb.
14 * Catacomb/Python is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (at your option) any later version.
19 * Catacomb/Python is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
24 * You should have received a copy of the GNU General Public License
25 * along with Catacomb/Python; if not, write to the Free Software Foundation,
26 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
29 /*----- Header files ------------------------------------------------------*/
31 #include "catacomb-python.h"
33 /*----- Filters -----------------------------------------------------------*/
35 PyTypeObject
*pfilt_pytype
;
37 static PyObject
*pfilt_pywrap(pfilt
*f
)
40 o
= PyObject_New(pfilt_pyobj
, pfilt_pytype
);
42 o
->st
= pfilt_step(f
, 0);
43 return ((PyObject
*)o
);
46 static PyObject
*pfilt_pymake(PyTypeObject
*ty
, PyObject
*xobj
)
51 if (PFILT_PYCHECK(xobj
)) RETURN_OBJ(xobj
);
52 if ((x
= getmp(xobj
)) == 0) goto end
;
53 o
= (pfilt_pyobj
*)ty
->tp_alloc(ty
, 0);
54 o
->st
= pfilt_create(&o
->f
, x
);
57 return ((PyObject
*)o
);
60 static PyObject
*pfilt_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
62 char *kwlist
[] = { "x", 0 };
65 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O:new", kwlist
, &xobj
))
67 return (pfilt_pymake(ty
, xobj
));
70 static void pfilt_pydealloc(PyObject
*me
)
71 { pfilt_destroy(PFILT_F(me
)); FREEOBJ(me
); }
73 static PyObject
*pfmeth_step(PyObject
*me
, PyObject
*arg
)
77 if (!PyArg_ParseTuple(arg
, "O&:step", convmpw
, &x
)) return (0);
78 PFILT_ST(me
) = pfilt_step(PFILT_F(me
), x
);
82 static PyObject
*pfmeth_muladd(PyObject
*me
, PyObject
*arg
)
87 if (!PyArg_ParseTuple(arg
, "O&O&:muladd", convmpw
, &m
, convmpw
, &a
))
89 o
= PyObject_New(pfilt_pyobj
, pfilt_pytype
);
90 o
->st
= pfilt_muladd(&o
->f
, PFILT_F(me
), m
, a
);
91 return ((PyObject
*)o
);
94 static CONVFUNC(pfilt
, pfilt
*, PFILT_F
)
96 static PyObject
*pfmeth_jump(PyObject
*me
, PyObject
*arg
)
100 if (!PyArg_ParseTuple(arg
, "O&:jump", convpfilt
, &f
)) return (0);
101 PFILT_ST(me
) = pfilt_jump(PFILT_F(me
), f
);
105 static PyObject
*meth__PrimeFilter_smallfactor(PyObject
*me
, PyObject
*arg
)
110 if (!PyArg_ParseTuple(arg
, "OO&:smallfactor", &me
, convmp
, &x
)) goto end
;
111 rc
= PyInt_FromLong(pfilt_smallfactor(x
));
117 static int pfilt_pynonzerop(PyObject
*me
)
118 { return (PFILT_ST(me
) != PGEN_FAIL
); }
120 static PyObject
*pfilt_pyint(PyObject
*me
)
125 if (mp_tolong_checked(PFILT_F(me
)->m
, &l
)) goto end
;
126 rc
= PyInt_FromLong(l
);
131 static PyObject
*pfilt_pylong(PyObject
*me
)
132 { return (mp_topylong(PFILT_F(me
)->m
)); }
134 static PyObject
*pfget_x(PyObject
*me
, void *hunoz
)
135 { return (mp_pywrap(MP_COPY(PFILT_F(me
)->m
))); }
137 static PyObject
*pfget_status(PyObject
*me
, void *hunoz
)
138 { return (PyInt_FromLong(PFILT_ST(me
))); }
140 static PyGetSetDef pfilt_pygetset
[] = {
141 #define GETSETNAME(op, name) pf##op##_##name
142 GET (x
, "F.x -> current position of filter")
143 GET (status
, "F.status -> primality status of filter")
148 static PyMethodDef pfilt_pymethods
[] = {
149 #define METHNAME(name) pfmeth_##name
150 METH (step
, "F.step(N)")
151 METH (muladd
, "F.muladd(M, A)")
152 METH (jump
, "F.jump(FF)")
157 static PyNumberMethods pfilt_pynumber
= {
159 0, /* @nb_subtract@ */
160 0, /* @nb_multiply@ */
162 0, /* @nb_remainder@ */
165 0, /* @nb_negative@ */
166 0, /* @nb_positive@ */
167 0, /* @nb_absolute@ */
168 pfilt_pynonzerop
, /* @nb_nonzero@ */
176 pfilt_pyint
, /* @nb_int@ */
177 pfilt_pylong
, /* @nb_long@ */
182 0, /* @nb_inplace_add@ */
183 0, /* @nb_inplace_subtract@ */
184 0, /* @nb_inplace_multiply@ */
185 0, /* @nb_inplace_divide@ */
186 0, /* @nb_inplace_remainder@ */
187 0, /* @nb_inplace_power@ */
188 0, /* @nb_inplace_lshift@ */
189 0, /* @nb_inplace_rshift@ */
190 0, /* @nb_inplace_and@ */
191 0, /* @nb_inplace_xor@ */
192 0, /* @nb_inplace_or@ */
194 0, /* @nb_floor_divide@ */
195 0, /* @nb_true_divide@ */
196 0, /* @nb_inplace_floor_divide@ */
197 0, /* @nb_inplace_true_divide@ */
200 static PyTypeObject pfilt_pytype_skel
= {
201 PyObject_HEAD_INIT(0) 0, /* Header */
202 "catacomb.PrimeFilter", /* @tp_name@ */
203 sizeof(pfilt_pyobj
), /* @tp_basicsize@ */
204 0, /* @tp_itemsize@ */
206 pfilt_pydealloc
, /* @tp_dealloc@ */
208 0, /* @tp_getattr@ */
209 0, /* @tp_setattr@ */
210 0, /* @tp_compare@ */
212 &pfilt_pynumber
, /* @tp_as_number@ */
213 0, /* @tp_as_sequence@ */
214 0, /* @tp_as_mapping@ */
218 0, /* @tp_getattro@ */
219 0, /* @tp_setattro@ */
220 0, /* @tp_as_buffer@ */
221 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
225 "Small-primes filter.",
227 0, /* @tp_traverse@ */
229 0, /* @tp_richcompare@ */
230 0, /* @tp_weaklistoffset@ */
232 0, /* @tp_iternext@ */
233 pfilt_pymethods
, /* @tp_methods@ */
234 0, /* @tp_members@ */
235 pfilt_pygetset
, /* @tp_getset@ */
238 0, /* @tp_descr_get@ */
239 0, /* @tp_descr_set@ */
240 0, /* @tp_dictoffset@ */
242 PyType_GenericAlloc
, /* @tp_alloc@ */
243 pfilt_pynew
, /* @tp_new@ */
248 /*----- Rabin-Miller testing ----------------------------------------------*/
250 typedef struct rabin_pyobj
{
255 static PyTypeObject
*rabin_pytype
;
256 #define RABIN_R(o) (&((rabin_pyobj *)(o))->r)
258 static PyObject
*rabin_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
262 char *kwlist
[] = { "x", 0 };
264 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&:new", kwlist
, convmp
, &x
))
266 if (!MP_POSP(x
) || MP_EVENP(x
)) VALERR("must be positive and odd");
267 o
= (rabin_pyobj
*)ty
->tp_alloc(ty
, 0);
268 rabin_create(&o
->r
, x
);
270 return ((PyObject
*)o
);
273 static void rabin_pydealloc(PyObject
*me
)
275 rabin_destroy(RABIN_R(me
));
279 static PyObject
*rmeth_test(PyObject
*me
, PyObject
*arg
)
284 if (!PyArg_ParseTuple(arg
, "O&:test", convmp
, &w
)) goto end
;
285 rc
= PyInt_FromLong(rabin_test(RABIN_R(me
), w
));
291 static PyObject
*rmeth_rtest(PyObject
*me
, PyObject
*arg
)
296 if (!PyArg_ParseTuple(arg
, "O&:rtest", convmp
, &w
)) goto end
;
297 rc
= PyInt_FromLong(rabin_rtest(RABIN_R(me
), w
));
303 static PyObject
*rget_niters(PyObject
*me
, void *hunoz
)
304 { return (PyInt_FromLong(rabin_iters(mp_bits(RABIN_R(me
)->mm
.m
)))); }
306 static PyObject
*rget_x(PyObject
*me
, void *hunoz
)
307 { return (mp_pywrap(MP_COPY(RABIN_R(me
)->mm
.m
))); }
309 static PyObject
*meth__RabinMiller_iters(PyObject
*me
, PyObject
*arg
)
313 if (!PyArg_ParseTuple(arg
, "OO&:iters", &me
, convuint
, &n
)) return (0);
314 return (PyInt_FromLong(rabin_iters(n
)));
317 static PyGetSetDef rabin_pygetset
[] = {
318 #define GETSETNAME(op, name) r##op##_##name
319 GET (x
, "R.x -> number under test")
320 GET (niters
, "R.niters -> suggested number of tests")
325 static PyMethodDef rabin_pymethods
[] = {
326 #define METHNAME(name) rmeth_##name
327 METH (test
, "R.test(W) -> PGST")
328 METH (rtest
, "R.rtest(W) -> PGST")
333 static PyTypeObject rabin_pytype_skel
= {
334 PyObject_HEAD_INIT(0) 0, /* Header */
335 "catacomb.RabinMiller", /* @tp_name@ */
336 sizeof(rabin_pyobj
), /* @tp_basicsize@ */
337 0, /* @tp_itemsize@ */
339 rabin_pydealloc
, /* @tp_dealloc@ */
341 0, /* @tp_getattr@ */
342 0, /* @tp_setattr@ */
343 0, /* @tp_compare@ */
345 0, /* @tp_as_number@ */
346 0, /* @tp_as_sequence@ */
347 0, /* @tp_as_mapping@ */
351 0, /* @tp_getattro@ */
352 0, /* @tp_setattro@ */
353 0, /* @tp_as_buffer@ */
354 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
358 "Rabin-Miller strong primality test.",
360 0, /* @tp_traverse@ */
362 0, /* @tp_richcompare@ */
363 0, /* @tp_weaklistoffset@ */
365 0, /* @tp_iternext@ */
366 rabin_pymethods
, /* @tp_methods@ */
367 0, /* @tp_members@ */
368 rabin_pygetset
, /* @tp_getset@ */
371 0, /* @tp_descr_get@ */
372 0, /* @tp_descr_set@ */
373 0, /* @tp_dictoffset@ */
375 PyType_GenericAlloc
, /* @tp_alloc@ */
376 rabin_pynew
, /* @tp_new@ */
381 /*----- Events ------------------------------------------------------------*/
383 typedef struct pgevent_pyobj
{
388 static PyTypeObject
*pgevent_pytype
;
389 #define PGEVENT_EV(o) (((pgevent_pyobj *)(o))->ev)
391 static PyObject
*pgevent_pywrap(pgen_event
*ev
)
393 pgevent_pyobj
*o
= PyObject_New(pgevent_pyobj
, pgevent_pytype
);
395 return ((PyObject
*)o
);
398 static CONVFUNC(pgevent
, pgen_event
*, PGEVENT_EV
)
400 static void pgevent_kill(PyObject
*me
) { PGEVENT_EV(me
) = 0; }
401 static void pgevent_pydealloc(PyObject
*me
) { FREEOBJ(me
); }
403 #define PGEVENT_CHECK(me) do { \
404 if (!PGEVENT_EV(me)) { \
405 PyErr_SetString(PyExc_ValueError, "event object is dead"); \
410 static PyObject
*peget_name(PyObject
*me
, void *hunoz
)
411 { PGEVENT_CHECK(me
); return (PyString_FromString(PGEVENT_EV(me
)->name
)); }
413 static PyObject
*peget_x(PyObject
*me
, void *hunoz
)
414 { PGEVENT_CHECK(me
); return (mp_pywrap(MP_COPY(PGEVENT_EV(me
)->m
))); }
416 static PyObject
*peget_steps(PyObject
*me
, void *hunoz
)
417 { PGEVENT_CHECK(me
); return (PyInt_FromLong(PGEVENT_EV(me
)->steps
)); }
419 static PyObject
*peget_tests(PyObject
*me
, void *hunoz
)
420 { PGEVENT_CHECK(me
); return (PyInt_FromLong(PGEVENT_EV(me
)->tests
)); }
422 static PyObject
*peget_rng(PyObject
*me
, void *hunoz
)
423 { PGEVENT_CHECK(me
); return (grand_pywrap(PGEVENT_EV(me
)->r
, 0)); }
425 static int peset_x(PyObject
*me
, PyObject
*xobj
, void *hunoz
)
428 pgen_event
*ev
= PGEVENT_EV(me
);
431 if ((x
= getmp(xobj
)) == 0) goto end
;
440 static PyGetSetDef pgevent_pygetset
[] = {
441 #define GETSETNAME(op, name) pe##op##_##name
442 GET (name
, "EV.name -> value being generated")
443 GETSET(x
, "EV.x -> value under test")
444 GET (steps
, "EV.steps -> number of steps left")
445 GET (tests
, "EV.tests -> tests before passing")
446 GET (rng
, "EV.rng -> (noncrypto) random number generator")
451 static PyTypeObject pgevent_pytype_skel
= {
452 PyObject_HEAD_INIT(0) 0, /* Header */
453 "catacomb.PrimeGenEvent", /* @tp_name@ */
454 sizeof(pgevent_pyobj
), /* @tp_basicsize@ */
455 0, /* @tp_itemsize@ */
457 pgevent_pydealloc
, /* @tp_dealloc@ */
459 0, /* @tp_getattr@ */
460 0, /* @tp_setattr@ */
461 0, /* @tp_compare@ */
463 0, /* @tp_as_number@ */
464 0, /* @tp_as_sequence@ */
465 0, /* @tp_as_mapping@ */
469 0, /* @tp_getattro@ */
470 0, /* @tp_setattro@ */
471 0, /* @tp_as_buffer@ */
472 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
476 "Prime-generation event.",
478 0, /* @tp_traverse@ */
480 0, /* @tp_richcompare@ */
481 0, /* @tp_weaklistoffset@ */
483 0, /* @tp_iternext@ */
484 0, /* @tp_methods@ */
485 0, /* @tp_members@ */
486 pgevent_pygetset
, /* @tp_getset@ */
489 0, /* @tp_descr_get@ */
490 0, /* @tp_descr_set@ */
491 0, /* @tp_dictoffset@ */
493 PyType_GenericAlloc
, /* @tp_alloc@ */
494 abstract_pynew
, /* @tp_new@ */
499 /*----- Event handlers ----------------------------------------------------*/
501 PyTypeObject
*pgev_pytype
;
503 typedef struct pgstep_pyobj
{
508 static PyTypeObject
*pgstep_pytype
;
509 #define PGSTEP_STEP(o) (((pgstep_pyobj *)(o))->f.step)
511 typedef struct pgjump_pyobj
{
517 static PyTypeObject
*pgjump_pytype
;
518 #define PGJUMP_FOBJ(o) (((pgjump_pyobj *)(o))->fobj)
519 #define PGJUMP_J(o) (&((pgjump_pyobj *)(o))->j)
521 typedef struct pgtest_pyobj
{
526 static PyTypeObject
*pgtest_pytype
;
528 static int pgev_python(int rq
, pgen_event
*ev
, void *p
)
536 "pg_abort", "pg_done", "pg_begin", "pg_try", "pg_fail", "pg_pass"
541 if (rq
> N(meth
)) SYSERR("event code out of range");
542 pyev
= pgevent_pywrap(ev
);
543 if ((rc
= PyObject_CallMethod(py
, meth
[rq
], "(O)", pyev
)) == 0)
547 else if ((l
= PyInt_AsLong(rc
)) == -1 && PyErr_Occurred())
549 else if (l
< PGEN_ABORT
|| l
> PGEN_PASS
)
550 VALERR("return code out of range");
563 static PyObject
*pgev_pywrap(const pgev
*pg
)
567 o
= PyObject_New(pgev_pyobj
, pgev_pytype
);
569 return ((PyObject
*)o
);
572 int convpgev(PyObject
*o
, void *p
)
579 pg
->proc
= pgev_python
;
586 void droppgev(pgev
*p
)
588 if (p
->proc
== pgev_python
) {
589 PyObject
*py
= p
->ctx
;
594 static PyObject
*pgmeth_common(PyObject
*me
, PyObject
*arg
, int rq
)
597 pgev
*pg
= PGEV_PG(me
);
600 if (!PyArg_ParseTuple(arg
, "O&", convpgevent
, &ev
)) goto end
;
601 rc
= PyInt_FromLong(!pg
->proc ? rq
: pg
->proc(rq
, ev
, pg
->ctx
));
606 #define PGMETH(lc, uc) \
607 static PyObject *pgmeth_pg_##lc(PyObject *me, PyObject *arg) \
608 { return pgmeth_common(me, arg, PGEN_##uc); }
617 static PyObject
*pgev_stdev(pgen_proc
*proc
)
618 { pgev pg
; pg
.proc
= proc
; pg
.ctx
= 0; return (pgev_pywrap(&pg
)); }
620 static PyMethodDef pgev_pymethods
[] = {
621 #define METHNAME(name) pgmeth_##name
622 METH (pg_abort
, "E.pg_abort() -> PGRC -- prime generation aborted")
623 METH (pg_done
, "E.pg_done() -> PGRC -- prime generation finished")
624 METH (pg_begin
, "E.pg_begin() -> PGRC -- commence stepping/testing")
625 METH (pg_try
, "E.pg_try() -> PGRC -- found new candidate")
626 METH (pg_pass
, "E.pg_pass() -> PGRC -- passed primality test")
627 METH (pg_fail
, "E.pg_fail() -> PGRC -- failed primality test")
632 static PyTypeObject pgev_pytype_skel
= {
633 PyObject_HEAD_INIT(0) 0, /* Header */
634 "catacomb.PrimeGenBuiltinHandler", /* @tp_name@ */
635 sizeof(pgev_pyobj
), /* @tp_basicsize@ */
636 0, /* @tp_itemsize@ */
638 0, /* @tp_dealloc@ */
640 0, /* @tp_getattr@ */
641 0, /* @tp_setattr@ */
642 0, /* @tp_compare@ */
644 0, /* @tp_as_number@ */
645 0, /* @tp_as_sequence@ */
646 0, /* @tp_as_mapping@ */
650 0, /* @tp_getattro@ */
651 0, /* @tp_setattro@ */
652 0, /* @tp_as_buffer@ */
653 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
657 "Built-in prime-generation event handler, base class.",
659 0, /* @tp_traverse@ */
661 0, /* @tp_richcompare@ */
662 0, /* @tp_weaklistoffset@ */
664 0, /* @tp_iternext@ */
665 pgev_pymethods
, /* @tp_methods@ */
666 0, /* @tp_members@ */
670 0, /* @tp_descr_get@ */
671 0, /* @tp_descr_set@ */
672 0, /* @tp_dictoffset@ */
674 PyType_GenericAlloc
, /* @tp_alloc@ */
675 abstract_pynew
, /* @tp_new@ */
680 static PyObject
*pgstep_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
683 pgstep_pyobj
*rc
= 0;
684 char *kwlist
[] = { "step", 0 };
686 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&:new", kwlist
, convmpw
, &s
))
688 rc
= (pgstep_pyobj
*)ty
->tp_alloc(ty
, 0);
690 rc
->pg
.proc
= pgen_filter
;
693 return ((PyObject
*)rc
);
696 static PyObject
*psget_step(PyObject
*me
, void *hunoz
)
697 { return (PyInt_FromLong(PGSTEP_STEP(me
))); }
699 static PyGetSetDef pgstep_pygetset
[] = {
700 #define GETSETNAME(op, name) ps##op##_##name
701 GET (step
, "S.step -> step size for the stepper")
706 static PyTypeObject pgstep_pytype_skel
= {
707 PyObject_HEAD_INIT(0) 0, /* Header */
708 "catacomb.PrimeGenStepper", /* @tp_name@ */
709 sizeof(pgstep_pyobj
), /* @tp_basicsize@ */
710 0, /* @tp_itemsize@ */
712 0, /* @tp_dealloc@ */
714 0, /* @tp_getattr@ */
715 0, /* @tp_setattr@ */
716 0, /* @tp_compare@ */
718 0, /* @tp_as_number@ */
719 0, /* @tp_as_sequence@ */
720 0, /* @tp_as_mapping@ */
724 0, /* @tp_getattro@ */
725 0, /* @tp_setattro@ */
726 0, /* @tp_as_buffer@ */
727 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
731 "Simple prime-number stepper with small-factors filter.",
733 0, /* @tp_traverse@ */
735 0, /* @tp_richcompare@ */
736 0, /* @tp_weaklistoffset@ */
738 0, /* @tp_iternext@ */
739 0, /* @tp_methods@ */
740 0, /* @tp_members@ */
741 pgstep_pygetset
, /* @tp_getset@ */
744 0, /* @tp_descr_get@ */
745 0, /* @tp_descr_set@ */
746 0, /* @tp_dictoffset@ */
748 PyType_GenericAlloc
, /* @tp_alloc@ */
749 pgstep_pynew
, /* @tp_new@ */
754 static PyObject
*pgjump_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
757 pgjump_pyobj
*rc
= 0;
758 char *kwlist
[] = { "jump", 0 };
760 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O:new", kwlist
, &o
) ||
761 (fobj
= pfilt_pymake(pfilt_pytype
, o
)) == 0)
763 rc
= (pgjump_pyobj
*)ty
->tp_alloc(ty
, 0);
765 rc
->j
.j
= PFILT_F(fobj
);
766 rc
->pg
.proc
= pgen_jump
;
769 return ((PyObject
*)rc
);
772 static void pgjump_pydealloc(PyObject
*me
)
774 Py_DECREF(PGJUMP_FOBJ(me
));
778 static PyObject
*pjget_jump(PyObject
*me
, void *hunoz
)
779 { RETURN_OBJ(PGJUMP_FOBJ(me
)); }
781 static PyGetSetDef pgjump_pygetset
[] = {
782 #define GETSETNAME(op, name) pj##op##_##name
783 GET (jump
, "S.jump -> jump size for the stepper")
788 static PyTypeObject pgjump_pytype_skel
= {
789 PyObject_HEAD_INIT(0) 0, /* Header */
790 "catacomb.PrimeGenJumper", /* @tp_name@ */
791 sizeof(pgjump_pyobj
), /* @tp_basicsize@ */
792 0, /* @tp_itemsize@ */
794 pgjump_pydealloc
, /* @tp_dealloc@ */
796 0, /* @tp_getattr@ */
797 0, /* @tp_setattr@ */
798 0, /* @tp_compare@ */
800 0, /* @tp_as_number@ */
801 0, /* @tp_as_sequence@ */
802 0, /* @tp_as_mapping@ */
806 0, /* @tp_getattro@ */
807 0, /* @tp_setattro@ */
808 0, /* @tp_as_buffer@ */
809 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
813 "Stepper for larger steps, with small-factors filter.",
815 0, /* @tp_traverse@ */
817 0, /* @tp_richcompare@ */
818 0, /* @tp_weaklistoffset@ */
820 0, /* @tp_iternext@ */
821 0, /* @tp_methods@ */
822 0, /* @tp_members@ */
823 pgjump_pygetset
, /* @tp_getset@ */
826 0, /* @tp_descr_get@ */
827 0, /* @tp_descr_set@ */
828 0, /* @tp_dictoffset@ */
830 PyType_GenericAlloc
, /* @tp_alloc@ */
831 pgjump_pynew
, /* @tp_new@ */
836 static PyObject
*pgtest_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
838 pgtest_pyobj
*rc
= 0;
839 char *kwlist
[] = { 0 };
841 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, ":new", kwlist
)) goto end
;
842 rc
= (pgtest_pyobj
*)ty
->tp_alloc(ty
, 0);
843 rc
->pg
.proc
= pgen_test
;
846 return ((PyObject
*)rc
);
849 static PyTypeObject pgtest_pytype_skel
= {
850 PyObject_HEAD_INIT(0) 0, /* Header */
851 "catacomb.PrimeGenTester", /* @tp_name@ */
852 sizeof(pgtest_pyobj
), /* @tp_basicsize@ */
853 0, /* @tp_itemsize@ */
855 0, /* @tp_dealloc@ */
857 0, /* @tp_getattr@ */
858 0, /* @tp_setattr@ */
859 0, /* @tp_compare@ */
861 0, /* @tp_as_number@ */
862 0, /* @tp_as_sequence@ */
863 0, /* @tp_as_mapping@ */
867 0, /* @tp_getattro@ */
868 0, /* @tp_setattro@ */
869 0, /* @tp_as_buffer@ */
870 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
874 "Rabin-Miller tester.",
876 0, /* @tp_traverse@ */
878 0, /* @tp_richcompare@ */
879 0, /* @tp_weaklistoffset@ */
881 0, /* @tp_iternext@ */
882 0, /* @tp_methods@ */
883 0, /* @tp_members@ */
887 0, /* @tp_descr_get@ */
888 0, /* @tp_descr_set@ */
889 0, /* @tp_dictoffset@ */
891 PyType_GenericAlloc
, /* @tp_alloc@ */
892 pgtest_pynew
, /* @tp_new@ */
897 /*----- Prime generation functions ----------------------------------------*/
901 if (!PyErr_Occurred())
902 PyErr_SetString(PyExc_ValueError
, "prime generation failed");
905 static PyObject
*meth_pgen(PyObject
*me
, PyObject
*arg
, PyObject
*kw
)
911 pgen_filterctx fc
= { 2 };
913 pgev step
= { 0 }, test
= { 0 }, evt
= { 0 };
914 unsigned nsteps
= 0, ntests
= 0;
915 char *kwlist
[] = { "start", "name", "stepper", "tester", "event",
916 "nsteps", "ntests", 0 };
918 step
.proc
= pgen_filter
; step
.ctx
= &fc
;
919 test
.proc
= pgen_test
; test
.ctx
= &tc
;
920 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&|sO&O&O&O&O&:pgen", kwlist
,
921 convmp
, &x
, &p
, convpgev
, &step
,
922 convpgev
, &test
, convpgev
, &evt
,
923 convuint
, &nsteps
, convuint
, &ntests
))
925 if (!ntests
) ntests
= rabin_iters(mp_bits(x
));
926 if ((r
= pgen(p
, MP_NEW
, x
, evt
.proc
, evt
.ctx
,
927 nsteps
, step
.proc
, step
.ctx
,
928 ntests
, test
.proc
, test
.ctx
)) == 0)
930 if (PyErr_Occurred()) goto end
;
934 mp_drop(r
); mp_drop(x
);
935 droppgev(&step
); droppgev(&test
); droppgev(&evt
);
939 static PyObject
*meth_strongprime_setup(PyObject
*me
,
940 PyObject
*arg
, PyObject
*kw
)
944 grand
*r
= &rand_global
;
950 char *kwlist
[] = { "nbits", "name", "event", "rng", "nsteps", 0 };
952 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&|sO&O&O&", kwlist
,
953 convuint
, &nbits
, &name
,
954 convpgev
, &evt
, convgrand
, &r
,
957 if ((x
= strongprime_setup(name
, MP_NEW
, &f
, nbits
,
958 r
, n
, evt
.proc
, evt
.ctx
)) == 0)
960 rc
= Py_BuildValue("(NN)", mp_pywrap(x
), pfilt_pywrap(&f
));
968 static PyObject
*meth_strongprime(PyObject
*me
, PyObject
*arg
, PyObject
*kw
)
971 grand
*r
= &rand_global
;
977 char *kwlist
[] = { "nbits", "name", "event", "rng", "nsteps", 0 };
979 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&|sO&O&O&", kwlist
,
980 convuint
, &nbits
, &name
,
981 convpgev
, &evt
, convgrand
, &r
,
984 if ((x
= strongprime(name
, MP_NEW
, nbits
,
985 r
, n
, evt
.proc
, evt
.ctx
)) == 0)
995 static PyObject
*meth_limlee(PyObject
*me
, PyObject
*arg
, PyObject
*kw
)
998 pgev ie
= { 0 }, oe
= { 0 };
1000 grand
*r
= &rand_global
;
1003 PyObject
*rc
= 0, *vec
;
1004 char *kwlist
[] = { "pbits", "qbits", "name", "event", "ievent",
1005 "rng", "nsteps", 0 };
1008 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&O&|sO&O&O&O&:limlee", kwlist
,
1009 convuint
, &pl
, convuint
, &ql
,
1010 &p
, convpgev
, &oe
, convpgev
, &ie
,
1011 convgrand
, &r
, convuint
, &on
))
1013 if ((x
= limlee(p
, MP_NEW
, MP_NEW
, ql
, pl
, r
, on
,
1014 oe
.proc
, oe
.ctx
, ie
.proc
, ie
.ctx
, &nf
, &v
)) == 0)
1016 vec
= PyList_New(nf
);
1017 for (i
= 0; i
< nf
; i
++)
1018 PyList_SetItem(vec
, i
, mp_pywrap(v
[i
]));
1020 rc
= Py_BuildValue("(NN)", mp_pywrap(x
), vec
);
1022 droppgev(&oe
); droppgev(&ie
);
1026 /*----- Global stuff ------------------------------------------------------*/
1028 static PyMethodDef methods
[] = {
1029 #define METHNAME(name) meth_##name
1030 METH (_PrimeFilter_smallfactor
, "smallfactor(X) -> PGRC")
1031 METH (_RabinMiller_iters
, "iters(NBITS) -> NITERS")
1033 pgen(START, [name = 'p', stepper = PrimeGenStepper(2),\n\
1034 tester = PrimeGenTester(), event = pgen_nullev,\n\
1035 nsteps = 0, ntests = RabinMiller.iters(START.nbits)]) -> P")
1036 KWMETH(strongprime_setup
, "\
1037 strongprime_setup(NBITS, [name = 'p', event = pgen_nullev,\n\
1038 rng = rand, nsteps = 0]) -> (START, JUMP)")
1039 KWMETH(strongprime
, "\
1040 strongprime_setup(NBITS, [name = 'p', event = pgen_nullev,\n\
1041 rng = rand, nsteps = 0]) -> P")
1043 limlee(PBITS, QBITS, [name = 'p', event = pgen_nullev,\n\
1044 ievent = pgen_nullev, rng = rand, nsteps = 0]) -> (P, [Q, ...])")
1049 void pgen_pyinit(void)
1051 INITTYPE(pfilt
, root
);
1052 INITTYPE(rabin
, root
);
1053 INITTYPE(pgevent
, root
);
1054 INITTYPE(pgev
, root
);
1055 INITTYPE(pgstep
, pgev
);
1056 INITTYPE(pgjump
, pgev
);
1057 INITTYPE(pgtest
, pgev
);
1058 addmethods(methods
);
1061 static PyObject
*obj
;
1063 void pgen_pyinsert(PyObject
*mod
)
1065 INSERT("PrimeFilter", pfilt_pytype
);
1066 INSERT("RabinMiller", rabin_pytype
);
1067 INSERT("PrimeGenEvent", pgevent_pytype
);
1068 INSERT("PrimeGenBuiltinHandler", pgev_pytype
);
1069 INSERT("PrimeGenStepper", pgstep_pytype
);
1070 INSERT("PrimeGenJumper", pgjump_pytype
);
1071 INSERT("PrimeGenTester", pgtest_pytype
);
1072 INSERT("pgen_nullev", obj
= pgev_stdev(0));
1073 INSERT("pgen_stdev", pgev_stdev(pgen_ev
));
1074 INSERT("pgen_spinev", pgev_stdev(pgen_evspin
));
1075 INSERT("pgen_subev", pgev_stdev(pgen_subev
));
1078 /*----- That's all, folks -------------------------------------------------*/