Move enhanced prime finder function mpp_make_prime from primegen utility

program into mpprime.c.  declared in mpprime.h.

1 files changed, 1 insertions, 149 deletions

diff --git a/security/nss/lib/freebl/mpi/utils/primegen.c b/security/nss/lib/freebl/mpi/utils/primegen.c
index 2b30a94c0..77b986dc9 100644
--- a/security/nss/lib/freebl/mpi/utils/primegen.c
+++ b/security/nss/lib/freebl/mpi/utils/primegen.c
@@ -63,156 +63,11 @@
 
 #define NUM_TESTS 5  /* Number of Rabin-Miller iterations to test with */
 
-
-/* Produce table of composites from list of primes and trial value.  
-** trial must be odd. List of primes must not include 2.
-** sieve should have dimension >= MAXPRIME/2, where MAXPRIME is largest 
-** prime in list of primes.  After this function is finished,
-** if sieve[i] is non-zero, then (trial + 2*i) is composite.
-** Each prime used in the sieve costs one division of trial, and eliminates
-** one or more values from the search space. (3 eliminates 1/3 of the values
-** alone!)  Each value left in the search space costs 1 or more modular 
-** exponentations.  So, these divisions are a bargain!
-*/
-mp_err mpp_sieve(mp_int *trial, const mp_digit *primes, unsigned int nPrimes, 
-		 unsigned char *sieve, unsigned int nSieve)
-{
-  mp_err       res;
-  mp_digit     rem;
-  unsigned int ix;
-  unsigned long offset;
-
-  memset(sieve, 0, nSieve);
-
-  for(ix = 0; ix < nPrimes; ix++) {
-    mp_digit prime = primes[ix];
-    unsigned int i;
-    if((res = mp_mod_d(trial, prime, &rem)) != MP_OKAY) 
-      return res;
-
-    if (rem == 0) {
-      offset = 0;
-    } else {
-      offset = prime - (rem / 2);
-    }
-    for (i = offset; i < nSieve ; i += prime) {
-      sieve[i] = 1;
-    }
-  }
-
-  return MP_OKAY;
-}
-
-mp_err mpp_make_prime(mp_int *start, unsigned int nBits, unsigned int strong,
-		      unsigned long * nTries)
-{
-  mp_digit      np;
-  mp_err        res;
-  int           i;
-  mp_int        trial;
-  mp_int        q;
-  unsigned char sieve[32*1024];
-
-  ARGCHK(start != 0, MP_BADARG);
-  ARGCHK(nBits > 16, MP_RANGE);
-
-  mp_init(&trial);
-  mp_init(&q);
-  if (strong) 
-    --nBits;
-  res = mpl_set_bit(start, nBits - 1, 1);  if (res != MP_OKAY) goto loser;
-  res = mpl_set_bit(start,         0, 1);  if (res != MP_OKAY) goto loser;
-  for (i = mpl_significant_bits(start) - 1; i >= nBits; --i) {
-    res = mpl_set_bit(start, i, 0);  if (res != MP_OKAY) goto loser;
-  }
-  /* start sieveing with prime value of 3. */
-  res = mpp_sieve(start, prime_tab + 1, prime_tab_size - 1, 
-			 sieve, sizeof sieve);
-  if (res != MP_OKAY) goto loser;
 #ifdef DEBUG
-  res = 0;
-  for (i = 0; i < sizeof sieve; ++i) {
-    if (!sieve[i])
-      ++res;
-  }
-  fprintf(stderr,"sieve found %d potential primes.\n", res);
 #define FPUTC(x,y) fputc(x,y)
 #else
 #define FPUTC(x,y) 
 #endif
-  res = MP_NO;
-  for(i = 0; i < sizeof sieve; ++i) {
-    if (sieve[i])	/* this number is composite */
-      continue;
-    res = mp_add_d(start, 2 * i, &trial); if (res != MP_OKAY) goto loser;
-    FPUTC('.', stderr);
-    /* run a Fermat test */
-    res = mpp_fermat(&trial, 2);
-    if (res != MP_OKAY) {
-      if (res == MP_NO)
-	continue;	/* was composite */
-      goto loser;
-    }
-      
-    FPUTC('+', stderr);
-    /* If that passed, run some Miller-Rabin tests	*/
-    res = mpp_pprime(&trial, NUM_TESTS);
-    if (res != MP_OKAY) {
-      if (res == MP_NO)
-	continue;	/* was composite */
-      goto loser;
-    }
-    FPUTC('!', stderr);
-
-    if (!strong) 
-      break;	/* success !! */
-
-    /* At this point, we have strong evidence that our candidate
-       is itself prime.  If we want a strong prime, we need now
-       to test q = 2p + 1 for primality...
-     */
-    mp_mul_2(&trial, &q);
-    mp_add_d(&q, 1, &q);
-
-    /* Test q for small prime divisors ... */
-    np = prime_tab_size;
-    if (mpp_divis_primes(&q, &np) == MP_YES) { /* is composite */
-      mp_clear(&q);
-      continue;
-    }
-
-    /* And test with Fermat, as with its parent ... */
-    res = mpp_fermat(&q, 2);
-    if (res != MP_YES) {
-      mp_clear(&q);
-      if (res == MP_NO)
-	continue;	/* was composite */
-      goto loser;
-    }
-
-    /* And test with Miller-Rabin, as with its parent ... */
-    res = mpp_pprime(&q, NUM_TESTS);
-    if (res != MP_YES) {
-      mp_clear(&q);
-      if (res == MP_NO)
-	continue;	/* was composite */
-      goto loser;
-    }
-
-    /* If it passed, we've got a winner */
-    mp_exch(&q, &trial);
-    mp_clear(&q);
-    break;
-
-  } /* end of loop through sieved values */
-  if (res == MP_YES)
-    mp_exch(&trial, start);
-loser:
-  mp_clear(&trial);
-  if (nTries)
-    *nTries += i;
-  return res;
-}
 
 int main(int argc, char *argv[])
 {
@@ -293,10 +148,7 @@ int main(int argc, char *argv[])
       raw[ix] = (rand() * rand()) & UCHAR_MAX;
 
     raw[1] |= 0x80;             /* set high-order bit of test value     */
-    if(g_strong)
-      raw[rawlen - 1] |= 3;     /* set low-order two bits of test value */
-    else
-      raw[rawlen - 1] |= 1;     /* set low-order bit of test value      */
+    raw[rawlen - 1] |= 1;       /* set low-order bit of test value      */
 
     /* Make an mp_int out of the initializer */
     mp_read_raw(&testval, (char *)raw, rawlen);