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
*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 "PrimeFilter(X): 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 static const char *const 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 "RabinMiller(X): 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
);
447 if ((x
= getmp(xobj
)) == 0) goto end
;
456 static PyGetSetDef pgevent_pygetset
[] = {
457 #define GETSETNAME(op, name) pe##op##_##name
458 GET (name
, "EV.name -> value being generated")
459 GETSET(x
, "EV.x -> value under test")
460 GET (steps
, "EV.steps -> number of steps left")
461 GET (tests
, "EV.tests -> tests before passing")
462 GET (rng
, "EV.rng -> (noncrypto) random number generator")
467 static PyTypeObject pgevent_pytype_skel
= {
468 PyObject_HEAD_INIT(0) 0, /* Header */
469 "PrimeGenEvent", /* @tp_name@ */
470 sizeof(pgevent_pyobj
), /* @tp_basicsize@ */
471 0, /* @tp_itemsize@ */
473 pgevent_pydealloc
, /* @tp_dealloc@ */
475 0, /* @tp_getattr@ */
476 0, /* @tp_setattr@ */
477 0, /* @tp_compare@ */
479 0, /* @tp_as_number@ */
480 0, /* @tp_as_sequence@ */
481 0, /* @tp_as_mapping@ */
485 0, /* @tp_getattro@ */
486 0, /* @tp_setattro@ */
487 0, /* @tp_as_buffer@ */
488 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
492 "Prime-generation event.",
494 0, /* @tp_traverse@ */
496 0, /* @tp_richcompare@ */
497 0, /* @tp_weaklistoffset@ */
499 0, /* @tp_iternext@ */
500 0, /* @tp_methods@ */
501 0, /* @tp_members@ */
502 pgevent_pygetset
, /* @tp_getset@ */
505 0, /* @tp_descr_get@ */
506 0, /* @tp_descr_set@ */
507 0, /* @tp_dictoffset@ */
509 PyType_GenericAlloc
, /* @tp_alloc@ */
510 abstract_pynew
, /* @tp_new@ */
515 /*----- Event handlers ----------------------------------------------------*/
517 PyTypeObject
*pgev_pytype
;
519 typedef struct pgstep_pyobj
{
524 static PyTypeObject
*pgstep_pytype
;
525 #define PGSTEP_STEP(o) (((pgstep_pyobj *)(o))->f.step)
527 typedef struct pgjump_pyobj
{
533 static PyTypeObject
*pgjump_pytype
;
534 #define PGJUMP_FOBJ(o) (((pgjump_pyobj *)(o))->fobj)
535 #define PGJUMP_J(o) (&((pgjump_pyobj *)(o))->j)
537 typedef struct pgtest_pyobj
{
542 static PyTypeObject
*pgtest_pytype
;
544 static int pgev_python(int rq
, pgen_event
*ev
, void *p
)
551 static const char *const meth
[] =
552 { "pg_abort", "pg_done", "pg_begin", "pg_try", "pg_fail", "pg_pass" };
556 if (rq
> N(meth
)) SYSERR("event code out of range");
557 pyev
= pgevent_pywrap(ev
);
558 if ((rc
= PyObject_CallMethod(py
, (/*unconst*/ char *)meth
[rq
],
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");
579 static PyObject
*pgev_pywrap(const pgev
*pg
)
583 o
= PyObject_New(pgev_pyobj
, pgev_pytype
);
585 return ((PyObject
*)o
);
588 int convpgev(PyObject
*o
, void *p
)
595 pg
->proc
= pgev_python
;
602 void droppgev(pgev
*p
)
604 if (p
->proc
== pgev_python
) {
605 PyObject
*py
= p
->ctx
;
610 static PyObject
*pgmeth_common(PyObject
*me
, PyObject
*arg
, int rq
)
613 pgev
*pg
= PGEV_PG(me
);
616 if (!PyArg_ParseTuple(arg
, "O&", convpgevent
, &ev
)) goto end
;
617 rc
= PyInt_FromLong(!pg
->proc ? rq
: pg
->proc(rq
, ev
, pg
->ctx
));
622 #define PGMETH(lc, uc) \
623 static PyObject *pgmeth_pg_##lc(PyObject *me, PyObject *arg) \
624 { return pgmeth_common(me, arg, PGEN_##uc); }
633 static PyObject
*pgev_stdev(pgen_proc
*proc
)
634 { pgev pg
; pg
.proc
= proc
; pg
.ctx
= 0; return (pgev_pywrap(&pg
)); }
636 static PyMethodDef pgev_pymethods
[] = {
637 #define METHNAME(name) pgmeth_##name
638 METH (pg_abort
, "E.pg_abort() -> PGRC -- prime generation aborted")
639 METH (pg_done
, "E.pg_done() -> PGRC -- prime generation finished")
640 METH (pg_begin
, "E.pg_begin() -> PGRC -- commence stepping/testing")
641 METH (pg_try
, "E.pg_try() -> PGRC -- found new candidate")
642 METH (pg_pass
, "E.pg_pass() -> PGRC -- passed primality test")
643 METH (pg_fail
, "E.pg_fail() -> PGRC -- failed primality test")
648 static PyTypeObject pgev_pytype_skel
= {
649 PyObject_HEAD_INIT(0) 0, /* Header */
650 "PrimeGenBuiltinHandler", /* @tp_name@ */
651 sizeof(pgev_pyobj
), /* @tp_basicsize@ */
652 0, /* @tp_itemsize@ */
654 0, /* @tp_dealloc@ */
656 0, /* @tp_getattr@ */
657 0, /* @tp_setattr@ */
658 0, /* @tp_compare@ */
660 0, /* @tp_as_number@ */
661 0, /* @tp_as_sequence@ */
662 0, /* @tp_as_mapping@ */
666 0, /* @tp_getattro@ */
667 0, /* @tp_setattro@ */
668 0, /* @tp_as_buffer@ */
669 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
673 "Built-in prime-generation event handler, base class.",
675 0, /* @tp_traverse@ */
677 0, /* @tp_richcompare@ */
678 0, /* @tp_weaklistoffset@ */
680 0, /* @tp_iternext@ */
681 pgev_pymethods
, /* @tp_methods@ */
682 0, /* @tp_members@ */
686 0, /* @tp_descr_get@ */
687 0, /* @tp_descr_set@ */
688 0, /* @tp_dictoffset@ */
690 PyType_GenericAlloc
, /* @tp_alloc@ */
691 abstract_pynew
, /* @tp_new@ */
696 static PyObject
*pgstep_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
699 pgstep_pyobj
*rc
= 0;
700 static const char *const kwlist
[] = { "step", 0 };
702 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&:new", KWLIST
, convmpw
, &s
))
704 rc
= (pgstep_pyobj
*)ty
->tp_alloc(ty
, 0);
706 rc
->pg
.proc
= pgen_filter
;
709 return ((PyObject
*)rc
);
712 static PyObject
*psget_step(PyObject
*me
, void *hunoz
)
713 { return (PyInt_FromLong(PGSTEP_STEP(me
))); }
715 static PyGetSetDef pgstep_pygetset
[] = {
716 #define GETSETNAME(op, name) ps##op##_##name
717 GET (step
, "S.step -> step size for the stepper")
722 static PyTypeObject pgstep_pytype_skel
= {
723 PyObject_HEAD_INIT(0) 0, /* Header */
724 "PrimeGenStepper", /* @tp_name@ */
725 sizeof(pgstep_pyobj
), /* @tp_basicsize@ */
726 0, /* @tp_itemsize@ */
728 0, /* @tp_dealloc@ */
730 0, /* @tp_getattr@ */
731 0, /* @tp_setattr@ */
732 0, /* @tp_compare@ */
734 0, /* @tp_as_number@ */
735 0, /* @tp_as_sequence@ */
736 0, /* @tp_as_mapping@ */
740 0, /* @tp_getattro@ */
741 0, /* @tp_setattro@ */
742 0, /* @tp_as_buffer@ */
743 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
747 "PrimeGenStepper(STEP): simple stepper with small-factors filter.",
749 0, /* @tp_traverse@ */
751 0, /* @tp_richcompare@ */
752 0, /* @tp_weaklistoffset@ */
754 0, /* @tp_iternext@ */
755 0, /* @tp_methods@ */
756 0, /* @tp_members@ */
757 pgstep_pygetset
, /* @tp_getset@ */
760 0, /* @tp_descr_get@ */
761 0, /* @tp_descr_set@ */
762 0, /* @tp_dictoffset@ */
764 PyType_GenericAlloc
, /* @tp_alloc@ */
765 pgstep_pynew
, /* @tp_new@ */
770 static PyObject
*pgjump_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
773 pgjump_pyobj
*rc
= 0;
774 static const char *const kwlist
[] = { "jump", 0 };
776 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O:new", KWLIST
, &o
) ||
777 (fobj
= pfilt_pymake(pfilt_pytype
, o
)) == 0)
779 rc
= (pgjump_pyobj
*)ty
->tp_alloc(ty
, 0);
781 rc
->j
.j
= PFILT_F(fobj
);
782 rc
->pg
.proc
= pgen_jump
;
785 return ((PyObject
*)rc
);
788 static void pgjump_pydealloc(PyObject
*me
)
790 Py_DECREF(PGJUMP_FOBJ(me
));
794 static PyObject
*pjget_jump(PyObject
*me
, void *hunoz
)
795 { RETURN_OBJ(PGJUMP_FOBJ(me
)); }
797 static PyGetSetDef pgjump_pygetset
[] = {
798 #define GETSETNAME(op, name) pj##op##_##name
799 GET (jump
, "S.jump -> jump size for the stepper")
804 static PyTypeObject pgjump_pytype_skel
= {
805 PyObject_HEAD_INIT(0) 0, /* Header */
806 "PrimeGenJumper", /* @tp_name@ */
807 sizeof(pgjump_pyobj
), /* @tp_basicsize@ */
808 0, /* @tp_itemsize@ */
810 pgjump_pydealloc
, /* @tp_dealloc@ */
812 0, /* @tp_getattr@ */
813 0, /* @tp_setattr@ */
814 0, /* @tp_compare@ */
816 0, /* @tp_as_number@ */
817 0, /* @tp_as_sequence@ */
818 0, /* @tp_as_mapping@ */
822 0, /* @tp_getattro@ */
823 0, /* @tp_setattro@ */
824 0, /* @tp_as_buffer@ */
825 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
829 "PrimeGenJumper(JUMP): stepper for larger steps with small-factors filter.",
831 0, /* @tp_traverse@ */
833 0, /* @tp_richcompare@ */
834 0, /* @tp_weaklistoffset@ */
836 0, /* @tp_iternext@ */
837 0, /* @tp_methods@ */
838 0, /* @tp_members@ */
839 pgjump_pygetset
, /* @tp_getset@ */
842 0, /* @tp_descr_get@ */
843 0, /* @tp_descr_set@ */
844 0, /* @tp_dictoffset@ */
846 PyType_GenericAlloc
, /* @tp_alloc@ */
847 pgjump_pynew
, /* @tp_new@ */
852 static PyObject
*pgtest_pynew(PyTypeObject
*ty
, PyObject
*arg
, PyObject
*kw
)
854 pgtest_pyobj
*rc
= 0;
855 static const char *const kwlist
[] = { 0 };
857 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, ":new", KWLIST
)) goto end
;
858 rc
= (pgtest_pyobj
*)ty
->tp_alloc(ty
, 0);
859 rc
->pg
.proc
= pgen_test
;
862 return ((PyObject
*)rc
);
865 static PyTypeObject pgtest_pytype_skel
= {
866 PyObject_HEAD_INIT(0) 0, /* Header */
867 "PrimeGenTester", /* @tp_name@ */
868 sizeof(pgtest_pyobj
), /* @tp_basicsize@ */
869 0, /* @tp_itemsize@ */
871 0, /* @tp_dealloc@ */
873 0, /* @tp_getattr@ */
874 0, /* @tp_setattr@ */
875 0, /* @tp_compare@ */
877 0, /* @tp_as_number@ */
878 0, /* @tp_as_sequence@ */
879 0, /* @tp_as_mapping@ */
883 0, /* @tp_getattro@ */
884 0, /* @tp_setattro@ */
885 0, /* @tp_as_buffer@ */
886 Py_TPFLAGS_DEFAULT
| /* @tp_flags@ */
890 "PrimeGenTester(): Rabin-Miller tester.",
892 0, /* @tp_traverse@ */
894 0, /* @tp_richcompare@ */
895 0, /* @tp_weaklistoffset@ */
897 0, /* @tp_iternext@ */
898 0, /* @tp_methods@ */
899 0, /* @tp_members@ */
903 0, /* @tp_descr_get@ */
904 0, /* @tp_descr_set@ */
905 0, /* @tp_dictoffset@ */
907 PyType_GenericAlloc
, /* @tp_alloc@ */
908 pgtest_pynew
, /* @tp_new@ */
913 /*----- Prime generation functions ----------------------------------------*/
917 if (!PyErr_Occurred())
918 PyErr_SetString(PyExc_ValueError
, "prime generation failed");
921 static PyObject
*meth_pgen(PyObject
*me
, PyObject
*arg
, PyObject
*kw
)
927 pgen_filterctx fc
= { 2 };
929 pgev step
= { 0 }, test
= { 0 }, evt
= { 0 };
930 unsigned nsteps
= 0, ntests
= 0;
931 static const char *const kwlist
[] =
932 { "start", "name", "stepper", "tester", "event", "nsteps", "ntests", 0 };
934 step
.proc
= pgen_filter
; step
.ctx
= &fc
;
935 test
.proc
= pgen_test
; test
.ctx
= &tc
;
936 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&|sO&O&O&O&O&:pgen", KWLIST
,
937 convmp
, &x
, &p
, convpgev
, &step
,
938 convpgev
, &test
, convpgev
, &evt
,
939 convuint
, &nsteps
, convuint
, &ntests
))
941 if (!ntests
) ntests
= rabin_iters(mp_bits(x
));
942 if ((r
= pgen(p
, MP_NEW
, x
, evt
.proc
, evt
.ctx
,
943 nsteps
, step
.proc
, step
.ctx
,
944 ntests
, test
.proc
, test
.ctx
)) == 0)
946 if (PyErr_Occurred()) goto end
;
950 mp_drop(r
); mp_drop(x
);
951 droppgev(&step
); droppgev(&test
); droppgev(&evt
);
955 static PyObject
*meth_strongprime_setup(PyObject
*me
,
956 PyObject
*arg
, PyObject
*kw
)
960 grand
*r
= &rand_global
;
966 static const char *const kwlist
[] =
967 { "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
.proc
, evt
.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
;
994 static const char *const kwlist
[] =
995 { "nbits", "name", "event", "rng", "nsteps", 0 };
997 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&|sO&O&O&", KWLIST
,
998 convuint
, &nbits
, &name
,
999 convpgev
, &evt
, convgrand
, &r
,
1002 if ((x
= strongprime(name
, MP_NEW
, nbits
,
1003 r
, n
, evt
.proc
, evt
.ctx
)) == 0)
1013 static PyObject
*meth_limlee(PyObject
*me
, PyObject
*arg
, PyObject
*kw
)
1016 pgev ie
= { 0 }, oe
= { 0 };
1018 grand
*r
= &rand_global
;
1021 PyObject
*rc
= 0, *vec
;
1022 static const char *const kwlist
[] =
1023 { "pbits", "qbits", "name", "event", "ievent", "rng", "nsteps", 0 };
1026 if (!PyArg_ParseTupleAndKeywords(arg
, kw
, "O&O&|sO&O&O&O&:limlee", KWLIST
,
1027 convuint
, &pl
, convuint
, &ql
,
1028 &p
, convpgev
, &oe
, convpgev
, &ie
,
1029 convgrand
, &r
, convuint
, &on
))
1031 if ((x
= limlee(p
, MP_NEW
, MP_NEW
, ql
, pl
, r
, on
,
1032 oe
.proc
, oe
.ctx
, ie
.proc
, ie
.ctx
, &nf
, &v
)) == 0)
1034 vec
= PyList_New(nf
);
1035 for (i
= 0; i
< nf
; i
++)
1036 PyList_SetItem(vec
, i
, mp_pywrap(v
[i
]));
1038 rc
= Py_BuildValue("(NN)", mp_pywrap(x
), vec
);
1040 droppgev(&oe
); droppgev(&ie
);
1044 /*----- Global stuff ------------------------------------------------------*/
1046 static PyMethodDef methods
[] = {
1047 #define METHNAME(name) meth_##name
1048 METH (_PrimeFilter_smallfactor
, "smallfactor(X) -> PGRC")
1049 METH (_RabinMiller_iters
, "iters(NBITS) -> NITERS")
1051 pgen(START, [name = 'p', stepper = PrimeGenStepper(2),\n\
1052 tester = PrimeGenTester(), event = pgen_nullev,\n\
1053 nsteps = 0, ntests = RabinMiller.iters(START.nbits)]) -> P")
1054 KWMETH(strongprime_setup
, "\
1055 strongprime_setup(NBITS, [name = 'p', event = pgen_nullev,\n\
1056 rng = rand, nsteps = 0]) -> (START, JUMP)")
1057 KWMETH(strongprime
, "\
1058 strongprime(NBITS, [name = 'p', event = pgen_nullev,\n\
1059 rng = rand, nsteps = 0]) -> P")
1061 limlee(PBITS, QBITS, [name = 'p', event = pgen_nullev,\n\
1062 ievent = pgen_nullev, rng = rand, nsteps = 0]) -> (P, [Q, ...])")
1067 void pgen_pyinit(void)
1069 INITTYPE(pfilt
, root
);
1070 INITTYPE(rabin
, root
);
1071 INITTYPE(pgevent
, root
);
1072 INITTYPE(pgev
, root
);
1073 INITTYPE(pgstep
, pgev
);
1074 INITTYPE(pgjump
, pgev
);
1075 INITTYPE(pgtest
, pgev
);
1076 addmethods(methods
);
1079 static PyObject
*obj
;
1081 void pgen_pyinsert(PyObject
*mod
)
1083 INSERT("PrimeFilter", pfilt_pytype
);
1084 INSERT("RabinMiller", rabin_pytype
);
1085 INSERT("PrimeGenEvent", pgevent_pytype
);
1086 INSERT("PrimeGenBuiltinHandler", pgev_pytype
);
1087 INSERT("PrimeGenStepper", pgstep_pytype
);
1088 INSERT("PrimeGenJumper", pgjump_pytype
);
1089 INSERT("PrimeGenTester", pgtest_pytype
);
1090 INSERT("pgen_nullev", obj
= pgev_stdev(0));
1091 INSERT("pgen_stdev", pgev_stdev(pgen_ev
));
1092 INSERT("pgen_spinev", pgev_stdev(pgen_evspin
));
1093 INSERT("pgen_subev", pgev_stdev(pgen_subev
));
1096 /*----- That's all, folks -------------------------------------------------*/