/*
* Prime Generation
* (C) 1999-2007 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/numthry.h>
#include <botan/parsing.h>
#include <algorithm>

namespace Botan {

/*
* Generate a random prime
*/
BigInt random_prime(RandomNumberGenerator& rng,
                    size_t bits, const BigInt& coprime,
                    size_t equiv, size_t modulo)
   {
   if(coprime <= 0)
      {
      throw Invalid_Argument("random_prime: coprime must be > 0");
      }
   if(modulo % 2 == 1 || modulo == 0)
      {
      throw Invalid_Argument("random_prime: Invalid modulo value");
      }
   if(equiv >= modulo || equiv % 2 == 0)
      {
      throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
      }

   // Handle small values:
   if(bits <= 1)
      {
      throw Invalid_Argument("random_prime: Can't make a prime of " +
                             std::to_string(bits) + " bits");
      }
   else if(bits == 2)
      {
      return ((rng.next_byte() % 2) ? 2 : 3);
      }
   else if(bits == 3)
      {
      return ((rng.next_byte() % 2) ? 5 : 7);
      }
   else if(bits == 4)
      {
      return ((rng.next_byte() % 2) ? 11 : 13);
      }

   while(true)
      {
      BigInt p(rng, bits);

      // Force lowest and two top bits on
      p.set_bit(bits - 1);
      p.set_bit(bits - 2);
      p.set_bit(0);

      if(p % modulo != equiv)
         p += (modulo - p % modulo) + equiv;

      const size_t sieve_size = std::min(bits / 2, PRIME_TABLE_SIZE);
      secure_vector<u16bit> sieve(sieve_size);

      for(size_t j = 0; j != sieve.size(); ++j)
         sieve[j] = static_cast<u16bit>(p % PRIMES[j]);

      size_t counter = 0;
      while(true)
         {
         ++counter;

         if(counter >= 4096)
            {
            break; // don't try forever, choose a new starting point
            }

         p += modulo;

         if(p.bits() > bits)
            break;

         bool passes_sieve = true;
         for(size_t j = 0; j != sieve.size(); ++j)
            {
            sieve[j] = (sieve[j] + modulo) % PRIMES[j];
            if(sieve[j] == 0)
               {
               passes_sieve = false;
               break;
               }
            }

         if(!passes_sieve)
            continue;

         if(gcd(p - 1, coprime) != 1)
            continue;

         if(is_prime(p, rng, 128, true))
            {
            return p;
            }
         }
      }
   }

/*
* Generate a random safe prime
*/
BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
   {
   if(bits <= 64)
      throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
                             std::to_string(bits) + " bits");

   BigInt p;
   do
      p = (random_prime(rng, bits - 1) << 1) + 1;
   while(!is_prime(p, rng, 128, true));

   return p;
   }

}