From bd98b2dfce11db0e8893a2974d5f8db58dd90fa1 Mon Sep 17 00:00:00 2001
From: mdw <mdw>
Date: Sat, 20 Nov 1999 22:23:05 +0000
Subject: [PATCH] Add multiply-and-add function for Diffie-Hellman safe prime
 generation.

---
 pgen.c | 83 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 pgen.h | 25 +++++++++++++++++++-
 2 files changed, 103 insertions(+), 5 deletions(-)

diff --git a/pgen.c b/pgen.c
index 503b153..a57c30a 100644
--- a/pgen.c
+++ b/pgen.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: pgen.c,v 1.1 1999/11/19 13:17:57 mdw Exp $
+ * $Id: pgen.c,v 1.2 1999/11/20 22:23:05 mdw Exp $
  *
  * Finding and testing prime numbers
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: pgen.c,v $
+ * Revision 1.2  1999/11/20 22:23:05  mdw
+ * Add multiply-and-add function for Diffie-Hellman safe prime generation.
+ *
  * Revision 1.1  1999/11/19 13:17:57  mdw
  * Prime number generator and tester.
  *
@@ -121,14 +124,14 @@ void pgen_destroy(pgen *p)
 
 int pgen_step(pgen *p, mpw step)
 {
-  mp s;
   int rc = PGEN_MAYBE;
   int i;
 
   /* --- Add the step on to the number --- */
 
-  mp_build(&s, &step, &step + 1);
-  p->m = mp_add(p->m, p->m, &s);
+  p->m = mp_modify(p->m, MP_LEN(p->m) + 1);
+  mpx_uaddn(p->m->v, p->m->vl, step);
+  mp_shrink(p->m);
 
   /* --- Update the residue table --- */
 
@@ -142,11 +145,77 @@ int pgen_step(pgen *p, mpw step)
     }
   }
 
+  /* --- Small numbers must be prime --- */
+
+  if (rc == PGEN_MAYBE && MP_LEN(p->m) == 1 &&
+      p->m->v[0] < MAXPRIME * MAXPRIME)
+    rc = PGEN_PRIME;
+
   /* --- Done --- */
 
   return (rc);
 }
 
+/* --- @pgen_muladd@ --- *
+ *
+ * Arguments:	@pgen *p@ = destination prime generation context
+ *		@const pgen *q@ = source prime generation context
+ *		@mpw m@ = number to multiply by
+ *		@mpw a@ = number to add
+ *
+ * Returns:	One of the @PGEN@ constants above.
+ *
+ * Use:		Multiplies the number in a prime generation context by a
+ *		small value and then adds a small value.  The destination
+ *		should either be uninitialized or the same as the source.
+ *
+ *		Common things to do include multiplying by 2 and adding 0 to
+ *		turn a prime into a jump for finding other primes with @q@ as
+ *		a factor of @p - 1@, or multiplying by 2 and adding 1.
+ */
+
+int pgen_muladd(pgen *p, const pgen *q, mpw m, mpw a)
+{
+  int rc = PGEN_MAYBE;
+  int i;
+
+  /* --- Multiply the big number --- */
+
+  {
+    mp *d = mp_create(MP_LEN(q->m) + 2);
+    mpx_umuln(d->v, d->vl, q->m->v, q->m->vl, m);
+    mpx_uaddn(d->v, d->vl, a);
+    d->f = q->m->f;
+    if (p == q)
+      mp_drop(p->m);
+    mp_shrink(d);
+    p->m = d;
+  }
+
+  /* --- Gallivant through the residue table --- */
+      
+  for (i = 0; i < NPRIME; i++) {
+    p->r[i] = (q->r[i] * m + a) % ptab[i];
+    if (!p->r[i] && rc == PGEN_MAYBE) {
+      if (MP_LEN(p->m) == 1 && p->m->v[0] == ptab[i])
+	rc = PGEN_PRIME;
+      else
+	rc = PGEN_COMPOSITE;
+    }
+  }
+
+  /* --- Small numbers must be prime --- */
+
+  if (rc == PGEN_MAYBE && MP_LEN(p->m) == 1 &&
+      p->m->v[0] < MAXPRIME * MAXPRIME)
+    rc = PGEN_PRIME;
+
+  /* --- Finished --- */
+
+  return (rc);
+}
+
+
 /* --- @pgen_jump@ --- *
  *
  * Arguments:	@pgen *p@ = pointer to prime generation context
@@ -188,6 +257,12 @@ int pgen_jump(pgen *p, pgen *j)
     }
   }
 
+  /* --- Small numbers must be prime --- */
+
+  if (rc == PGEN_MAYBE && MP_LEN(p->m) == 1 &&
+      p->m->v[0] < MAXPRIME * MAXPRIME)
+    rc = PGEN_PRIME;
+
   /* --- Done --- */
 
   return (rc);
diff --git a/pgen.h b/pgen.h
index 536ba0a..6f2000c 100644
--- a/pgen.h
+++ b/pgen.h
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: pgen.h,v 1.1 1999/11/19 13:17:57 mdw Exp $
+ * $Id: pgen.h,v 1.2 1999/11/20 22:23:05 mdw Exp $
  *
  * Finding and testing prime numbers
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: pgen.h,v $
+ * Revision 1.2  1999/11/20 22:23:05  mdw
+ * Add multiply-and-add function for Diffie-Hellman safe prime generation.
+ *
  * Revision 1.1  1999/11/19 13:17:57  mdw
  * Prime number generator and tester.
  *
@@ -108,6 +111,26 @@ extern void pgen_destroy(pgen */*p*/);
 
 extern int pgen_step(pgen */*p*/, mpw /*step*/);
 
+/* --- @pgen_muladd@ --- *
+ *
+ * Arguments:	@pgen *p@ = destination prime generation context
+ *		@const pgen *q@ = source prime generation context
+ *		@mpw m@ = number to multiply by
+ *		@mpw a@ = number to add
+ *
+ * Returns:	One of the @PGEN@ constants above.
+ *
+ * Use:		Multiplies the number in a prime generation context by a
+ *		small value and then adds a small value.  The destination
+ *		should either be uninitialized or the same as the source.
+ *
+ *		Common things to do include multiplying by 2 and adding 0 to
+ *		turn a prime into a jump for finding other primes with @q@ as
+ *		a factor of @p - 1@, or multiplying by 2 and adding 1.
+ */
+
+extern int pgen_muladd(pgen */*p*/, const pgen */*q*/, mpw /*m*/, mpw /*a*/);
+
 /* --- @pgen_jump@ --- *
  *
  * Arguments:	@pgen *p@ = pointer to prime generation context
-- 
2.11.0