X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a..a938be516ed8fd8313ff3d061dd4b0f2d9acfa0e:/math/pgen.c?ds=sidebyside

diff --git a/math/pgen.c b/math/pgen.c
index 9a822f57..f10c163e 100644
--- a/math/pgen.c
+++ b/math/pgen.c
@@ -118,6 +118,7 @@ int pgen_jump(int rq, pgen_event *ev, void *p)
 int pgen_test(int rq, pgen_event *ev, void *p)
 {
   rabin *r = p;
+  mp *a = MP_NEW;
   int rc = PGEN_ABORT;
 
   switch (rq) {
@@ -126,13 +127,8 @@ int pgen_test(int rq, pgen_event *ev, void *p)
       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);
@@ -140,6 +136,7 @@ int pgen_test(int rq, pgen_event *ev, void *p)
       break;
   }
 
+  mp_drop(a);
   return (rc);
 }
 
@@ -283,7 +280,7 @@ mp *pgen(const char *name, mp *d, mp *m, pgen_proc *event, void *ectx,
       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;
       }
     }
@@ -319,28 +316,33 @@ mp *pgen(const char *name, mp *d, mp *m, pgen_proc *event, void *ectx,
  *		@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 ----------------------------------------------------------*/