Botan  1.10.9
make_prm.cpp
Go to the documentation of this file.
1 /*
2 * Prime Generation
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/numthry.h>
9 #include <botan/parsing.h>
10 #include <algorithm>
11 
12 namespace Botan {
13 
14 /*
15 * Generate a random prime
16 */
18  size_t bits, const BigInt& coprime,
19  size_t equiv, size_t modulo)
20  {
21  if(bits <= 1)
22  throw Invalid_Argument("random_prime: Can't make a prime of " +
23  to_string(bits) + " bits");
24  else if(bits == 2)
25  return ((rng.next_byte() % 2) ? 2 : 3);
26  else if(bits == 3)
27  return ((rng.next_byte() % 2) ? 5 : 7);
28  else if(bits == 4)
29  return ((rng.next_byte() % 2) ? 11 : 13);
30 
31  if(coprime <= 0)
32  throw Invalid_Argument("random_prime: coprime must be > 0");
33  if(modulo % 2 == 1 || modulo == 0)
34  throw Invalid_Argument("random_prime: Invalid modulo value");
35  if(equiv >= modulo || equiv % 2 == 0)
36  throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
37 
38  while(true)
39  {
40  BigInt p(rng, bits);
41 
42  // Force lowest and two top bits on
43  p.set_bit(bits - 1);
44  p.set_bit(bits - 2);
45  p.set_bit(0);
46 
47  if(p % modulo != equiv)
48  p += (modulo - p % modulo) + equiv;
49 
50  const size_t sieve_size = std::min(bits / 2, PRIME_TABLE_SIZE);
51  SecureVector<size_t> sieve(sieve_size);
52 
53  for(size_t j = 0; j != sieve.size(); ++j)
54  sieve[j] = p % PRIMES[j];
55 
56  size_t counter = 0;
57  while(true)
58  {
59  if(counter == 4096 || p.bits() > bits)
60  break;
61 
62  bool passes_sieve = true;
63  ++counter;
64  p += modulo;
65 
66  if(p.bits() > bits)
67  break;
68 
69  for(size_t j = 0; j != sieve.size(); ++j)
70  {
71  sieve[j] = (sieve[j] + modulo) % PRIMES[j];
72  if(sieve[j] == 0)
73  passes_sieve = false;
74  }
75 
76  if(!passes_sieve || gcd(p - 1, coprime) != 1)
77  continue;
78  if(check_prime(p, rng))
79  return p;
80  }
81  }
82  }
83 
84 /*
85 * Generate a random safe prime
86 */
88  {
89  if(bits <= 64)
90  throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
91  to_string(bits) + " bits");
92 
93  BigInt p;
94  do
95  p = (random_prime(rng, bits - 1) << 1) + 1;
96  while(!check_prime(p, rng));
97  return p;
98  }
99 
100 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:220
void set_bit(size_t n)
Definition: bigint.cpp:205
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:167
std::invalid_argument Invalid_Argument
Definition: exceptn.h:20
size_t bits() const
Definition: bigint.cpp:253
RandomNumberGenerator * rng
Definition: global_rng.cpp:165
size_t size() const
Definition: secmem.h:29
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:87
std::string to_string(u64bit n, size_t min_len)
Definition: parsing.cpp:42
const u16bit BOTAN_DLL PRIMES[]
Definition: primes.cpp:12
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17
bool check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:143