<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.14"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Crypto++: nbtheory.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td id="projectalign" style="padding-left: 0.5em;">
<div id="projectname">Crypto++
 <span id="projectnumber">7.0</span>
</div>
<div id="projectbrief">Free C++ class library of cryptographic schemes</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.14 -->
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&dn=gpl-2.0.txt GPL-v2 */
$(function() {
initMenu('',false,false,'search.php','Search');
});
/* @license-end */</script>
<div id="main-nav"></div>
</div><!-- top -->
<div class="header">
<div class="headertitle">
<div class="title">nbtheory.h</div> </div>
</div><!--header-->
<div class="contents">
<a href="nbtheory_8h.html">Go to the documentation of this file.</a><div class="fragment"><div class="line"><a name="l00001"></a><span class="lineno"> 1</span> <span class="comment">// nbtheory.h - originally written and placed in the public domain by Wei Dai</span></div><div class="line"><a name="l00002"></a><span class="lineno"> 2</span> <span class="comment"></span></div><div class="line"><a name="l00003"></a><span class="lineno"> 3</span> <span class="comment">/// \file nbtheory.h</span></div><div class="line"><a name="l00004"></a><span class="lineno"> 4</span> <span class="comment">/// \brief Classes and functions for number theoretic operations</span></div><div class="line"><a name="l00005"></a><span class="lineno"> 5</span> <span class="comment"></span></div><div class="line"><a name="l00006"></a><span class="lineno"> 6</span> <span class="preprocessor">#ifndef CRYPTOPP_NBTHEORY_H</span></div><div class="line"><a name="l00007"></a><span class="lineno"> 7</span> <span class="preprocessor">#define CRYPTOPP_NBTHEORY_H</span></div><div class="line"><a name="l00008"></a><span class="lineno"> 8</span> </div><div class="line"><a name="l00009"></a><span class="lineno"> 9</span> <span class="preprocessor">#include "<a class="code" href="cryptlib_8h.html">cryptlib.h</a>"</span></div><div class="line"><a name="l00010"></a><span class="lineno"> 10</span> <span class="preprocessor">#include "<a class="code" href="integer_8h.html">integer.h</a>"</span></div><div class="line"><a name="l00011"></a><span class="lineno"> 11</span> <span class="preprocessor">#include "<a class="code" href="algparam_8h.html">algparam.h</a>"</span></div><div class="line"><a name="l00012"></a><span class="lineno"> 12</span> </div><div class="line"><a name="l00013"></a><span class="lineno"> 13</span> NAMESPACE_BEGIN(<a class="code" href="namespace_crypto_p_p.html">CryptoPP</a>)</div><div class="line"><a name="l00014"></a><span class="lineno"> 14</span> </div><div class="line"><a name="l00015"></a><span class="lineno"> 15</span> <span class="comment">/// \brief The Small Prime table</span></div><div class="line"><a name="l00016"></a><span class="lineno"> 16</span> <span class="comment"></span><span class="comment">/// \details GetPrimeTable obtains pointer to small prime table and provides the size of the table.</span></div><div class="line"><a name="l00017"></a><span class="lineno"> 17</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keyword">const</span> word16 * CRYPTOPP_API <a class="code" href="nbtheory_8h.html#aa41f53fa846ea7546d7269b5d5c6a29f">GetPrimeTable</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> &size);</div><div class="line"><a name="l00018"></a><span class="lineno"> 18</span> </div><div class="line"><a name="l00019"></a><span class="lineno"> 19</span> <span class="comment">// ************ primality testing ****************</span></div><div class="line"><a name="l00020"></a><span class="lineno"> 20</span> <span class="comment"></span></div><div class="line"><a name="l00021"></a><span class="lineno"> 21</span> <span class="comment">/// \brief Generates a provable prime</span></div><div class="line"><a name="l00022"></a><span class="lineno"> 22</span> <span class="comment">/// \param rng a RandomNumberGenerator to produce random material</span></div><div class="line"><a name="l00023"></a><span class="lineno"> 23</span> <span class="comment">/// \param bits the number of bits in the prime number</span></div><div class="line"><a name="l00024"></a><span class="lineno"> 24</span> <span class="comment">/// \returns Integer() meeting Maurer's tests for primality</span></div><div class="line"><a name="l00025"></a><span class="lineno"> 25</span> <span class="comment"></span>CRYPTOPP_DLL <a class="code" href="class_integer.html">Integer</a> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a4f5215dbaaf83eacf300ef54f0e941fc">MaurerProvablePrime</a>(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bits);</div><div class="line"><a name="l00026"></a><span class="lineno"> 26</span> <span class="comment"></span></div><div class="line"><a name="l00027"></a><span class="lineno"> 27</span> <span class="comment">/// \brief Generates a provable prime</span></div><div class="line"><a name="l00028"></a><span class="lineno"> 28</span> <span class="comment">/// \param rng a RandomNumberGenerator to produce random material</span></div><div class="line"><a name="l00029"></a><span class="lineno"> 29</span> <span class="comment">/// \param bits the number of bits in the prime number</span></div><div class="line"><a name="l00030"></a><span class="lineno"> 30</span> <span class="comment">/// \returns Integer() meeting Mihailescu's tests for primality</span></div><div class="line"><a name="l00031"></a><span class="lineno"> 31</span> <span class="comment">/// \details Mihailescu's methods performs a search using algorithmic progressions.</span></div><div class="line"><a name="l00032"></a><span class="lineno"> 32</span> <span class="comment"></span>CRYPTOPP_DLL <a class="code" href="class_integer.html">Integer</a> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a40fab13239e32e04892023c81bb42597">MihailescuProvablePrime</a>(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bits);</div><div class="line"><a name="l00033"></a><span class="lineno"> 33</span> <span class="comment"></span></div><div class="line"><a name="l00034"></a><span class="lineno"> 34</span> <span class="comment">/// \brief Tests whether a number is a small prime</span></div><div class="line"><a name="l00035"></a><span class="lineno"> 35</span> <span class="comment">/// \param p a candidate prime to test</span></div><div class="line"><a name="l00036"></a><span class="lineno"> 36</span> <span class="comment">/// \returns true if p is a small prime, false otherwise</span></div><div class="line"><a name="l00037"></a><span class="lineno"> 37</span> <span class="comment">/// \details Internally, the library maintains a table of the first 32719 prime numbers</span></div><div class="line"><a name="l00038"></a><span class="lineno"> 38</span> <span class="comment">/// in sorted order. IsSmallPrime searches the table and returns true if p is</span></div><div class="line"><a name="l00039"></a><span class="lineno"> 39</span> <span class="comment">/// in the table.</span></div><div class="line"><a name="l00040"></a><span class="lineno"> 40</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a7bfb6022241ff5fb96250e366c68d49e">IsSmallPrime</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p);</div><div class="line"><a name="l00041"></a><span class="lineno"> 41</span> <span class="comment"></span></div><div class="line"><a name="l00042"></a><span class="lineno"> 42</span> <span class="comment">/// \brief Tests whether a number is divisible by a small prime</span></div><div class="line"><a name="l00043"></a><span class="lineno"> 43</span> <span class="comment">/// \returns true if p is divisible by some prime less than bound.</span></div><div class="line"><a name="l00044"></a><span class="lineno"> 44</span> <span class="comment">/// \details TrialDivision() returns <tt>true</tt> if <tt>p</tt> is divisible by some prime less</span></div><div class="line"><a name="l00045"></a><span class="lineno"> 45</span> <span class="comment">/// than <tt>bound</tt>. <tt>bound</tt> should not be greater than the largest entry in the</span></div><div class="line"><a name="l00046"></a><span class="lineno"> 46</span> <span class="comment">/// prime table, which is 32719.</span></div><div class="line"><a name="l00047"></a><span class="lineno"> 47</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#aef5a456e724cba394ff8ad788eae777d">TrialDivision</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p, <span class="keywordtype">unsigned</span> bound);</div><div class="line"><a name="l00048"></a><span class="lineno"> 48</span> <span class="comment"></span></div><div class="line"><a name="l00049"></a><span class="lineno"> 49</span> <span class="comment">/// \brief Tests whether a number is divisible by a small prime</span></div><div class="line"><a name="l00050"></a><span class="lineno"> 50</span> <span class="comment">/// \returns true if p is NOT divisible by small primes.</span></div><div class="line"><a name="l00051"></a><span class="lineno"> 51</span> <span class="comment">/// \details SmallDivisorsTest() returns <tt>true</tt> if <tt>p</tt> is NOT divisible by some</span></div><div class="line"><a name="l00052"></a><span class="lineno"> 52</span> <span class="comment">/// prime less than 32719.</span></div><div class="line"><a name="l00053"></a><span class="lineno"> 53</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a7d7be62fa8075e10432f49cc08273707">SmallDivisorsTest</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p);</div><div class="line"><a name="l00054"></a><span class="lineno"> 54</span> <span class="comment"></span></div><div class="line"><a name="l00055"></a><span class="lineno"> 55</span> <span class="comment">/// \brief Determine if a number is probably prime</span></div><div class="line"><a name="l00056"></a><span class="lineno"> 56</span> <span class="comment">/// \param n the number to test</span></div><div class="line"><a name="l00057"></a><span class="lineno"> 57</span> <span class="comment">/// \param b the base to exponentiate</span></div><div class="line"><a name="l00058"></a><span class="lineno"> 58</span> <span class="comment">/// \returns true if the number n is probably prime, false otherwise.</span></div><div class="line"><a name="l00059"></a><span class="lineno"> 59</span> <span class="comment">/// \details IsFermatProbablePrime raises <tt>b</tt> to the <tt>n-1</tt> power and checks if</span></div><div class="line"><a name="l00060"></a><span class="lineno"> 60</span> <span class="comment">/// the result is congruent to 1 modulo <tt>n</tt>.</span></div><div class="line"><a name="l00061"></a><span class="lineno"> 61</span> <span class="comment">/// \details These is no reason to use IsFermatProbablePrime, use IsStrongProbablePrime or</span></div><div class="line"><a name="l00062"></a><span class="lineno"> 62</span> <span class="comment">/// IsStrongLucasProbablePrime instead.</span></div><div class="line"><a name="l00063"></a><span class="lineno"> 63</span> <span class="comment">/// \sa IsStrongProbablePrime, IsStrongLucasProbablePrime</span></div><div class="line"><a name="l00064"></a><span class="lineno"> 64</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#abcaf62227292dc648e6f2f11f2a6e158">IsFermatProbablePrime</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &n, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b);</div><div class="line"><a name="l00065"></a><span class="lineno"> 65</span> <span class="comment"></span></div><div class="line"><a name="l00066"></a><span class="lineno"> 66</span> <span class="comment">/// \brief Determine if a number is probably prime</span></div><div class="line"><a name="l00067"></a><span class="lineno"> 67</span> <span class="comment">/// \param n the number to test</span></div><div class="line"><a name="l00068"></a><span class="lineno"> 68</span> <span class="comment">/// \returns true if the number n is probably prime, false otherwise.</span></div><div class="line"><a name="l00069"></a><span class="lineno"> 69</span> <span class="comment">/// \details These is no reason to use IsLucasProbablePrime, use IsStrongProbablePrime or</span></div><div class="line"><a name="l00070"></a><span class="lineno"> 70</span> <span class="comment">/// IsStrongLucasProbablePrime instead.</span></div><div class="line"><a name="l00071"></a><span class="lineno"> 71</span> <span class="comment">/// \sa IsStrongProbablePrime, IsStrongLucasProbablePrime</span></div><div class="line"><a name="l00072"></a><span class="lineno"> 72</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#aada479f79cb8988f4df16df1e321fc7b">IsLucasProbablePrime</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &n);</div><div class="line"><a name="l00073"></a><span class="lineno"> 73</span> <span class="comment"></span></div><div class="line"><a name="l00074"></a><span class="lineno"> 74</span> <span class="comment">/// \brief Determine if a number is probably prime</span></div><div class="line"><a name="l00075"></a><span class="lineno"> 75</span> <span class="comment">/// \param n the number to test</span></div><div class="line"><a name="l00076"></a><span class="lineno"> 76</span> <span class="comment">/// \param b the base to exponentiate</span></div><div class="line"><a name="l00077"></a><span class="lineno"> 77</span> <span class="comment">/// \returns true if the number n is probably prime, false otherwise.</span></div><div class="line"><a name="l00078"></a><span class="lineno"> 78</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a97c6199f98f7c5174373422d1e1c39af">IsStrongProbablePrime</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &n, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b);</div><div class="line"><a name="l00079"></a><span class="lineno"> 79</span> <span class="comment"></span></div><div class="line"><a name="l00080"></a><span class="lineno"> 80</span> <span class="comment">/// \brief Determine if a number is probably prime</span></div><div class="line"><a name="l00081"></a><span class="lineno"> 81</span> <span class="comment">/// \param n the number to test</span></div><div class="line"><a name="l00082"></a><span class="lineno"> 82</span> <span class="comment">/// \returns true if the number n is probably prime, false otherwise.</span></div><div class="line"><a name="l00083"></a><span class="lineno"> 83</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a9167952dad6998d1b854dee8355b53a0">IsStrongLucasProbablePrime</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &n);</div><div class="line"><a name="l00084"></a><span class="lineno"> 84</span> <span class="comment"></span></div><div class="line"><a name="l00085"></a><span class="lineno"> 85</span> <span class="comment">/// \brief Determine if a number is probably prime</span></div><div class="line"><a name="l00086"></a><span class="lineno"> 86</span> <span class="comment">/// \param rng a RandomNumberGenerator to produce random material</span></div><div class="line"><a name="l00087"></a><span class="lineno"> 87</span> <span class="comment">/// \param n the number to test</span></div><div class="line"><a name="l00088"></a><span class="lineno"> 88</span> <span class="comment">/// \param rounds the number of tests to perform</span></div><div class="line"><a name="l00089"></a><span class="lineno"> 89</span> <span class="comment">/// \details This is the Rabin-Miller primality test, i.e. repeating the strong probable prime</span></div><div class="line"><a name="l00090"></a><span class="lineno"> 90</span> <span class="comment">/// test for several rounds with random bases</span></div><div class="line"><a name="l00091"></a><span class="lineno"> 91</span> <span class="comment">/// \sa <A HREF="https://crypto.stackexchange.com/q/17707/10496">Trial divisions before</span></div><div class="line"><a name="l00092"></a><span class="lineno"> 92</span> <span class="comment">/// Miller-Rabin checks?</A> on Crypto Stack Exchange</span></div><div class="line"><a name="l00093"></a><span class="lineno"> 93</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a637fa2abf1a48bc38f3c0d7c7edd679a">RabinMillerTest</a>(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &n, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> rounds);</div><div class="line"><a name="l00094"></a><span class="lineno"> 94</span> <span class="comment"></span></div><div class="line"><a name="l00095"></a><span class="lineno"> 95</span> <span class="comment">/// \brief Verifies a number is probably prime</span></div><div class="line"><a name="l00096"></a><span class="lineno"> 96</span> <span class="comment">/// \param p a candidate prime to test</span></div><div class="line"><a name="l00097"></a><span class="lineno"> 97</span> <span class="comment">/// \returns true if p is a probable prime, false otherwise</span></div><div class="line"><a name="l00098"></a><span class="lineno"> 98</span> <span class="comment">/// \details IsPrime() is suitable for testing candidate primes when creating them. Internally,</span></div><div class="line"><a name="l00099"></a><span class="lineno"> 99</span> <span class="comment">/// IsPrime() utilizes SmallDivisorsTest(), IsStrongProbablePrime() and IsStrongLucasProbablePrime().</span></div><div class="line"><a name="l00100"></a><span class="lineno"> 100</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#ae8442dd787d99d3604436a91799552bf">IsPrime</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p);</div><div class="line"><a name="l00101"></a><span class="lineno"> 101</span> <span class="comment"></span></div><div class="line"><a name="l00102"></a><span class="lineno"> 102</span> <span class="comment">/// \brief Verifies a number is probably prime</span></div><div class="line"><a name="l00103"></a><span class="lineno"> 103</span> <span class="comment">/// \param rng a RandomNumberGenerator for randomized testing</span></div><div class="line"><a name="l00104"></a><span class="lineno"> 104</span> <span class="comment">/// \param p a candidate prime to test</span></div><div class="line"><a name="l00105"></a><span class="lineno"> 105</span> <span class="comment">/// \param level the level of thoroughness of testing</span></div><div class="line"><a name="l00106"></a><span class="lineno"> 106</span> <span class="comment">/// \returns true if p is a strong probable prime, false otherwise</span></div><div class="line"><a name="l00107"></a><span class="lineno"> 107</span> <span class="comment">/// \details VerifyPrime() is suitable for testing candidate primes created by others. Internally,</span></div><div class="line"><a name="l00108"></a><span class="lineno"> 108</span> <span class="comment">/// VerifyPrime() utilizes IsPrime() and one-round RabinMillerTest(). If the candiate passes and</span></div><div class="line"><a name="l00109"></a><span class="lineno"> 109</span> <span class="comment">/// level is greater than 1, then 10 round RabinMillerTest() primality testing is performed.</span></div><div class="line"><a name="l00110"></a><span class="lineno"> 110</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a633d17045e229eccc3614426df054463">VerifyPrime</a>(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> level = 1);</div><div class="line"><a name="l00111"></a><span class="lineno"> 111</span> <span class="comment"></span></div><div class="line"><a name="l00112"></a><span class="lineno"> 112</span> <span class="comment">/// \brief Application callback to signal suitability of a cabdidate prime</span></div><div class="line"><a name="l00113"></a><span class="lineno"><a class="line" href="class_prime_selector.html"> 113</a></span> <span class="comment"></span><span class="keyword">class </span>CRYPTOPP_DLL <a class="code" href="class_prime_selector.html">PrimeSelector</a></div><div class="line"><a name="l00114"></a><span class="lineno"> 114</span> {</div><div class="line"><a name="l00115"></a><span class="lineno"> 115</span> <span class="keyword">public</span>:</div><div class="line"><a name="l00116"></a><span class="lineno"> 116</span>  <span class="keyword">const</span> <a class="code" href="class_prime_selector.html">PrimeSelector</a> *GetSelectorPointer()<span class="keyword"> const </span>{<span class="keywordflow">return</span> <span class="keyword">this</span>;}</div><div class="line"><a name="l00117"></a><span class="lineno"> 117</span>  <span class="keyword">virtual</span> <span class="keywordtype">bool</span> IsAcceptable(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &candidate) <span class="keyword">const</span> =0;</div><div class="line"><a name="l00118"></a><span class="lineno"> 118</span> };</div><div class="line"><a name="l00119"></a><span class="lineno"> 119</span> <span class="comment"></span></div><div class="line"><a name="l00120"></a><span class="lineno"> 120</span> <span class="comment">/// \brief Finds a random prime of special form</span></div><div class="line"><a name="l00121"></a><span class="lineno"> 121</span> <span class="comment">/// \param p an Integer reference to receive the prime</span></div><div class="line"><a name="l00122"></a><span class="lineno"> 122</span> <span class="comment">/// \param max the maximum value</span></div><div class="line"><a name="l00123"></a><span class="lineno"> 123</span> <span class="comment">/// \param equiv the equivalence class based on the parameter mod</span></div><div class="line"><a name="l00124"></a><span class="lineno"> 124</span> <span class="comment">/// \param mod the modulus used to reduce the equivalence class</span></div><div class="line"><a name="l00125"></a><span class="lineno"> 125</span> <span class="comment">/// \param pSelector pointer to a PrimeSelector function for the application to signal suitability</span></div><div class="line"><a name="l00126"></a><span class="lineno"> 126</span> <span class="comment">/// \returns true if and only if FirstPrime() finds a prime and returns the prime through p. If FirstPrime()</span></div><div class="line"><a name="l00127"></a><span class="lineno"> 127</span> <span class="comment">/// returns false, then no such prime exists and the value of p is undefined</span></div><div class="line"><a name="l00128"></a><span class="lineno"> 128</span> <span class="comment">/// \details FirstPrime() uses a fast sieve to find the first probable prime</span></div><div class="line"><a name="l00129"></a><span class="lineno"> 129</span> <span class="comment">/// in <tt>{x | p<=x<=max and x%mod==equiv}</tt></span></div><div class="line"><a name="l00130"></a><span class="lineno"> 130</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#aaef9ef9567713cd9935e468309ebcc9d">FirstPrime</a>(<a class="code" href="class_integer.html">Integer</a> &p, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &max, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &equiv, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &mod, <span class="keyword">const</span> <a class="code" href="class_prime_selector.html">PrimeSelector</a> *pSelector);</div><div class="line"><a name="l00131"></a><span class="lineno"> 131</span> </div><div class="line"><a name="l00132"></a><span class="lineno"> 132</span> CRYPTOPP_DLL <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> CRYPTOPP_API PrimeSearchInterval(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &max);</div><div class="line"><a name="l00133"></a><span class="lineno"> 133</span> </div><div class="line"><a name="l00134"></a><span class="lineno"> 134</span> CRYPTOPP_DLL <a class="code" href="class_algorithm_parameters.html">AlgorithmParameters</a> CRYPTOPP_API MakeParametersForTwoPrimesOfEqualSize(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> productBitLength);</div><div class="line"><a name="l00135"></a><span class="lineno"> 135</span> </div><div class="line"><a name="l00136"></a><span class="lineno"> 136</span> <span class="comment">// ********** other number theoretic functions ************</span></div><div class="line"><a name="l00137"></a><span class="lineno"> 137</span> <span class="comment"></span></div><div class="line"><a name="l00138"></a><span class="lineno"> 138</span> <span class="comment">/// \brief Calculate the greatest common divisor</span></div><div class="line"><a name="l00139"></a><span class="lineno"> 139</span> <span class="comment">/// \param a the first term</span></div><div class="line"><a name="l00140"></a><span class="lineno"> 140</span> <span class="comment">/// \param b the second term</span></div><div class="line"><a name="l00141"></a><span class="lineno"> 141</span> <span class="comment">/// \returns the greatest common divisor if one exists, 0 otherwise.</span></div><div class="line"><a name="l00142"></a><span class="lineno"><a class="line" href="nbtheory_8h.html#ac1d98aa1d0ed1df97bf0dc194da5169a"> 142</a></span> <span class="comment"></span><span class="keyword">inline</span> <a class="code" href="class_integer.html">Integer</a> <a class="code" href="nbtheory_8h.html#ac1d98aa1d0ed1df97bf0dc194da5169a">GCD</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)</div><div class="line"><a name="l00143"></a><span class="lineno"> 143</span>  {<span class="keywordflow">return</span> <a class="code" href="class_integer.html#a2d4d29937f8ef666717530b30f137c37">Integer::Gcd</a>(a,b);}</div><div class="line"><a name="l00144"></a><span class="lineno"> 144</span> <span class="comment"></span></div><div class="line"><a name="l00145"></a><span class="lineno"> 145</span> <span class="comment">/// \brief Determine relative primality</span></div><div class="line"><a name="l00146"></a><span class="lineno"> 146</span> <span class="comment">/// \param a the first term</span></div><div class="line"><a name="l00147"></a><span class="lineno"> 147</span> <span class="comment">/// \param b the second term</span></div><div class="line"><a name="l00148"></a><span class="lineno"> 148</span> <span class="comment">/// \returns true if <tt>a</tt> and <tt>b</tt> are relatively prime, false otherwise.</span></div><div class="line"><a name="l00149"></a><span class="lineno"><a class="line" href="nbtheory_8h.html#a1653aff24d226faac1ff141e665ef9e1"> 149</a></span> <span class="comment"></span><span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="nbtheory_8h.html#a1653aff24d226faac1ff141e665ef9e1">RelativelyPrime</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)</div><div class="line"><a name="l00150"></a><span class="lineno"> 150</span>  {<span class="keywordflow">return</span> <a class="code" href="class_integer.html#a2d4d29937f8ef666717530b30f137c37">Integer::Gcd</a>(a,b) == <a class="code" href="class_integer.html#a8c070592581bf6c2f928c72bfa1c1638">Integer::One</a>();}</div><div class="line"><a name="l00151"></a><span class="lineno"> 151</span> <span class="comment"></span></div><div class="line"><a name="l00152"></a><span class="lineno"> 152</span> <span class="comment">/// \brief Calculate the least common multiple</span></div><div class="line"><a name="l00153"></a><span class="lineno"> 153</span> <span class="comment">/// \param a the first term</span></div><div class="line"><a name="l00154"></a><span class="lineno"> 154</span> <span class="comment">/// \param b the second term</span></div><div class="line"><a name="l00155"></a><span class="lineno"> 155</span> <span class="comment">/// \returns the least common multiple of <tt>a</tt> and <tt>b</tt>.</span></div><div class="line"><a name="l00156"></a><span class="lineno"><a class="line" href="nbtheory_8h.html#adaa35c5ed3df59615477e3ae91cc8015"> 156</a></span> <span class="comment"></span><span class="keyword">inline</span> <a class="code" href="class_integer.html">Integer</a> <a class="code" href="nbtheory_8h.html#adaa35c5ed3df59615477e3ae91cc8015">LCM</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)</div><div class="line"><a name="l00157"></a><span class="lineno"> 157</span>  {<span class="keywordflow">return</span> a/<a class="code" href="class_integer.html#a2d4d29937f8ef666717530b30f137c37">Integer::Gcd</a>(a,b)*b;}</div><div class="line"><a name="l00158"></a><span class="lineno"> 158</span> <span class="comment"></span></div><div class="line"><a name="l00159"></a><span class="lineno"> 159</span> <span class="comment">/// \brief Calculate multiplicative inverse</span></div><div class="line"><a name="l00160"></a><span class="lineno"> 160</span> <span class="comment">/// \param a the number to test</span></div><div class="line"><a name="l00161"></a><span class="lineno"> 161</span> <span class="comment">/// \param b the modulus</span></div><div class="line"><a name="l00162"></a><span class="lineno"> 162</span> <span class="comment">/// \returns an Integer <tt>(a ^ -1) % n</tt> or 0 if none exists.</span></div><div class="line"><a name="l00163"></a><span class="lineno"> 163</span> <span class="comment">/// \details EuclideanMultiplicativeInverse returns the multiplicative inverse of the Integer</span></div><div class="line"><a name="l00164"></a><span class="lineno"> 164</span> <span class="comment">/// <tt>*a</tt> modulo the Integer <tt>b</tt>. If no Integer exists then Integer 0 is returned.</span></div><div class="line"><a name="l00165"></a><span class="lineno"><a class="line" href="nbtheory_8h.html#aa88bcc8ea0e0608098a17bec60abe61e"> 165</a></span> <span class="comment"></span><span class="keyword">inline</span> <a class="code" href="class_integer.html">Integer</a> <a class="code" href="nbtheory_8h.html#aa88bcc8ea0e0608098a17bec60abe61e">EuclideanMultiplicativeInverse</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)</div><div class="line"><a name="l00166"></a><span class="lineno"> 166</span>  {<span class="keywordflow">return</span> a.InverseMod(b);}</div><div class="line"><a name="l00167"></a><span class="lineno"> 167</span> </div><div class="line"><a name="l00168"></a><span class="lineno"> 168</span> <span class="comment"></span></div><div class="line"><a name="l00169"></a><span class="lineno"> 169</span> <span class="comment">/// \brief Chinese Remainder Theorem</span></div><div class="line"><a name="l00170"></a><span class="lineno"> 170</span> <span class="comment">/// \param xp the first number, mod p</span></div><div class="line"><a name="l00171"></a><span class="lineno"> 171</span> <span class="comment">/// \param p the first prime modulus</span></div><div class="line"><a name="l00172"></a><span class="lineno"> 172</span> <span class="comment">/// \param xq the second number, mod q</span></div><div class="line"><a name="l00173"></a><span class="lineno"> 173</span> <span class="comment">/// \param q the second prime modulus</span></div><div class="line"><a name="l00174"></a><span class="lineno"> 174</span> <span class="comment">/// \param u inverse of p mod q</span></div><div class="line"><a name="l00175"></a><span class="lineno"> 175</span> <span class="comment">/// \returns the CRT value of the parameters</span></div><div class="line"><a name="l00176"></a><span class="lineno"> 176</span> <span class="comment">/// \details CRT uses the Chinese Remainder Theorem to calculate <tt>x</tt> given</span></div><div class="line"><a name="l00177"></a><span class="lineno"> 177</span> <span class="comment">/// <tt>x mod p</tt> and <tt>x mod q</tt>, and <tt>u</tt> the inverse of <tt>p mod q</tt>.</span></div><div class="line"><a name="l00178"></a><span class="lineno"> 178</span> <span class="comment"></span>CRYPTOPP_DLL <a class="code" href="class_integer.html">Integer</a> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#ab3fae49135264b5b5afecd0331915040">CRT</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &xp, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &xq, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &q, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &u);</div><div class="line"><a name="l00179"></a><span class="lineno"> 179</span> <span class="comment"></span></div><div class="line"><a name="l00180"></a><span class="lineno"> 180</span> <span class="comment">/// \brief Calculate the Jacobi symbol</span></div><div class="line"><a name="l00181"></a><span class="lineno"> 181</span> <span class="comment">/// \param a the first term</span></div><div class="line"><a name="l00182"></a><span class="lineno"> 182</span> <span class="comment">/// \param b the second term</span></div><div class="line"><a name="l00183"></a><span class="lineno"> 183</span> <span class="comment">/// \returns the the Jacobi symbol.</span></div><div class="line"><a name="l00184"></a><span class="lineno"> 184</span> <span class="comment">/// \details Jacobi symbols are calculated using the following rules:</span></div><div class="line"><a name="l00185"></a><span class="lineno"> 185</span> <span class="comment">/// -# if <tt>b</tt> is prime, then <tt>Jacobi(a, b)</tt>, then return 0</span></div><div class="line"><a name="l00186"></a><span class="lineno"> 186</span> <span class="comment">/// -# if <tt>a%b</tt>==0 AND <tt>a</tt> is quadratic residue <tt>mod b</tt>, then return 1</span></div><div class="line"><a name="l00187"></a><span class="lineno"> 187</span> <span class="comment">/// -# return -1 otherwise</span></div><div class="line"><a name="l00188"></a><span class="lineno"> 188</span> <span class="comment">/// \details Refer to a number theory book for what Jacobi symbol means when <tt>b</tt> is not prime.</span></div><div class="line"><a name="l00189"></a><span class="lineno"> 189</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">int</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#abffe3c03543252f53fcf59fdb2df765c">Jacobi</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b);</div><div class="line"><a name="l00190"></a><span class="lineno"> 190</span> <span class="comment"></span></div><div class="line"><a name="l00191"></a><span class="lineno"> 191</span> <span class="comment">/// \brief Calculate the Lucas value</span></div><div class="line"><a name="l00192"></a><span class="lineno"> 192</span> <span class="comment">/// \returns the Lucas value</span></div><div class="line"><a name="l00193"></a><span class="lineno"> 193</span> <span class="comment">/// \details Lucas() calculates the Lucas function <tt>V_e(p, 1) mod n</tt>.</span></div><div class="line"><a name="l00194"></a><span class="lineno"> 194</span> <span class="comment"></span>CRYPTOPP_DLL <a class="code" href="class_integer.html">Integer</a> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a6f8b2f16d9cb4cdc4bfa5a785928044a">Lucas</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &e, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &n);</div><div class="line"><a name="l00195"></a><span class="lineno"> 195</span> <span class="comment"></span></div><div class="line"><a name="l00196"></a><span class="lineno"> 196</span> <span class="comment">/// \brief Calculate the inverse Lucas value</span></div><div class="line"><a name="l00197"></a><span class="lineno"> 197</span> <span class="comment">/// \returns the inverse Lucas value</span></div><div class="line"><a name="l00198"></a><span class="lineno"> 198</span> <span class="comment">/// \details InverseLucas() calculates <tt>x</tt> such that <tt>m==Lucas(e, x, p*q)</tt>,</span></div><div class="line"><a name="l00199"></a><span class="lineno"> 199</span> <span class="comment">/// <tt>p q</tt> primes, <tt>u</tt> is inverse of <tt>p mod q</tt>.</span></div><div class="line"><a name="l00200"></a><span class="lineno"> 200</span> <span class="comment"></span>CRYPTOPP_DLL <a class="code" href="class_integer.html">Integer</a> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a9b5b91490b1ae3357ab4f0d863f103c1">InverseLucas</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &e, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &m, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &q, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &u);</div><div class="line"><a name="l00201"></a><span class="lineno"> 201</span> <span class="comment"></span></div><div class="line"><a name="l00202"></a><span class="lineno"> 202</span> <span class="comment">/// \brief Modular multiplication</span></div><div class="line"><a name="l00203"></a><span class="lineno"> 203</span> <span class="comment">/// \param x the first term</span></div><div class="line"><a name="l00204"></a><span class="lineno"> 204</span> <span class="comment">/// \param y the second term</span></div><div class="line"><a name="l00205"></a><span class="lineno"> 205</span> <span class="comment">/// \param m the modulus</span></div><div class="line"><a name="l00206"></a><span class="lineno"> 206</span> <span class="comment">/// \returns an Integer <tt>(x * y) % m</tt>.</span></div><div class="line"><a name="l00207"></a><span class="lineno"><a class="line" href="nbtheory_8h.html#a1b800e2880542031bc81cbb7cd0bec3e"> 207</a></span> <span class="comment"></span><span class="keyword">inline</span> <a class="code" href="class_integer.html">Integer</a> <a class="code" href="nbtheory_8h.html#a1b800e2880542031bc81cbb7cd0bec3e">ModularMultiplication</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &x, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &y, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &m)</div><div class="line"><a name="l00208"></a><span class="lineno"> 208</span>  {<span class="keywordflow">return</span> a_times_b_mod_c(x, y, m);}</div><div class="line"><a name="l00209"></a><span class="lineno"> 209</span> <span class="comment"></span></div><div class="line"><a name="l00210"></a><span class="lineno"> 210</span> <span class="comment">/// \brief Modular exponentiation</span></div><div class="line"><a name="l00211"></a><span class="lineno"> 211</span> <span class="comment">/// \param x the base</span></div><div class="line"><a name="l00212"></a><span class="lineno"> 212</span> <span class="comment">/// \param e the exponent</span></div><div class="line"><a name="l00213"></a><span class="lineno"> 213</span> <span class="comment">/// \param m the modulus</span></div><div class="line"><a name="l00214"></a><span class="lineno"> 214</span> <span class="comment">/// \returns an Integer <tt>(a ^ b) % m</tt>.</span></div><div class="line"><a name="l00215"></a><span class="lineno"><a class="line" href="nbtheory_8h.html#a5365cc677fbc93221d9bdfaec442ca3d"> 215</a></span> <span class="comment"></span><span class="keyword">inline</span> <a class="code" href="class_integer.html">Integer</a> <a class="code" href="nbtheory_8h.html#a5365cc677fbc93221d9bdfaec442ca3d">ModularExponentiation</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &x, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &e, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &m)</div><div class="line"><a name="l00216"></a><span class="lineno"> 216</span>  {<span class="keywordflow">return</span> a_exp_b_mod_c(x, e, m);}</div><div class="line"><a name="l00217"></a><span class="lineno"> 217</span> <span class="comment"></span></div><div class="line"><a name="l00218"></a><span class="lineno"> 218</span> <span class="comment">/// \brief Extract a modular square root</span></div><div class="line"><a name="l00219"></a><span class="lineno"> 219</span> <span class="comment">/// \param a the number to extract square root</span></div><div class="line"><a name="l00220"></a><span class="lineno"> 220</span> <span class="comment">/// \param p the prime modulus</span></div><div class="line"><a name="l00221"></a><span class="lineno"> 221</span> <span class="comment">/// \returns the modular square root if it exists</span></div><div class="line"><a name="l00222"></a><span class="lineno"> 222</span> <span class="comment">/// \details ModularSquareRoot returns <tt>x</tt> such that <tt>x*x%p == a</tt>, <tt>p</tt> prime</span></div><div class="line"><a name="l00223"></a><span class="lineno"> 223</span> <span class="comment"></span>CRYPTOPP_DLL <a class="code" href="class_integer.html">Integer</a> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#abb83c7bbd49b1761028d08a9a1016e68">ModularSquareRoot</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p);</div><div class="line"><a name="l00224"></a><span class="lineno"> 224</span> <span class="comment"></span></div><div class="line"><a name="l00225"></a><span class="lineno"> 225</span> <span class="comment">/// \brief Extract a modular root</span></div><div class="line"><a name="l00226"></a><span class="lineno"> 226</span> <span class="comment">/// \returns a modular root if it exists</span></div><div class="line"><a name="l00227"></a><span class="lineno"> 227</span> <span class="comment">/// \details ModularRoot returns <tt>x</tt> such that <tt>a==ModularExponentiation(x, e, p*q)</tt>,</span></div><div class="line"><a name="l00228"></a><span class="lineno"> 228</span> <span class="comment">/// <tt>p</tt> <tt>q</tt> primes, and <tt>e</tt> relatively prime to <tt>(p-1)*(q-1)</tt>,</span></div><div class="line"><a name="l00229"></a><span class="lineno"> 229</span> <span class="comment">/// <tt>dp=d%(p-1)</tt>, <tt>dq=d%(q-1)</tt>, (d is inverse of <tt>e mod (p-1)*(q-1)</tt>)</span></div><div class="line"><a name="l00230"></a><span class="lineno"> 230</span> <span class="comment">/// and <tt>u=inverse of p mod q</tt>.</span></div><div class="line"><a name="l00231"></a><span class="lineno"> 231</span> <span class="comment"></span>CRYPTOPP_DLL <a class="code" href="class_integer.html">Integer</a> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#aad7ca1c53c38a93997327226eddc0240">ModularRoot</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &dp, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &dq, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &q, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &u);</div><div class="line"><a name="l00232"></a><span class="lineno"> 232</span> <span class="comment"></span></div><div class="line"><a name="l00233"></a><span class="lineno"> 233</span> <span class="comment">/// \brief Solve a Modular Quadratic Equation</span></div><div class="line"><a name="l00234"></a><span class="lineno"> 234</span> <span class="comment">/// \param r1 the first residue</span></div><div class="line"><a name="l00235"></a><span class="lineno"> 235</span> <span class="comment">/// \param r2 the second residue</span></div><div class="line"><a name="l00236"></a><span class="lineno"> 236</span> <span class="comment">/// \param a the first coefficient</span></div><div class="line"><a name="l00237"></a><span class="lineno"> 237</span> <span class="comment">/// \param b the second coefficient</span></div><div class="line"><a name="l00238"></a><span class="lineno"> 238</span> <span class="comment">/// \param c the third constant</span></div><div class="line"><a name="l00239"></a><span class="lineno"> 239</span> <span class="comment">/// \param p the prime modulus</span></div><div class="line"><a name="l00240"></a><span class="lineno"> 240</span> <span class="comment">/// \returns true if solutions exist</span></div><div class="line"><a name="l00241"></a><span class="lineno"> 241</span> <span class="comment">/// \details SolveModularQuadraticEquation() finds <tt>r1</tt> and <tt>r2</tt> such that <tt>ax^2 +</span></div><div class="line"><a name="l00242"></a><span class="lineno"> 242</span> <span class="comment">/// bx + c == 0 (mod p)</tt> for x in <tt>{r1, r2}</tt>, <tt>p</tt> prime.</span></div><div class="line"><a name="l00243"></a><span class="lineno"> 243</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">bool</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#aa308ad452a47cf22de4ac3204ab09e7d">SolveModularQuadraticEquation</a>(<a class="code" href="class_integer.html">Integer</a> &r1, <a class="code" href="class_integer.html">Integer</a> &r2, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &c, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p);</div><div class="line"><a name="l00244"></a><span class="lineno"> 244</span> <span class="comment"></span></div><div class="line"><a name="l00245"></a><span class="lineno"> 245</span> <span class="comment">/// \brief Estimate work factor</span></div><div class="line"><a name="l00246"></a><span class="lineno"> 246</span> <span class="comment">/// \param bitlength the size of the number, in bits</span></div><div class="line"><a name="l00247"></a><span class="lineno"> 247</span> <span class="comment">/// \returns the estimated work factor, in operations</span></div><div class="line"><a name="l00248"></a><span class="lineno"> 248</span> <span class="comment">/// \details DiscreteLogWorkFactor returns log base 2 of estimated number of operations to</span></div><div class="line"><a name="l00249"></a><span class="lineno"> 249</span> <span class="comment">/// calculate discrete log or factor a number.</span></div><div class="line"><a name="l00250"></a><span class="lineno"> 250</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a0b8a9730d2aaeabc3c8582574ab9cf6d">DiscreteLogWorkFactor</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bitlength);</div><div class="line"><a name="l00251"></a><span class="lineno"> 251</span> <span class="comment"></span></div><div class="line"><a name="l00252"></a><span class="lineno"> 252</span> <span class="comment">/// \brief Estimate work factor</span></div><div class="line"><a name="l00253"></a><span class="lineno"> 253</span> <span class="comment">/// \param bitlength the size of the number, in bits</span></div><div class="line"><a name="l00254"></a><span class="lineno"> 254</span> <span class="comment">/// \returns the estimated work factor, in operations</span></div><div class="line"><a name="l00255"></a><span class="lineno"> 255</span> <span class="comment">/// \details FactoringWorkFactor returns log base 2 of estimated number of operations to</span></div><div class="line"><a name="l00256"></a><span class="lineno"> 256</span> <span class="comment">/// calculate discrete log or factor a number.</span></div><div class="line"><a name="l00257"></a><span class="lineno"> 257</span> <span class="comment"></span>CRYPTOPP_DLL <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> CRYPTOPP_API <a class="code" href="nbtheory_8h.html#a8e5a50115e2e7f5546884e4b9d9d1f30">FactoringWorkFactor</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bitlength);</div><div class="line"><a name="l00258"></a><span class="lineno"> 258</span> </div><div class="line"><a name="l00259"></a><span class="lineno"> 259</span> <span class="comment">// ********************************************************</span></div><div class="line"><a name="l00260"></a><span class="lineno"> 260</span> <span class="comment"></span></div><div class="line"><a name="l00261"></a><span class="lineno"> 261</span> <span class="comment">/// \brief Generator of prime numbers of special forms</span></div><div class="line"><a name="l00262"></a><span class="lineno"><a class="line" href="class_prime_and_generator.html"> 262</a></span> <span class="comment"></span><span class="keyword">class </span>CRYPTOPP_DLL <a class="code" href="class_prime_and_generator.html">PrimeAndGenerator</a></div><div class="line"><a name="l00263"></a><span class="lineno"> 263</span> {</div><div class="line"><a name="l00264"></a><span class="lineno"> 264</span> <span class="keyword">public</span>:<span class="comment"></span></div><div class="line"><a name="l00265"></a><span class="lineno"> 265</span> <span class="comment"> /// \brief Construct a PrimeAndGenerator</span></div><div class="line"><a name="l00266"></a><span class="lineno"><a class="line" href="class_prime_and_generator.html#a45b2743c9edd5e67bb4f5241d3fdd890"> 266</a></span> <span class="comment"></span> <a class="code" href="class_prime_and_generator.html#a45b2743c9edd5e67bb4f5241d3fdd890">PrimeAndGenerator</a>() {}</div><div class="line"><a name="l00267"></a><span class="lineno"> 267</span> <span class="comment"></span></div><div class="line"><a name="l00268"></a><span class="lineno"> 268</span> <span class="comment"> /// \brief Construct a PrimeAndGenerator</span></div><div class="line"><a name="l00269"></a><span class="lineno"> 269</span> <span class="comment"> /// \param delta +1 or -1</span></div><div class="line"><a name="l00270"></a><span class="lineno"> 270</span> <span class="comment"> /// \param rng a RandomNumberGenerator derived class</span></div><div class="line"><a name="l00271"></a><span class="lineno"> 271</span> <span class="comment"> /// \param pbits the number of bits in the prime p</span></div><div class="line"><a name="l00272"></a><span class="lineno"> 272</span> <span class="comment"> /// \details PrimeAndGenerator() generates a random prime p of the form <tt>2*q+delta</tt>, where delta is 1 or -1 and q is</span></div><div class="line"><a name="l00273"></a><span class="lineno"> 273</span> <span class="comment"> /// also prime. Internally the constructor calls <tt>Generate(delta, rng, pbits, pbits-1)</tt>.</span></div><div class="line"><a name="l00274"></a><span class="lineno"> 274</span> <span class="comment"> /// \pre <tt>pbits > 5</tt></span></div><div class="line"><a name="l00275"></a><span class="lineno"> 275</span> <span class="comment"> /// \warning This PrimeAndGenerator() is slow because primes of this form are harder to find.</span></div><div class="line"><a name="l00276"></a><span class="lineno"><a class="line" href="class_prime_and_generator.html#a35fcc8d77d72793bb4afc386b454dfc1"> 276</a></span> <span class="comment"></span> <a class="code" href="class_prime_and_generator.html#a35fcc8d77d72793bb4afc386b454dfc1">PrimeAndGenerator</a>(<span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta, <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits)</div><div class="line"><a name="l00277"></a><span class="lineno"> 277</span>  {Generate(delta, rng, pbits, pbits-1);}</div><div class="line"><a name="l00278"></a><span class="lineno"> 278</span> <span class="comment"></span></div><div class="line"><a name="l00279"></a><span class="lineno"> 279</span> <span class="comment"> /// \brief Construct a PrimeAndGenerator</span></div><div class="line"><a name="l00280"></a><span class="lineno"> 280</span> <span class="comment"> /// \param delta +1 or -1</span></div><div class="line"><a name="l00281"></a><span class="lineno"> 281</span> <span class="comment"> /// \param rng a RandomNumberGenerator derived class</span></div><div class="line"><a name="l00282"></a><span class="lineno"> 282</span> <span class="comment"> /// \param pbits the number of bits in the prime p</span></div><div class="line"><a name="l00283"></a><span class="lineno"> 283</span> <span class="comment"> /// \param qbits the number of bits in the prime q</span></div><div class="line"><a name="l00284"></a><span class="lineno"> 284</span> <span class="comment"> /// \details PrimeAndGenerator() generates a random prime p of the form <tt>2*r*q+delta</tt>, where q is also prime.</span></div><div class="line"><a name="l00285"></a><span class="lineno"> 285</span> <span class="comment"> /// Internally the constructor calls <tt>Generate(delta, rng, pbits, qbits)</tt>.</span></div><div class="line"><a name="l00286"></a><span class="lineno"> 286</span> <span class="comment"> /// \pre <tt>qbits > 4 && pbits > qbits</tt></span></div><div class="line"><a name="l00287"></a><span class="lineno"><a class="line" href="class_prime_and_generator.html#af014ff08d285a45c5deafc4f6a9c2abe"> 287</a></span> <span class="comment"></span> <a class="code" href="class_prime_and_generator.html#af014ff08d285a45c5deafc4f6a9c2abe">PrimeAndGenerator</a>(<span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta, <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits, <span class="keywordtype">unsigned</span> qbits)</div><div class="line"><a name="l00288"></a><span class="lineno"> 288</span>  {Generate(delta, rng, pbits, qbits);}</div><div class="line"><a name="l00289"></a><span class="lineno"> 289</span> <span class="comment"></span></div><div class="line"><a name="l00290"></a><span class="lineno"> 290</span> <span class="comment"> /// \brief Generate a Prime and Generator</span></div><div class="line"><a name="l00291"></a><span class="lineno"> 291</span> <span class="comment"> /// \param delta +1 or -1</span></div><div class="line"><a name="l00292"></a><span class="lineno"> 292</span> <span class="comment"> /// \param rng a RandomNumberGenerator derived class</span></div><div class="line"><a name="l00293"></a><span class="lineno"> 293</span> <span class="comment"> /// \param pbits the number of bits in the prime p</span></div><div class="line"><a name="l00294"></a><span class="lineno"> 294</span> <span class="comment"> /// \param qbits the number of bits in the prime q</span></div><div class="line"><a name="l00295"></a><span class="lineno"> 295</span> <span class="comment"> /// \details Generate() generates a random prime p of the form <tt>2*r*q+delta</tt>, where q is also prime.</span></div><div class="line"><a name="l00296"></a><span class="lineno"> 296</span> <span class="comment"></span> <span class="keywordtype">void</span> Generate(<span class="keywordtype">signed</span> <span class="keywordtype">int</span> delta, <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits, <span class="keywordtype">unsigned</span> qbits);</div><div class="line"><a name="l00297"></a><span class="lineno"> 297</span> <span class="comment"></span></div><div class="line"><a name="l00298"></a><span class="lineno"> 298</span> <span class="comment"> /// \brief Retrieve first prime</span></div><div class="line"><a name="l00299"></a><span class="lineno"> 299</span> <span class="comment"> /// \returns Prime() returns the prime p.</span></div><div class="line"><a name="l00300"></a><span class="lineno"><a class="line" href="class_prime_and_generator.html#acb878f8b71f1260b6458c50ad87d592a"> 300</a></span> <span class="comment"></span> <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& <a class="code" href="class_prime_and_generator.html#acb878f8b71f1260b6458c50ad87d592a">Prime</a>()<span class="keyword"> const </span>{<span class="keywordflow">return</span> p;}</div><div class="line"><a name="l00301"></a><span class="lineno"> 301</span> <span class="comment"></span></div><div class="line"><a name="l00302"></a><span class="lineno"> 302</span> <span class="comment"> /// \brief Retrieve second prime</span></div><div class="line"><a name="l00303"></a><span class="lineno"> 303</span> <span class="comment"> /// \returns SubPrime() returns the prime q.</span></div><div class="line"><a name="l00304"></a><span class="lineno"><a class="line" href="class_prime_and_generator.html#ae2d1a2b6be1c325680c7cc6d1da399a3"> 304</a></span> <span class="comment"></span> <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& <a class="code" href="class_prime_and_generator.html#ae2d1a2b6be1c325680c7cc6d1da399a3">SubPrime</a>()<span class="keyword"> const </span>{<span class="keywordflow">return</span> q;}</div><div class="line"><a name="l00305"></a><span class="lineno"> 305</span> <span class="comment"></span></div><div class="line"><a name="l00306"></a><span class="lineno"> 306</span> <span class="comment"> /// \brief Retrieve the generator</span></div><div class="line"><a name="l00307"></a><span class="lineno"> 307</span> <span class="comment"> /// \returns Generator() returns the the generator g.</span></div><div class="line"><a name="l00308"></a><span class="lineno"><a class="line" href="class_prime_and_generator.html#a00e94acffa91d09a711616c60ce2327e"> 308</a></span> <span class="comment"></span> <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& <a class="code" href="class_prime_and_generator.html#a00e94acffa91d09a711616c60ce2327e">Generator</a>()<span class="keyword"> const </span>{<span class="keywordflow">return</span> g;}</div><div class="line"><a name="l00309"></a><span class="lineno"> 309</span> </div><div class="line"><a name="l00310"></a><span class="lineno"> 310</span> <span class="keyword">private</span>:</div><div class="line"><a name="l00311"></a><span class="lineno"> 311</span>  <a class="code" href="class_integer.html">Integer</a> p, q, g;</div><div class="line"><a name="l00312"></a><span class="lineno"> 312</span> };</div><div class="line"><a name="l00313"></a><span class="lineno"> 313</span> </div><div class="line"><a name="l00314"></a><span class="lineno"> 314</span> NAMESPACE_END</div><div class="line"><a name="l00315"></a><span class="lineno"> 315</span> </div><div class="line"><a name="l00316"></a><span class="lineno"> 316</span> <span class="preprocessor">#endif</span></div><div class="ttc" id="nbtheory_8h_html_ab3fae49135264b5b5afecd0331915040"><div class="ttname"><a href="nbtheory_8h.html#ab3fae49135264b5b5afecd0331915040">CRT</a></div><div class="ttdeci">Integer CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)</div><div class="ttdoc">Chinese Remainder Theorem. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00553">nbtheory.cpp:553</a></div></div>
<div class="ttc" id="nbtheory_8h_html_aa41f53fa846ea7546d7269b5d5c6a29f"><div class="ttname"><a href="nbtheory_8h.html#aa41f53fa846ea7546d7269b5d5c6a29f">GetPrimeTable</a></div><div class="ttdeci">const word16 * GetPrimeTable(unsigned int &size)</div><div class="ttdoc">The Small Prime table. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00053">nbtheory.cpp:53</a></div></div>
<div class="ttc" id="algparam_8h_html"><div class="ttname"><a href="algparam_8h.html">algparam.h</a></div><div class="ttdoc">Classes for working with NameValuePairs. </div></div>
<div class="ttc" id="nbtheory_8h_html_aada479f79cb8988f4df16df1e321fc7b"><div class="ttname"><a href="nbtheory_8h.html#aada479f79cb8988f4df16df1e321fc7b">IsLucasProbablePrime</a></div><div class="ttdeci">bool IsLucasProbablePrime(const Integer &n)</div><div class="ttdoc">Determine if a number is probably prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00155">nbtheory.cpp:155</a></div></div>
<div class="ttc" id="nbtheory_8h_html_aaef9ef9567713cd9935e468309ebcc9d"><div class="ttname"><a href="nbtheory_8h.html#aaef9ef9567713cd9935e468309ebcc9d">FirstPrime</a></div><div class="ttdeci">bool FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)</div><div class="ttdoc">Finds a random prime of special form. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00379">nbtheory.cpp:379</a></div></div>
<div class="ttc" id="class_integer_html_a2d4d29937f8ef666717530b30f137c37"><div class="ttname"><a href="class_integer.html#a2d4d29937f8ef666717530b30f137c37">Integer::Gcd</a></div><div class="ttdeci">static Integer Gcd(const Integer &a, const Integer &n)</div><div class="ttdoc">Calculate greatest common divisor. </div><div class="ttdef"><b>Definition:</b> <a href="integer_8cpp_source.html#l04381">integer.cpp:4381</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a7d7be62fa8075e10432f49cc08273707"><div class="ttname"><a href="nbtheory_8h.html#a7d7be62fa8075e10432f49cc08273707">SmallDivisorsTest</a></div><div class="ttdeci">bool SmallDivisorsTest(const Integer &p)</div><div class="ttdoc">Tests whether a number is divisible by a small prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00089">nbtheory.cpp:89</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a9167952dad6998d1b854dee8355b53a0"><div class="ttname"><a href="nbtheory_8h.html#a9167952dad6998d1b854dee8355b53a0">IsStrongLucasProbablePrime</a></div><div class="ttdeci">bool IsStrongLucasProbablePrime(const Integer &n)</div><div class="ttdoc">Determine if a number is probably prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00182">nbtheory.cpp:182</a></div></div>
<div class="ttc" id="cryptlib_8h_html"><div class="ttname"><a href="cryptlib_8h.html">cryptlib.h</a></div><div class="ttdoc">Abstract base classes that provide a uniform interface to this library. </div></div>
<div class="ttc" id="nbtheory_8h_html_a4f5215dbaaf83eacf300ef54f0e941fc"><div class="ttname"><a href="nbtheory_8h.html#a4f5215dbaaf83eacf300ef54f0e941fc">MaurerProvablePrime</a></div><div class="ttdeci">Integer MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits)</div><div class="ttdoc">Generates a provable prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00510">nbtheory.cpp:510</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a7bfb6022241ff5fb96250e366c68d49e"><div class="ttname"><a href="nbtheory_8h.html#a7bfb6022241ff5fb96250e366c68d49e">IsSmallPrime</a></div><div class="ttdeci">bool IsSmallPrime(const Integer &p)</div><div class="ttdoc">Tests whether a number is a small prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00060">nbtheory.cpp:60</a></div></div>
<div class="ttc" id="class_random_number_generator_html"><div class="ttname"><a href="class_random_number_generator.html">RandomNumberGenerator</a></div><div class="ttdoc">Interface for random number generators. </div><div class="ttdef"><b>Definition:</b> <a href="cryptlib_8h_source.html#l01330">cryptlib.h:1330</a></div></div>
<div class="ttc" id="nbtheory_8h_html_abcaf62227292dc648e6f2f11f2a6e158"><div class="ttname"><a href="nbtheory_8h.html#abcaf62227292dc648e6f2f11f2a6e158">IsFermatProbablePrime</a></div><div class="ttdeci">bool IsFermatProbablePrime(const Integer &n, const Integer &b)</div><div class="ttdoc">Determine if a number is probably prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00096">nbtheory.cpp:96</a></div></div>
<div class="ttc" id="nbtheory_8h_html_abffe3c03543252f53fcf59fdb2df765c"><div class="ttname"><a href="nbtheory_8h.html#abffe3c03543252f53fcf59fdb2df765c">Jacobi</a></div><div class="ttdeci">int Jacobi(const Integer &a, const Integer &b)</div><div class="ttdoc">Calculate the Jacobi symbol. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00785">nbtheory.cpp:785</a></div></div>
<div class="ttc" id="class_prime_and_generator_html_a35fcc8d77d72793bb4afc386b454dfc1"><div class="ttname"><a href="class_prime_and_generator.html#a35fcc8d77d72793bb4afc386b454dfc1">PrimeAndGenerator::PrimeAndGenerator</a></div><div class="ttdeci">PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits)</div><div class="ttdoc">Construct a PrimeAndGenerator. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00276">nbtheory.h:276</a></div></div>
<div class="ttc" id="class_prime_and_generator_html"><div class="ttname"><a href="class_prime_and_generator.html">PrimeAndGenerator</a></div><div class="ttdoc">Generator of prime numbers of special forms. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00262">nbtheory.h:262</a></div></div>
<div class="ttc" id="nbtheory_8h_html_abb83c7bbd49b1761028d08a9a1016e68"><div class="ttname"><a href="nbtheory_8h.html#abb83c7bbd49b1761028d08a9a1016e68">ModularSquareRoot</a></div><div class="ttdeci">Integer ModularSquareRoot(const Integer &a, const Integer &p)</div><div class="ttdoc">Extract a modular square root. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00572">nbtheory.cpp:572</a></div></div>
<div class="ttc" id="class_integer_html_a8c070592581bf6c2f928c72bfa1c1638"><div class="ttname"><a href="class_integer.html#a8c070592581bf6c2f928c72bfa1c1638">Integer::One</a></div><div class="ttdeci">static const Integer & One()</div><div class="ttdoc">Integer representing 1. </div><div class="ttdef"><b>Definition:</b> <a href="integer_8cpp_source.html#l04824">integer.cpp:4824</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a9b5b91490b1ae3357ab4f0d863f103c1"><div class="ttname"><a href="nbtheory_8h.html#a9b5b91490b1ae3357ab4f0d863f103c1">InverseLucas</a></div><div class="ttdeci">Integer InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)</div><div class="ttdoc">Calculate the inverse Lucas value. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00998">nbtheory.cpp:998</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a97c6199f98f7c5174373422d1e1c39af"><div class="ttname"><a href="nbtheory_8h.html#a97c6199f98f7c5174373422d1e1c39af">IsStrongProbablePrime</a></div><div class="ttdeci">bool IsStrongProbablePrime(const Integer &n, const Integer &b)</div><div class="ttdoc">Determine if a number is probably prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00105">nbtheory.cpp:105</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a40fab13239e32e04892023c81bb42597"><div class="ttname"><a href="nbtheory_8h.html#a40fab13239e32e04892023c81bb42597">MihailescuProvablePrime</a></div><div class="ttdeci">Integer MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits)</div><div class="ttdoc">Generates a provable prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00470">nbtheory.cpp:470</a></div></div>
<div class="ttc" id="nbtheory_8h_html_ac1d98aa1d0ed1df97bf0dc194da5169a"><div class="ttname"><a href="nbtheory_8h.html#ac1d98aa1d0ed1df97bf0dc194da5169a">GCD</a></div><div class="ttdeci">Integer GCD(const Integer &a, const Integer &b)</div><div class="ttdoc">Calculate the greatest common divisor. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00142">nbtheory.h:142</a></div></div>
<div class="ttc" id="class_prime_and_generator_html_ae2d1a2b6be1c325680c7cc6d1da399a3"><div class="ttname"><a href="class_prime_and_generator.html#ae2d1a2b6be1c325680c7cc6d1da399a3">PrimeAndGenerator::SubPrime</a></div><div class="ttdeci">const Integer & SubPrime() const</div><div class="ttdoc">Retrieve second prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00304">nbtheory.h:304</a></div></div>
<div class="ttc" id="class_prime_and_generator_html_acb878f8b71f1260b6458c50ad87d592a"><div class="ttname"><a href="class_prime_and_generator.html#acb878f8b71f1260b6458c50ad87d592a">PrimeAndGenerator::Prime</a></div><div class="ttdeci">const Integer & Prime() const</div><div class="ttdoc">Retrieve first prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00300">nbtheory.h:300</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a6f8b2f16d9cb4cdc4bfa5a785928044a"><div class="ttname"><a href="nbtheory_8h.html#a6f8b2f16d9cb4cdc4bfa5a785928044a">Lucas</a></div><div class="ttdeci">Integer Lucas(const Integer &e, const Integer &p, const Integer &n)</div><div class="ttdoc">Calculate the Lucas value. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00812">nbtheory.cpp:812</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a633d17045e229eccc3614426df054463"><div class="ttname"><a href="nbtheory_8h.html#a633d17045e229eccc3614426df054463">VerifyPrime</a></div><div class="ttdeci">bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)</div><div class="ttdoc">Verifies a number is probably prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00247">nbtheory.cpp:247</a></div></div>
<div class="ttc" id="class_prime_selector_html"><div class="ttname"><a href="class_prime_selector.html">PrimeSelector</a></div><div class="ttdoc">Application callback to signal suitability of a cabdidate prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00113">nbtheory.h:113</a></div></div>
<div class="ttc" id="class_integer_html"><div class="ttname"><a href="class_integer.html">Integer</a></div><div class="ttdoc">Multiple precision integer with arithmetic operations. </div><div class="ttdef"><b>Definition:</b> <a href="integer_8h_source.html#l00049">integer.h:49</a></div></div>
<div class="ttc" id="nbtheory_8h_html_adaa35c5ed3df59615477e3ae91cc8015"><div class="ttname"><a href="nbtheory_8h.html#adaa35c5ed3df59615477e3ae91cc8015">LCM</a></div><div class="ttdeci">Integer LCM(const Integer &a, const Integer &b)</div><div class="ttdoc">Calculate the least common multiple. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00156">nbtheory.h:156</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a1b800e2880542031bc81cbb7cd0bec3e"><div class="ttname"><a href="nbtheory_8h.html#a1b800e2880542031bc81cbb7cd0bec3e">ModularMultiplication</a></div><div class="ttdeci">Integer ModularMultiplication(const Integer &x, const Integer &y, const Integer &m)</div><div class="ttdoc">Modular multiplication. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00207">nbtheory.h:207</a></div></div>
<div class="ttc" id="nbtheory_8h_html_ae8442dd787d99d3604436a91799552bf"><div class="ttname"><a href="nbtheory_8h.html#ae8442dd787d99d3604436a91799552bf">IsPrime</a></div><div class="ttdeci">bool IsPrime(const Integer &p)</div><div class="ttdoc">Verifies a number is probably prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00237">nbtheory.cpp:237</a></div></div>
<div class="ttc" id="class_prime_and_generator_html_af014ff08d285a45c5deafc4f6a9c2abe"><div class="ttname"><a href="class_prime_and_generator.html#af014ff08d285a45c5deafc4f6a9c2abe">PrimeAndGenerator::PrimeAndGenerator</a></div><div class="ttdeci">PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)</div><div class="ttdoc">Construct a PrimeAndGenerator. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00287">nbtheory.h:287</a></div></div>
<div class="ttc" id="nbtheory_8h_html_aef5a456e724cba394ff8ad788eae777d"><div class="ttname"><a href="nbtheory_8h.html#aef5a456e724cba394ff8ad788eae777d">TrialDivision</a></div><div class="ttdeci">bool TrialDivision(const Integer &p, unsigned bound)</div><div class="ttdoc">Tests whether a number is divisible by a small prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00071">nbtheory.cpp:71</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a0b8a9730d2aaeabc3c8582574ab9cf6d"><div class="ttname"><a href="nbtheory_8h.html#a0b8a9730d2aaeabc3c8582574ab9cf6d">DiscreteLogWorkFactor</a></div><div class="ttdeci">unsigned int DiscreteLogWorkFactor(unsigned int bitlength)</div><div class="ttdoc">Estimate work factor. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l01027">nbtheory.cpp:1027</a></div></div>
<div class="ttc" id="nbtheory_8h_html_aad7ca1c53c38a93997327226eddc0240"><div class="ttname"><a href="nbtheory_8h.html#aad7ca1c53c38a93997327226eddc0240">ModularRoot</a></div><div class="ttdeci">Integer ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)</div><div class="ttdoc">Extract a modular root. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00646">nbtheory.cpp:646</a></div></div>
<div class="ttc" id="nbtheory_8h_html_aa88bcc8ea0e0608098a17bec60abe61e"><div class="ttname"><a href="nbtheory_8h.html#aa88bcc8ea0e0608098a17bec60abe61e">EuclideanMultiplicativeInverse</a></div><div class="ttdeci">Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)</div><div class="ttdoc">Calculate multiplicative inverse. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00165">nbtheory.h:165</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a1653aff24d226faac1ff141e665ef9e1"><div class="ttname"><a href="nbtheory_8h.html#a1653aff24d226faac1ff141e665ef9e1">RelativelyPrime</a></div><div class="ttdeci">bool RelativelyPrime(const Integer &a, const Integer &b)</div><div class="ttdoc">Determine relative primality. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00149">nbtheory.h:149</a></div></div>
<div class="ttc" id="class_algorithm_parameters_html"><div class="ttname"><a href="class_algorithm_parameters.html">AlgorithmParameters</a></div><div class="ttdoc">An object that implements NameValuePairs. </div><div class="ttdef"><b>Definition:</b> <a href="algparam_8h_source.html#l00419">algparam.h:419</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a637fa2abf1a48bc38f3c0d7c7edd679a"><div class="ttname"><a href="nbtheory_8h.html#a637fa2abf1a48bc38f3c0d7c7edd679a">RabinMillerTest</a></div><div class="ttdeci">bool RabinMillerTest(RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)</div><div class="ttdoc">Determine if a number is probably prime. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00138">nbtheory.cpp:138</a></div></div>
<div class="ttc" id="integer_8h_html"><div class="ttname"><a href="integer_8h.html">integer.h</a></div><div class="ttdoc">Multiple precision integer with arithmetic operations. </div></div>
<div class="ttc" id="namespace_crypto_p_p_html"><div class="ttname"><a href="namespace_crypto_p_p.html">CryptoPP</a></div><div class="ttdoc">Crypto++ library namespace. </div></div>
<div class="ttc" id="nbtheory_8h_html_aa308ad452a47cf22de4ac3204ab09e7d"><div class="ttname"><a href="nbtheory_8h.html#aa308ad452a47cf22de4ac3204ab09e7d">SolveModularQuadraticEquation</a></div><div class="ttdeci">bool SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)</div><div class="ttdoc">Solve a Modular Quadratic Equation. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l00621">nbtheory.cpp:621</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a5365cc677fbc93221d9bdfaec442ca3d"><div class="ttname"><a href="nbtheory_8h.html#a5365cc677fbc93221d9bdfaec442ca3d">ModularExponentiation</a></div><div class="ttdeci">Integer ModularExponentiation(const Integer &x, const Integer &e, const Integer &m)</div><div class="ttdoc">Modular exponentiation. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00215">nbtheory.h:215</a></div></div>
<div class="ttc" id="class_prime_and_generator_html_a45b2743c9edd5e67bb4f5241d3fdd890"><div class="ttname"><a href="class_prime_and_generator.html#a45b2743c9edd5e67bb4f5241d3fdd890">PrimeAndGenerator::PrimeAndGenerator</a></div><div class="ttdeci">PrimeAndGenerator()</div><div class="ttdoc">Construct a PrimeAndGenerator. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00266">nbtheory.h:266</a></div></div>
<div class="ttc" id="nbtheory_8h_html_a8e5a50115e2e7f5546884e4b9d9d1f30"><div class="ttname"><a href="nbtheory_8h.html#a8e5a50115e2e7f5546884e4b9d9d1f30">FactoringWorkFactor</a></div><div class="ttdeci">unsigned int FactoringWorkFactor(unsigned int bitlength)</div><div class="ttdoc">Estimate work factor. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8cpp_source.html#l01019">nbtheory.cpp:1019</a></div></div>
<div class="ttc" id="class_prime_and_generator_html_a00e94acffa91d09a711616c60ce2327e"><div class="ttname"><a href="class_prime_and_generator.html#a00e94acffa91d09a711616c60ce2327e">PrimeAndGenerator::Generator</a></div><div class="ttdeci">const Integer & Generator() const</div><div class="ttdoc">Retrieve the generator. </div><div class="ttdef"><b>Definition:</b> <a href="nbtheory_8h_source.html#l00308">nbtheory.h:308</a></div></div>
</div><!-- fragment --></div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Sun Sep 16 2018 07:57:58 for Crypto++ by  <a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.14
</small></address>
</body>
</html>
distrib
>
Mageia
>
7
>
armv7hl
>
media
>
core-release
>
by-pkgid
>
0a67b807a02637f2cae68649d519a89d
>
files
>
2467
