Botan  1.11.15
src/lib/math/numbertheory/make_prm.cpp
Go to the documentation of this file.
00001 /*
00002 * Prime Generation
00003 * (C) 1999-2007 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/numthry.h>
00009 #include <botan/parsing.h>
00010 #include <algorithm>
00011 
00012 namespace Botan {
00013 
00014 /*
00015 * Generate a random prime
00016 */
00017 BigInt random_prime(RandomNumberGenerator& rng,
00018                     size_t bits, const BigInt& coprime,
00019                     size_t equiv, size_t modulo)
00020    {
00021    if(bits <= 1)
00022       throw Invalid_Argument("random_prime: Can't make a prime of " +
00023                              std::to_string(bits) + " bits");
00024    else if(bits == 2)
00025       return ((rng.next_byte() % 2) ? 2 : 3);
00026    else if(bits == 3)
00027       return ((rng.next_byte() % 2) ? 5 : 7);
00028    else if(bits == 4)
00029       return ((rng.next_byte() % 2) ? 11 : 13);
00030 
00031    if(coprime <= 0)
00032       throw Invalid_Argument("random_prime: coprime must be > 0");
00033    if(modulo % 2 == 1 || modulo == 0)
00034       throw Invalid_Argument("random_prime: Invalid modulo value");
00035    if(equiv >= modulo || equiv % 2 == 0)
00036       throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
00037 
00038    while(true)
00039       {
00040       BigInt p(rng, bits);
00041 
00042       // Force lowest and two top bits on
00043       p.set_bit(bits - 1);
00044       p.set_bit(bits - 2);
00045       p.set_bit(0);
00046 
00047       if(p % modulo != equiv)
00048          p += (modulo - p % modulo) + equiv;
00049 
00050       const size_t sieve_size = std::min(bits / 2, PRIME_TABLE_SIZE);
00051       secure_vector<u16bit> sieve(sieve_size);
00052 
00053       for(size_t j = 0; j != sieve.size(); ++j)
00054          sieve[j] = p % PRIMES[j];
00055 
00056       size_t counter = 0;
00057       while(true)
00058          {
00059          if(counter == 4096 || p.bits() > bits)
00060             break;
00061 
00062          bool passes_sieve = true;
00063          ++counter;
00064          p += modulo;
00065 
00066          if(p.bits() > bits)
00067             break;
00068 
00069          for(size_t j = 0; j != sieve.size(); ++j)
00070             {
00071             sieve[j] = (sieve[j] + modulo) % PRIMES[j];
00072             if(sieve[j] == 0)
00073                passes_sieve = false;
00074             }
00075 
00076          if(!passes_sieve || gcd(p - 1, coprime) != 1)
00077             continue;
00078          if(is_prime(p, rng, 64, true))
00079             return p;
00080          }
00081       }
00082    }
00083 
00084 /*
00085 * Generate a random safe prime
00086 */
00087 BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
00088    {
00089    if(bits <= 64)
00090       throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
00091                              std::to_string(bits) + " bits");
00092 
00093    BigInt p;
00094    do
00095       p = (random_prime(rng, bits - 1) << 1) + 1;
00096    while(!is_prime(p, rng, 64, true));
00097    return p;
00098    }
00099 
00100 }