bool primality_test(const BigInt& n,
                    RandomNumberGenerator& rng,
                    size_t level)
   {
   const size_t PREF_NONCE_BITS = 128;

   if(n == 2)
      return true;
   if(n <= 1 || n.is_even())
      return false;

   // Fast path testing for small numbers (<= 65521)
   if(n <= PRIMES[PRIME_TABLE_SIZE-1])
      {
      const word num = n.word_at(0);

      for(size_t i = 0; PRIMES[i]; ++i)
         {
         if(num == PRIMES[i])
            return true;
         if(num < PRIMES[i])
            return false;
         }

      return false;
      }

   if(level > 2)
      level = 2;

   const size_t NONCE_BITS = std::min(n.bits() - 2, PREF_NONCE_BITS);

   MillerRabin_Test mr(n);

   if(mr.is_witness(2))
      return false;

   const size_t tests = miller_rabin_test_iterations(n.bits(), level);

   for(size_t i = 0; i != tests; ++i)
      {
      BigInt nonce;
      while(nonce < 2 || nonce >= (n-1))
         nonce.randomize(rng, NONCE_BITS);

      if(mr.is_witness(nonce))
         return false;
      }

   return true;
   }
bool primality_test(const BigInt& n,
                    RandomNumberGenerator& rng,
                    size_t level)
   {
   const size_t PREF_NONCE_BITS = 128;

   if(n == 2)
      return true;
   if(n <= 1 || n.is_even())
      return false;

    
   if(n <= PRIMES[PRIME_TABLE_SIZE-1])
      {
      const word num = n.word_at(0);

      for(size_t i = 0; PRIMES[i]; ++i)
         {
         if(num == PRIMES[i])
            return true;
         if(num < PRIMES[i])
            return false;
         }

      return false;
      }

   if(level > 2)
      level = 2;

   const size_t NONCE_BITS = std::min(n.bits() - 2, PREF_NONCE_BITS);

   MillerRabin_Test mr(n);

   if(mr.is_witness(2))
      return false;

   const size_t tests = miller_rabin_test_iterations(n.bits(), level);

   for(size_t i = 0; i != tests; ++i)
      {
      BigInt nonce;
      while(nonce < 2 || nonce >= (n-1))
         nonce.randomize(rng, NONCE_BITS);

      if(mr.is_witness(nonce))
         return false;
      }

   return true;
   }