...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

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 prime with probability *0.25^trials*.
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/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" << std::endl; return 1; }