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 //[safe_prime
7
8 #include <boost/multiprecision/cpp_int.hpp>
9 #include <boost/multiprecision/miller_rabin.hpp>
10 #include <iostream>
11 #include <iomanip>
12
main()13 int main()
14 {
15 using namespace boost::random;
16 using namespace boost::multiprecision;
17
18 typedef cpp_int int_type;
19 mt11213b base_gen(clock());
20 independent_bits_engine<mt11213b, 256, int_type> gen(base_gen);
21 //
22 // We must use a different generator for the tests and number generation, otherwise
23 // we get false positives.
24 //
25 mt19937 gen2(clock());
26
27 for(unsigned i = 0; i < 100000; ++i)
28 {
29 int_type n = gen();
30 if(miller_rabin_test(n, 25, gen2))
31 {
32 // Value n is probably prime, see if (n-1)/2 is also prime:
33 std::cout << "We have a probable prime with value: " << std::hex << std::showbase << n << std::endl;
34 if(miller_rabin_test((n-1)/2, 25, gen2))
35 {
36 std::cout << "We have a safe prime with value: " << std::hex << std::showbase << n << std::endl;
37 return 0;
38 }
39 }
40 }
41 std::cout << "Ooops, no safe primes were found - probably a bad choice of seed values!" << std::endl;
42 return 0;
43 }
44
45 //]
46