ceph/src/boost/libs/multiprecision/example/safe_prime.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 //[safe_prime
   7
   8 #include <boost/multiprecision/cpp_int.hpp>
   9 #include <boost/multiprecision/miller_rabin.hpp>
  10 #include <iostream>
  11 #include <iomanip>
  12
  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 //]