rc = PGEN_ABORT;
if (!(act & A_DONE)) {
act |= A_ENDSTEP | A_DONE;
- if (p == P_TEST)
+ if (p == P_TEST && rq != PGEN_BEGIN)
act |= A_ENDTEST;
}
}
* @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 ----------------------------------------------------------*/