ceph/src/boost/libs/multiprecision/doc/html/boost_multiprecision/tut/primetest.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Primality Testing</title>
   5 <link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
   7 <link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;Boost.Multiprecision">
   8 <link rel="up" href="../tut.html" title="Tutorial">
   9 <link rel="prev" href="random.html" title="Generating Random Numbers">
  10 <link rel="next" href="lits.html" title="Literal Types and constexpr Support">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="random.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../tut.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="lits.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="boost_multiprecision.tut.primetest"></a><a class="link" href="primetest.html" title="Primality Testing">Primality Testing</a>
  28 </h3></div></div></div>
  29 <p>
  30         The library implements a Miller-Rabin test for primality:
  31       </p>
  32 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">multiprecision</span><span class="special">/</span><span class="identifier">miller_rabin</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  33
  34 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Backend</span><span class="special">,</span> <span class="identifier">expression_template_option</span> <span class="identifier">ExpressionTemplates</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Engine</span><span class="special">&gt;</span>
  35 <span class="keyword">bool</span> <span class="identifier">miller_rabin_test</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">number</span><span class="special">&lt;</span><span class="identifier">Backend</span><span class="special">,</span> <span class="identifier">ExpressionTemplates</span><span class="special">&gt;&amp;</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">trials</span><span class="special">,</span> <span class="identifier">Engine</span><span class="special">&amp;</span> <span class="identifier">gen</span><span class="special">);</span>
  36
  37 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Backend</span><span class="special">,</span> <span class="identifier">expression_template_option</span> <span class="identifier">ExpressionTemplates</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Engine</span><span class="special">&gt;</span>
  38 <span class="keyword">bool</span> <span class="identifier">miller_rabin_test</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">number</span><span class="special">&lt;</span><span class="identifier">Backend</span><span class="special">,</span> <span class="identifier">ExpressionTemplates</span><span class="special">&gt;&amp;</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">trials</span><span class="special">);</span>
  39 </pre>
  40 <p>
  41         These functions perform a Miller-Rabin test for primality, if the result
  42         is <code class="computeroutput"><span class="keyword">false</span></code> then <span class="emphasis"><em>n</em></span>
  43         is definitely composite, while if the result is true then n is probably prime.
  44         The probability to declare a composite n as probable prime is at most 0.25<sup>trials</sup>.
  45         Note that this does not allow a statement about the probability of n being
  46         actually prime (for that, the prior probability would have to be known).
  47         The algorithm used performs some trial divisions to exclude small prime factors,
  48         does one Fermat test to exclude many more composites, and then uses the Miller-Rabin
  49         algorithm straight out of Knuth Vol 2, which recommends 25 trials for a pretty
  50         strong likelihood that <span class="emphasis"><em>n</em></span> is prime.
  51       </p>
  52 <p>
  53         The third optional argument is for a Uniform Random Number Generator from
  54         Boost.Random. When not provided the <code class="computeroutput"><span class="identifier">mt19937</span></code>
  55         generator is used. Note that when producing random primes then you should
  56         probably use a different random number generator to produce candidate prime
  57         numbers for testing, than is used internally by <code class="computeroutput"><span class="identifier">miller_rabin_test</span></code>
  58         for determining whether the value is prime. It also helps of course to seed
  59         the generators with some source of randomness.
  60       </p>
  61 <p>
  62         The following example searches for a prime <code class="computeroutput"><span class="identifier">p</span></code>
  63         for which <code class="computeroutput"><span class="special">(</span><span class="identifier">p</span><span class="special">-</span><span class="number">1</span><span class="special">)/</span><span class="number">2</span></code> is also probably prime:
  64       </p>
  65 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">multiprecision</span><span class="special">/</span><span class="identifier">cpp_int</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  66 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">multiprecision</span><span class="special">/</span><span class="identifier">miller_rabin</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  67 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">iostream</span><span class="special">&gt;</span>
  68 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">iomanip</span><span class="special">&gt;</span>
  69
  70 <span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
  71 <span class="special">{</span>
  72    <span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">random</span><span class="special">;</span>
  73    <span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">multiprecision</span><span class="special">;</span>
  74
  75    <span class="keyword">typedef</span> <span class="identifier">cpp_int</span> <span class="identifier">int_type</span><span class="special">;</span>
  76    <span class="identifier">mt11213b</span> <span class="identifier">base_gen</span><span class="special">(</span><span class="identifier">clock</span><span class="special">());</span>
  77    <span class="identifier">independent_bits_engine</span><span class="special">&lt;</span><span class="identifier">mt11213b</span><span class="special">,</span> <span class="number">256</span><span class="special">,</span> <span class="identifier">int_type</span><span class="special">&gt;</span> <span class="identifier">gen</span><span class="special">(</span><span class="identifier">base_gen</span><span class="special">);</span>
  78    <span class="comment">//</span>
  79    <span class="comment">// We must use a different generator for the tests and number generation, otherwise</span>
  80    <span class="comment">// we get false positives.</span>
  81    <span class="comment">//</span>
  82    <span class="identifier">mt19937</span> <span class="identifier">gen2</span><span class="special">(</span><span class="identifier">clock</span><span class="special">());</span>
  83
  84    <span class="keyword">for</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special">&lt;</span> <span class="number">100000</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span>
  85    <span class="special">{</span>
  86       <span class="identifier">int_type</span> <span class="identifier">n</span> <span class="special">=</span> <span class="identifier">gen</span><span class="special">();</span>
  87       <span class="keyword">if</span><span class="special">(</span><span class="identifier">miller_rabin_test</span><span class="special">(</span><span class="identifier">n</span><span class="special">,</span> <span class="number">25</span><span class="special">,</span> <span class="identifier">gen2</span><span class="special">))</span>
  88       <span class="special">{</span>
  89          <span class="comment">// Value n is probably prime, see if (n-1)/2 is also prime:</span>
  90          <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"We have a probable prime with value: "</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">hex</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">showbase</span> <span class="special">&lt;&lt;</span> <span class="identifier">n</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
  91          <span class="keyword">if</span><span class="special">(</span><span class="identifier">miller_rabin_test</span><span class="special">((</span><span class="identifier">n</span><span class="special">-</span><span class="number">1</span><span class="special">)/</span><span class="number">2</span><span class="special">,</span> <span class="number">25</span><span class="special">,</span> <span class="identifier">gen2</span><span class="special">))</span>
  92          <span class="special">{</span>
  93             <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"We have a safe prime with value: "</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">hex</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">showbase</span> <span class="special">&lt;&lt;</span> <span class="identifier">n</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
  94             <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
  95          <span class="special">}</span>
  96       <span class="special">}</span>
  97    <span class="special">}</span>
  98    <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"Ooops, no safe primes were found"</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
  99    <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span>
 100 <span class="special">}</span>
 101 </pre>
 102 </div>
 103 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 104 <td align="left"></td>
 105 <td align="right"><div class="copyright-footer">Copyright &#169; 2002-2013 John Maddock and Christopher Kormanyos<p>
 106         Distributed under the Boost Software License, Version 1.0. (See accompanying
 107         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
 108       </p>
 109 </div></td>
 110 </tr></table>
 111 <hr>
 112 <div class="spirit-nav">
 113 <a accesskey="p" href="random.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../tut.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="lits.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 114 </div>
 115 </body>
 116 </html>