...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 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/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; }