Библиотека проводит тест Миллера-Рабина на первичность:

#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);

Эти функции выполняют тест Миллера-Рабина на первичность, если результатложный, тоnопределенно композитный, тогда как если результат истинный, то n, вероятно, простой. Вероятность объявить составное n вероятным простым числом составляет максимум 0,25^{испытаний.}. Обратите внимание, что это не позволяет утверждать о вероятности n быть фактически простым (для этого должна быть известна предыдущая вероятность). Используемый алгоритм выполняет некоторые пробные подразделения для исключения небольших простых факторов, выполняет один тест Ферма для исключения многих других композитов, а затем использует алгоритм Миллера-Рабина прямо из Knuth Vol 2, который рекомендует 25 испытаний для довольно высокой вероятности того, чтоnявляется простым.

Третьим необязательным аргументом является унифицированный генератор случайных чисел от Boost. Случайно. При необеспечении используется генераторmt19937. Обратите внимание, что при производстве случайных простых чисел вам, вероятно, следует использовать другой генератор случайных чисел для получения кандидатных простых чисел для тестирования, чем используется внутриmiller_rabin_testдля определения, является ли значение простым. Это также помогает, конечно, сеять генераторы с некоторым источником случайности.

Следующий пример ищет простоеp, для которогоp-1/2также, вероятно, является простым:

#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;
}