Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Primality Testing

The library implements a Miller-Rabin test for primality:

#include <boost/multiprecision/miller_rabin.hpp>

template <class Backend, expression_template_option ExpressionTemplates, class Engine>
bool miller_rabin_test(const number<Backend, ExpressionTemplates>& n, unsigned trials, Engine& gen);

template <class Backend, expression_template_option ExpressionTemplates, class Engine>
bool miller_rabin_test(const number<Backend, ExpressionTemplates>& n, unsigned trials);

These functions perform a Miller-Rabin test for primality, if the result is false then n is definitely composite, while if the result is true then n is probably prime. The probability to declare a composite n as probable prime is at most 0.25trials. Note that this does not allow a statement about the probability of n being actually prime (for that, the prior probability would have to be known). The algorithm used performs some trial divisions to exclude small prime factors, does one Fermat test to exclude many more composites, and then uses the Miller-Rabin algorithm straight out of Knuth Vol 2, which recommends 25 trials for a pretty strong likelihood that n is prime.

The third optional argument is for a Uniform Random Number Generator from Boost.Random. When not provided the mt19937 generator is used. Note that when producing random primes then you should probably use a different random number generator to produce candidate prime numbers for testing, than is used internally by miller_rabin_test for determining whether the value is prime. It also helps of course to seed the generators with some source of randomness.

The following example searches for a prime p for which (p-1)/2 is also probably prime:

#include <boost/random.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
#include <iostream>
#include <iomanip>

int main()
{
   using namespace boost::random;
   using namespace boost::multiprecision;

   typedef cpp_int int_type;
   mt11213b base_gen(clock());
   independent_bits_engine<mt11213b, 256, int_type> gen(base_gen);
   //
   // We must use a different generator for the tests and number generation, otherwise
   // we get false positives.
   //
   mt19937 gen2(clock());

   for(unsigned i = 0; i < 100000; ++i)
   {
      int_type n = gen();
      if(miller_rabin_test(n, 25, gen2))
      {
         // Value n is probably prime, see if (n-1)/2 is also prime:
         std::cout << "We have a probable prime with value: " << std::hex << std::showbase << n << std::endl;
         if(miller_rabin_test((n-1)/2, 25, gen2))
         {
            std::cout << "We have a safe prime with value: " << std::hex << std::showbase << n << std::endl;
            return 0;
         }
      }
   }
   std::cout << "Ooops, no safe primes were found - probably a bad choice of seed values!" << std::endl;
   return 0;
}

PrevUpHomeNext