int pgen_test(int rq, pgen_event *ev, void *p)
{
rabin *r = p;
+ mp *a = MP_NEW;
int rc = PGEN_ABORT;
switch (rq) {
rc = PGEN_TRY;
break;
case PGEN_TRY:
- if (!ev->tests)
- rc = rabin_rtest(r, MP_TWO);
- else {
- mp *a = mprand_range(MP_NEW, ev->m, ev->r, 0);
- rc = rabin_rtest(r, a);
- mp_drop(a);
- }
+ a = mprand_range(a, ev->m, ev->r, 0);
+ rc = rabin_rtest(r, a);
break;
case PGEN_DONE:
rabin_destroy(r);
break;
}
+ mp_drop(a);
+ return (rc);
+}
+
+/* --- @pgen_bailliepswtest@ --- */
+
+int pgen_bailliepswtest(int rq, pgen_event *ev, void *p)
+{
+ rabin r;
+ int rc;
+
+ switch (rq) {
+ case PGEN_BEGIN:
+ if (ev->tests != 2) rc = PGEN_ABORT;
+ else rc = PGEN_TRY;
+ break;
+
+ case PGEN_DONE:
+ rc = PGEN_DONE;
+ break;
+
+ case PGEN_TRY:
+ switch (ev->tests) {
+ case 2:
+ rabin_create(&r, ev->m);
+ rc = rabin_test(&r, MP_TWO);
+ rabin_destroy(&r);
+ break;
+ case 1:
+ rc = pgen_granfrob(ev->m, 0, 0);
+ break;
+ default:
+ rc = PGEN_ABORT;
+ break;
+ }
+ break;
+
+ default:
+ rc = PGEN_ABORT;
+ break;
+ }
+
return (rc);
}
ev.m = MP_COPY(m);
else
ev.m = 0;
- ev.steps = 0;
- ev.tests = 0;
+ ev.steps = steps;
+ ev.tests = tests;
ev.r = fibrand_create(0);
/* --- Tell the event handler we're under way --- */
/* --- If decrementing counters is requested, do that --- */
if ((act & A_STEP) && steps) {
- ev.steps++;
- if (ev.steps == steps) {
+ ev.steps--;
+ if (!ev.steps) {
act |= A_EVENT | A_ENDSTEP | A_DONE;
rc = PGEN_ABORT;
}
- ev.tests = 0;
+ ev.tests = tests;
}
if ((act & A_TEST) && tests) {
- ev.tests++;
- if (ev.tests == tests) {
+ ev.tests--;
+ if (!ev.tests) {
act |= A_ENDTEST | A_ENDSTEP | A_DONE;
rc = PGEN_DONE;
}
* @grand *gr@ = a random number source
*
* Returns: Nonzero if @p@ is really prime.
+ *
+ * Use: Checks the primality of @p@. If @p@ is prime, then this
+ * function returns nonzero; if @p@ is really composite then it
+ * %%\emph{probably}%% returns zero, but might not.
+ *
+ * Currently, this function uses the Baillie--PSW test, which
+ * combines a single Miller--Rabin test with witness 2 with a
+ * single Frobenius test with parameters chosen using
+ * Selfridge's `Method A'. No composites are known which pass
+ * this test, though it's conjectured that infinitely many
+ * exist.
*/
int pgen_primep(mp *p, grand *gr)
{
- int i;
rabin r;
- mp *x = MP_NEW;
+ int rc;
if (MP_NEGP(p)) return (0);
switch (pfilt_smallfactor(p)) {
case PGEN_DONE: return (1);
case PGEN_FAIL: return (0);
}
- rabin_create(&r, p);
- for (i = 32; i; i--) {
- x = mprand_range(x, p, gr, 0);
- if (rabin_rtest(&r, x) == PGEN_FAIL)
- break;
- }
- MP_DROP(x);
- rabin_destroy(&r);
- return (!i);
+ rabin_create(&r, p); rc = rabin_test(&r, MP_TWO); rabin_destroy(&r);
+ if (rc == PGEN_FAIL) return (0);
+ rc = pgen_granfrob(p, 0, 0); if (rc == PGEN_FAIL) return (0);
+ return (1);
}
/*----- Test rig ----------------------------------------------------------*/