ceph/src/boost/libs/multiprecision/test/test_miller_rabin.cpp

   1 ///////////////////////////////////////////////////////////////
   2 //  Copyright 2012 John Maddock. Distributed under the Boost
   3 //  Software License, Version 1.0. (See accompanying file
   4 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
   5
   6 #ifdef _MSC_VER
   7 #define _SCL_SECURE_NO_WARNINGS
   8 #endif
   9
  10 #include <boost/multiprecision/gmp.hpp>
  11 #include <boost/multiprecision/cpp_int.hpp>
  12 #include <boost/multiprecision/miller_rabin.hpp>
  13 #include <boost/math/special_functions/prime.hpp>
  14 #include <boost/random.hpp>
  15 #include <random>
  16 #include <iostream>
  17 #include <iomanip>
  18 #include "test.hpp"
  19
  20 template <class I>
  21 void test()
  22 {
  23    //
  24    // Very simple test program to verify that the GMP's Miller-Rabin
  25    // implementation and this one agree on whether some random numbers
  26    // are prime or not.  Of course these are probabilistic tests so there's
  27    // no reason why they should actually agree - except the probability of
  28    // disagreement for 25 trials is almost infinitely small.
  29    //
  30    using namespace boost::random;
  31    using namespace boost::multiprecision;
  32
  33    typedef I test_type;
  34
  35    static const unsigned test_bits =
  36       std::numeric_limits<test_type>::digits && (std::numeric_limits<test_type>::digits <= 256)
  37          ? std::numeric_limits<test_type>::digits
  38          : 128;
  39
  40    independent_bits_engine<mt11213b, test_bits, test_type> gen;
  41    //
  42    // We must use a different generator for the tests and number generation, otherwise
  43    // we get false positives.  Further we use the same random number engine for the
  44    // Miller Rabin test as GMP uses internally:
  45    //
  46    mt19937 gen2;
  47
  48    //
  49    // Begin by testing the primes in our table as all these should return true:
  50    //
  51    for (unsigned i = 1; i < boost::math::max_prime; ++i)
  52    {
  53       BOOST_TEST(miller_rabin_test(test_type(boost::math::prime(i)), 25, gen));
  54       BOOST_TEST(mpz_probab_prime_p(mpz_int(boost::math::prime(i)).backend().data(), 25));
  55    }
  56    //
  57    // Now test some random values and compare GMP's native routine with ours.
  58    //
  59    for (unsigned i = 0; i < 10000; ++i)
  60    {
  61       test_type n              = gen();
  62       bool      is_prime_boost = miller_rabin_test(n, 25, gen2);
  63       bool      is_gmp_prime   = mpz_probab_prime_p(mpz_int(n).backend().data(), 25) ? true : false;
  64       if (is_prime_boost && is_gmp_prime)
  65       {
  66          std::cout << "We have a prime: " << std::hex << std::showbase << n << std::endl;
  67       }
  68       if (is_prime_boost != is_gmp_prime)
  69          std::cout << std::hex << std::showbase << "n = " << n << std::endl;
  70       BOOST_CHECK_EQUAL(is_prime_boost, is_gmp_prime);
  71    }
  72 }
  73
  74 int main()
  75 {
  76    using namespace boost::multiprecision;
  77
  78    test<mpz_int>();
  79    test<number<gmp_int, et_off> >();
  80    test<std::uint64_t>();
  81    test<std::uint32_t>();
  82
  83    test<cpp_int>();
  84    test<number<cpp_int_backend<64, 64, unsigned_magnitude, checked, void>, et_off> >();
  85    test<checked_uint128_t>();
  86    test<checked_uint1024_t>();
  87
  88    return boost::report_errors();
  89 }