title: Slow Random Prime Generation
body: <p>I am working on a fully homomorphic encryption scheme that requires the generation of very large prime numbers (i.e. 200 digits or more) and currently our method is the biggest bottleneck in our program.We are using Shoup's NTL library, projects we have referenced have used the same library and have had much faster run times.</p>
  
  <p>The function below is used to choose a random prime number Q0 such that lowLimit &lt; Q0 &lt; limit. The library function RandomPrime comes from NTL, it requires a specific number of bits for which your returned prime requires to be represented in binary so I've used the other library function PickRandom which returns a random integer, then I use that integer to determine the number of bits for the prime.</p>
  
  <p>This is by far our biggest run time bottleneck. Is anyone familiar with NTL or any other, more efficient methods of prime number generation?</p>
  
  <pre><code>ZZ chooseQ0(const ZZ &amp;lowLimit, const long &amp;lambda, const ZZ &amp;productOfPrimes){
  ZZ prime, limit, Two, i, Q0, temp, s, last, temp2;
  Two = 2;
  long bits;
  long err = 10;
  
  limit = power(Two, pow(lambda, 5))/productOfPrimes;
  cout &lt;&lt; "Q0 limit: " &lt;&lt; limit &lt;&lt; endl;
  
  srand(time(NULL));
  s = rand()%100;
  SetSeed(s);
  RePick:
  temp = PickRandom(limit);
  if(temp &lt;= lowLimit){
      cout &lt;&lt; "Repicked Q0-1" &lt;&lt; endl;
      goto RePick;
  }
  
  cout &lt;&lt; "Q0 Random Number: " &lt;&lt; temp &lt;&lt; endl;
  redo:
  
  bits = NumBits(temp);
  RandomPrime(temp2, bits, err);
  if(temp2 &lt;= lowLimit || temp2 &gt; limit){
      cout &lt;&lt; "Repicked Q0-2" &lt;&lt; endl;
      goto RePick;
  }
  cout&lt;&lt; "Q0: " &lt;&lt; temp2&lt;&lt; endl;
  return temp2;
  }
  </code></pre>