summaryrefslogtreecommitdiff
path: root/boost/multiprecision/miller_rabin.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/multiprecision/miller_rabin.hpp')
-rw-r--r--boost/multiprecision/miller_rabin.hpp74
1 files changed, 40 insertions, 34 deletions
diff --git a/boost/multiprecision/miller_rabin.hpp b/boost/multiprecision/miller_rabin.hpp
index 7ce9c8d730..8771993b41 100644
--- a/boost/multiprecision/miller_rabin.hpp
+++ b/boost/multiprecision/miller_rabin.hpp
@@ -6,8 +6,13 @@
#ifndef BOOST_MP_MR_HPP
#define BOOST_MP_MR_HPP
-#include <boost/random.hpp>
+#include <random>
+#include <cstdint>
+#include <type_traits>
+#include <boost/multiprecision/detail/standalone_config.hpp>
#include <boost/multiprecision/integer.hpp>
+#include <boost/multiprecision/detail/uniform_int_distribution.hpp>
+#include <boost/multiprecision/detail/assert.hpp>
namespace boost {
namespace multiprecision {
@@ -16,66 +21,66 @@ namespace detail {
template <class I>
bool check_small_factors(const I& n)
{
- constexpr const std::uint32_t small_factors1[] = {
+ constexpr std::uint32_t small_factors1[] = {
3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u};
- constexpr const std::uint32_t pp1 = 223092870u;
+ constexpr std::uint32_t pp1 = 223092870u;
std::uint32_t m1 = integer_modulus(n, pp1);
- for (unsigned i = 0; i < sizeof(small_factors1) / sizeof(small_factors1[0]); ++i)
+ for (std::size_t i = 0; i < sizeof(small_factors1) / sizeof(small_factors1[0]); ++i)
{
- BOOST_ASSERT(pp1 % small_factors1[i] == 0);
+ BOOST_MP_ASSERT(pp1 % small_factors1[i] == 0);
if (m1 % small_factors1[i] == 0)
return false;
}
- constexpr const std::uint32_t small_factors2[] = {
+ constexpr std::uint32_t small_factors2[] = {
29u, 31u, 37u, 41u, 43u, 47u};
- constexpr const std::uint32_t pp2 = 2756205443u;
+ constexpr std::uint32_t pp2 = 2756205443u;
m1 = integer_modulus(n, pp2);
- for (unsigned i = 0; i < sizeof(small_factors2) / sizeof(small_factors2[0]); ++i)
+ for (std::size_t i = 0; i < sizeof(small_factors2) / sizeof(small_factors2[0]); ++i)
{
- BOOST_ASSERT(pp2 % small_factors2[i] == 0);
+ BOOST_MP_ASSERT(pp2 % small_factors2[i] == 0);
if (m1 % small_factors2[i] == 0)
return false;
}
- constexpr const std::uint32_t small_factors3[] = {
+ constexpr std::uint32_t small_factors3[] = {
53u, 59u, 61u, 67u, 71u};
- constexpr const std::uint32_t pp3 = 907383479u;
+ constexpr std::uint32_t pp3 = 907383479u;
m1 = integer_modulus(n, pp3);
- for (unsigned i = 0; i < sizeof(small_factors3) / sizeof(small_factors3[0]); ++i)
+ for (std::size_t i = 0; i < sizeof(small_factors3) / sizeof(small_factors3[0]); ++i)
{
- BOOST_ASSERT(pp3 % small_factors3[i] == 0);
+ BOOST_MP_ASSERT(pp3 % small_factors3[i] == 0);
if (m1 % small_factors3[i] == 0)
return false;
}
- constexpr const std::uint32_t small_factors4[] = {
+ constexpr std::uint32_t small_factors4[] = {
73u, 79u, 83u, 89u, 97u};
- constexpr const std::uint32_t pp4 = 4132280413u;
+ constexpr std::uint32_t pp4 = 4132280413u;
m1 = integer_modulus(n, pp4);
- for (unsigned i = 0; i < sizeof(small_factors4) / sizeof(small_factors4[0]); ++i)
+ for (std::size_t i = 0; i < sizeof(small_factors4) / sizeof(small_factors4[0]); ++i)
{
- BOOST_ASSERT(pp4 % small_factors4[i] == 0);
+ BOOST_MP_ASSERT(pp4 % small_factors4[i] == 0);
if (m1 % small_factors4[i] == 0)
return false;
}
- constexpr const std::uint32_t small_factors5[6][4] = {
+ constexpr std::uint32_t small_factors5[6][4] = {
{101u, 103u, 107u, 109u},
{113u, 127u, 131u, 137u},
{139u, 149u, 151u, 157u},
{163u, 167u, 173u, 179u},
{181u, 191u, 193u, 197u},
{199u, 211u, 223u, 227u}};
- constexpr const std::uint32_t pp5[6] =
+ constexpr std::uint32_t pp5[6] =
{
121330189u,
113u * 127u * 131u * 137u,
@@ -84,13 +89,13 @@ bool check_small_factors(const I& n)
181u * 191u * 193u * 197u,
199u * 211u * 223u * 227u};
- for (unsigned k = 0; k < sizeof(pp5) / sizeof(*pp5); ++k)
+ for (std::size_t k = 0; k < sizeof(pp5) / sizeof(*pp5); ++k)
{
m1 = integer_modulus(n, pp5[k]);
- for (unsigned i = 0; i < 4; ++i)
+ for (std::size_t i = 0; i < 4; ++i)
{
- BOOST_ASSERT(pp5[k] % small_factors5[k][i] == 0);
+ BOOST_MP_ASSERT(pp5[k] % small_factors5[k][i] == 0);
if (m1 % small_factors5[k][i] == 0)
return false;
}
@@ -98,9 +103,9 @@ bool check_small_factors(const I& n)
return true;
}
-inline bool is_small_prime(unsigned n)
+inline bool is_small_prime(std::size_t n)
{
- constexpr const unsigned char p[] =
+ constexpr unsigned char p[] =
{
3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u, 29u, 31u,
37u, 41u, 43u, 47u, 53u, 59u, 61u, 67u, 71u, 73u,
@@ -108,7 +113,7 @@ inline bool is_small_prime(unsigned n)
127u, 131u, 137u, 139u, 149u, 151u, 157u, 163u,
167u, 173u, 179u, 181u, 191u, 193u, 197u, 199u,
211u, 223u, 227u};
- for (unsigned i = 0; i < sizeof(p) / sizeof(*p); ++i)
+ for (std::size_t i = 0; i < sizeof(p) / sizeof(*p); ++i)
{
if (n == p[i])
return true;
@@ -133,7 +138,7 @@ cast_to_unsigned(const I& val)
template <class I, class Engine>
typename std::enable_if<number_category<I>::value == number_kind_integer, bool>::type
-miller_rabin_test(const I& n, unsigned trials, Engine& gen)
+miller_rabin_test(const I& n, std::size_t trials, Engine& gen)
{
using number_type = I;
@@ -157,19 +162,20 @@ miller_rabin_test(const I& n, unsigned trials, Engine& gen)
return false;
q = n - 1;
- unsigned k = lsb(q);
+ std::size_t k = lsb(q);
q >>= k;
// Declare our random number generator:
- boost::random::uniform_int_distribution<number_type> dist(2, n - 2);
+ boost::multiprecision::uniform_int_distribution<number_type> dist(2, n - 2);
+
//
// Execute the trials:
//
- for (unsigned i = 0; i < trials; ++i)
+ for (std::size_t i = 0; i < trials; ++i)
{
x = dist(gen);
y = powm(x, q, n);
- unsigned j = 0;
+ std::size_t j = 0;
while (true)
{
if (y == nm1)
@@ -190,21 +196,21 @@ miller_rabin_test(const I& n, unsigned trials, Engine& gen)
template <class I>
typename std::enable_if<number_category<I>::value == number_kind_integer, bool>::type
-miller_rabin_test(const I& x, unsigned trials)
+miller_rabin_test(const I& x, std::size_t trials)
{
- static mt19937 gen;
+ static std::mt19937 gen;
return miller_rabin_test(x, trials, gen);
}
template <class tag, class Arg1, class Arg2, class Arg3, class Arg4, class Engine>
-bool miller_rabin_test(const detail::expression<tag, Arg1, Arg2, Arg3, Arg4>& n, unsigned trials, Engine& gen)
+bool miller_rabin_test(const detail::expression<tag, Arg1, Arg2, Arg3, Arg4>& n, std::size_t trials, Engine& gen)
{
using number_type = typename detail::expression<tag, Arg1, Arg2, Arg3, Arg4>::result_type;
return miller_rabin_test(number_type(n), trials, gen);
}
template <class tag, class Arg1, class Arg2, class Arg3, class Arg4>
-bool miller_rabin_test(const detail::expression<tag, Arg1, Arg2, Arg3, Arg4>& n, unsigned trials)
+bool miller_rabin_test(const detail::expression<tag, Arg1, Arg2, Arg3, Arg4>& n, std::size_t trials)
{
using number_type = typename detail::expression<tag, Arg1, Arg2, Arg3, Arg4>::result_type;
return miller_rabin_test(number_type(n), trials);
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-23 08:42:41 +0000