static MPI
gen_prime( unsigned int nbits, int secret, int randomlevel )
{
    unsigned  nlimbs;
    MPI prime, ptest, pminus1, val_2, val_3, result;
    int i;
    unsigned x, step;
    int count1, count2;
    int *mods;

    if( 0 && DBG_CIPHER )
	log_debug("generate a prime of %u bits ", nbits );

    if (nbits < 16)
      {
        log_error (_("can't generate a prime with less than %d bits\n"), 16);
        exit (2);
      }

    if( !no_of_small_prime_numbers ) {
	for(i=0; small_prime_numbers[i]; i++ )
	    no_of_small_prime_numbers++;
    }
    mods = xmalloc( no_of_small_prime_numbers * sizeof *mods );
    /* Make nbits fit into MPI implementation.  */
    nlimbs = mpi_nlimb_hint_from_nbits (nbits);
    val_2  = mpi_alloc_set_ui( 2 );
    val_3 = mpi_alloc_set_ui( 3);
    prime  = secret? mpi_alloc_secure( nlimbs ): mpi_alloc( nlimbs );
    result = mpi_alloc_like( prime );
    pminus1= mpi_alloc_like( prime );
    ptest  = mpi_alloc_like( prime );
    count1 = count2 = 0;
    for(;;) {  /* try forvever */
	int dotcount=0;

	/* generate a random number */
	{   char *p = get_random_bits( nbits, randomlevel, secret );
	    mpi_set_buffer( prime, p, (nbits+7)/8, 0 );
	    xfree(p);
	}

	/* Set high order bit to 1, set low order bit to 0.
           If we are generating a secret prime we are most probably
           doing that for RSA, to make sure that the modulus does have
           the requested keysize we set the 2 high order bits */
	mpi_set_highbit( prime, nbits-1 );
        if (secret)
          mpi_set_bit (prime, nbits-2);
	mpi_set_bit( prime, 0 );

	/* calculate all remainders */
	for(i=0; (x = small_prime_numbers[i]); i++ )
	    mods[i] = mpi_fdiv_r_ui(NULL, prime, x);

	/* now try some primes starting with prime */
	for(step=0; step < 20000; step += 2 ) {
	    /* check against all the small primes we have in mods */
	    count1++;
	    for(i=0; (x = small_prime_numbers[i]); i++ ) {
		while( mods[i] + step >= x )
		    mods[i] -= x;
		if( !(mods[i] + step) )
		    break;
	    }
	    if( x )
		continue;   /* found a multiple of an already known prime */

	    mpi_add_ui( ptest, prime, step );

	    /* do a faster Fermat test */
	    count2++;
	    mpi_sub_ui( pminus1, ptest, 1);
	    mpi_powm( result, val_2, pminus1, ptest );
	    if( !mpi_cmp_ui( result, 1 ) ) { /* not composite */
		/* perform stronger tests */
		if( is_prime(ptest, 5, &count2 ) ) {
		    if( !mpi_test_bit( ptest, nbits-1 ) ) {
			progress('\n');
			log_debug("overflow in prime generation\n");
			break; /* step loop, continue with a new prime */
		    }

		    mpi_free(val_2);
		    mpi_free(val_3);
		    mpi_free(result);
		    mpi_free(pminus1);
		    mpi_free(prime);
		    xfree(mods);
		    return ptest;
		}
	    }
	    if( ++dotcount == 10 ) {
		progress('.');
		dotcount = 0;
	    }
	}
	progress(':'); /* restart with a new random value */
    }
}