41 lines
2.1 KiB
Plaintext
41 lines
2.1 KiB
Plaintext
|
[/
|
||
|
|
Copyright 2011 - 2020 John Maddock.
|
||
|
|
Copyright 2013 - 2019 Paul A. Bristow.
|
||
|
|
Copyright 2013 Christopher Kormanyos.
|
||
|
|
|
||
|
|
Distributed under the Boost Software License, Version 1.0.
|
||
|
|
(See accompanying file LICENSE_1_0.txt or copy at
|
||
|
|
http://www.boost.org/LICENSE_1_0.txt).
|
||
|
|
]
|
||
|
|
|
||
|
|
[section:primetest Primality Testing]
|
||
|
|
|
||
|
|
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.25[super trials]. 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:
|
||
|
|
|
||
|
|
[safe_prime]
|
||
|
|
|
||
|
|
[endsect] [/section:primetest Primality Testing]
|