<!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 File Reference</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="summary">
<a href="#nested-classes">Classes</a> |
<a href="#func-members">Functions</a> </div>
<div class="headertitle">
<div class="title">nbtheory.h File Reference</div> </div>
</div><!--header-->
<div class="contents">
<p>Classes and functions for number theoretic operations.
<a href="#details">More...</a></p>
<p><a href="nbtheory_8h_source.html">Go to the source code of this file.</a></p>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="nested-classes"></a>
Classes</h2></td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">class  </td><td class="memItemRight" valign="bottom"><a class="el" href="class_prime_selector.html">PrimeSelector</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft"> </td><td class="mdescRight">Application callback to signal suitability of a cabdidate prime. <a href="class_prime_selector.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">class  </td><td class="memItemRight" valign="bottom"><a class="el" href="class_prime_and_generator.html">PrimeAndGenerator</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft"> </td><td class="mdescRight">Generator of prime numbers of special forms. <a href="class_prime_and_generator.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="func-members"></a>
Functions</h2></td></tr>
<tr class="memitem:aa41f53fa846ea7546d7269b5d5c6a29f"><td class="memItemLeft" align="right" valign="top">const word16 * </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#aa41f53fa846ea7546d7269b5d5c6a29f">GetPrimeTable</a> (unsigned int &size)</td></tr>
<tr class="memdesc:aa41f53fa846ea7546d7269b5d5c6a29f"><td class="mdescLeft"> </td><td class="mdescRight">The Small Prime table. <a href="#aa41f53fa846ea7546d7269b5d5c6a29f">More...</a><br /></td></tr>
<tr class="separator:aa41f53fa846ea7546d7269b5d5c6a29f"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a4f5215dbaaf83eacf300ef54f0e941fc"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a4f5215dbaaf83eacf300ef54f0e941fc">MaurerProvablePrime</a> (<a class="el" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, unsigned int bits)</td></tr>
<tr class="memdesc:a4f5215dbaaf83eacf300ef54f0e941fc"><td class="mdescLeft"> </td><td class="mdescRight">Generates a provable prime. <a href="#a4f5215dbaaf83eacf300ef54f0e941fc">More...</a><br /></td></tr>
<tr class="separator:a4f5215dbaaf83eacf300ef54f0e941fc"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a40fab13239e32e04892023c81bb42597"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a40fab13239e32e04892023c81bb42597">MihailescuProvablePrime</a> (<a class="el" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, unsigned int bits)</td></tr>
<tr class="memdesc:a40fab13239e32e04892023c81bb42597"><td class="mdescLeft"> </td><td class="mdescRight">Generates a provable prime. <a href="#a40fab13239e32e04892023c81bb42597">More...</a><br /></td></tr>
<tr class="separator:a40fab13239e32e04892023c81bb42597"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a7bfb6022241ff5fb96250e366c68d49e"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a7bfb6022241ff5fb96250e366c68d49e">IsSmallPrime</a> (const <a class="el" href="class_integer.html">Integer</a> &p)</td></tr>
<tr class="memdesc:a7bfb6022241ff5fb96250e366c68d49e"><td class="mdescLeft"> </td><td class="mdescRight">Tests whether a number is a small prime. <a href="#a7bfb6022241ff5fb96250e366c68d49e">More...</a><br /></td></tr>
<tr class="separator:a7bfb6022241ff5fb96250e366c68d49e"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:aef5a456e724cba394ff8ad788eae777d"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#aef5a456e724cba394ff8ad788eae777d">TrialDivision</a> (const <a class="el" href="class_integer.html">Integer</a> &p, unsigned bound)</td></tr>
<tr class="memdesc:aef5a456e724cba394ff8ad788eae777d"><td class="mdescLeft"> </td><td class="mdescRight">Tests whether a number is divisible by a small prime. <a href="#aef5a456e724cba394ff8ad788eae777d">More...</a><br /></td></tr>
<tr class="separator:aef5a456e724cba394ff8ad788eae777d"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a7d7be62fa8075e10432f49cc08273707"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a7d7be62fa8075e10432f49cc08273707">SmallDivisorsTest</a> (const <a class="el" href="class_integer.html">Integer</a> &p)</td></tr>
<tr class="memdesc:a7d7be62fa8075e10432f49cc08273707"><td class="mdescLeft"> </td><td class="mdescRight">Tests whether a number is divisible by a small prime. <a href="#a7d7be62fa8075e10432f49cc08273707">More...</a><br /></td></tr>
<tr class="separator:a7d7be62fa8075e10432f49cc08273707"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:abcaf62227292dc648e6f2f11f2a6e158"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#abcaf62227292dc648e6f2f11f2a6e158">IsFermatProbablePrime</a> (const <a class="el" href="class_integer.html">Integer</a> &n, const <a class="el" href="class_integer.html">Integer</a> &b)</td></tr>
<tr class="memdesc:abcaf62227292dc648e6f2f11f2a6e158"><td class="mdescLeft"> </td><td class="mdescRight">Determine if a number is probably prime. <a href="#abcaf62227292dc648e6f2f11f2a6e158">More...</a><br /></td></tr>
<tr class="separator:abcaf62227292dc648e6f2f11f2a6e158"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:aada479f79cb8988f4df16df1e321fc7b"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#aada479f79cb8988f4df16df1e321fc7b">IsLucasProbablePrime</a> (const <a class="el" href="class_integer.html">Integer</a> &n)</td></tr>
<tr class="memdesc:aada479f79cb8988f4df16df1e321fc7b"><td class="mdescLeft"> </td><td class="mdescRight">Determine if a number is probably prime. <a href="#aada479f79cb8988f4df16df1e321fc7b">More...</a><br /></td></tr>
<tr class="separator:aada479f79cb8988f4df16df1e321fc7b"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a97c6199f98f7c5174373422d1e1c39af"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a97c6199f98f7c5174373422d1e1c39af">IsStrongProbablePrime</a> (const <a class="el" href="class_integer.html">Integer</a> &n, const <a class="el" href="class_integer.html">Integer</a> &b)</td></tr>
<tr class="memdesc:a97c6199f98f7c5174373422d1e1c39af"><td class="mdescLeft"> </td><td class="mdescRight">Determine if a number is probably prime. <a href="#a97c6199f98f7c5174373422d1e1c39af">More...</a><br /></td></tr>
<tr class="separator:a97c6199f98f7c5174373422d1e1c39af"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a9167952dad6998d1b854dee8355b53a0"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a9167952dad6998d1b854dee8355b53a0">IsStrongLucasProbablePrime</a> (const <a class="el" href="class_integer.html">Integer</a> &n)</td></tr>
<tr class="memdesc:a9167952dad6998d1b854dee8355b53a0"><td class="mdescLeft"> </td><td class="mdescRight">Determine if a number is probably prime. <a href="#a9167952dad6998d1b854dee8355b53a0">More...</a><br /></td></tr>
<tr class="separator:a9167952dad6998d1b854dee8355b53a0"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a637fa2abf1a48bc38f3c0d7c7edd679a"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a637fa2abf1a48bc38f3c0d7c7edd679a">RabinMillerTest</a> (<a class="el" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, const <a class="el" href="class_integer.html">Integer</a> &n, unsigned int rounds)</td></tr>
<tr class="memdesc:a637fa2abf1a48bc38f3c0d7c7edd679a"><td class="mdescLeft"> </td><td class="mdescRight">Determine if a number is probably prime. <a href="#a637fa2abf1a48bc38f3c0d7c7edd679a">More...</a><br /></td></tr>
<tr class="separator:a637fa2abf1a48bc38f3c0d7c7edd679a"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ae8442dd787d99d3604436a91799552bf"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#ae8442dd787d99d3604436a91799552bf">IsPrime</a> (const <a class="el" href="class_integer.html">Integer</a> &p)</td></tr>
<tr class="memdesc:ae8442dd787d99d3604436a91799552bf"><td class="mdescLeft"> </td><td class="mdescRight">Verifies a number is probably prime. <a href="#ae8442dd787d99d3604436a91799552bf">More...</a><br /></td></tr>
<tr class="separator:ae8442dd787d99d3604436a91799552bf"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a633d17045e229eccc3614426df054463"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a633d17045e229eccc3614426df054463">VerifyPrime</a> (<a class="el" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, const <a class="el" href="class_integer.html">Integer</a> &p, unsigned int level=1)</td></tr>
<tr class="memdesc:a633d17045e229eccc3614426df054463"><td class="mdescLeft"> </td><td class="mdescRight">Verifies a number is probably prime. <a href="#a633d17045e229eccc3614426df054463">More...</a><br /></td></tr>
<tr class="separator:a633d17045e229eccc3614426df054463"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:aaef9ef9567713cd9935e468309ebcc9d"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#aaef9ef9567713cd9935e468309ebcc9d">FirstPrime</a> (<a class="el" href="class_integer.html">Integer</a> &p, const <a class="el" href="class_integer.html">Integer</a> &max, const <a class="el" href="class_integer.html">Integer</a> &equiv, const <a class="el" href="class_integer.html">Integer</a> &mod, const <a class="el" href="class_prime_selector.html">PrimeSelector</a> *pSelector)</td></tr>
<tr class="memdesc:aaef9ef9567713cd9935e468309ebcc9d"><td class="mdescLeft"> </td><td class="mdescRight">Finds a random prime of special form. <a href="#aaef9ef9567713cd9935e468309ebcc9d">More...</a><br /></td></tr>
<tr class="separator:aaef9ef9567713cd9935e468309ebcc9d"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a404a825d6ad8d8b32e910db16b8da9f0"><td class="memItemLeft" align="right" valign="top"><a id="a404a825d6ad8d8b32e910db16b8da9f0"></a>
unsigned int </td><td class="memItemRight" valign="bottom"><b>PrimeSearchInterval</b> (const <a class="el" href="class_integer.html">Integer</a> &max)</td></tr>
<tr class="separator:a404a825d6ad8d8b32e910db16b8da9f0"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a6f2c28be97e3e4ad3d521f6213880a04"><td class="memItemLeft" align="right" valign="top"><a id="a6f2c28be97e3e4ad3d521f6213880a04"></a>
<a class="el" href="class_algorithm_parameters.html">AlgorithmParameters</a> </td><td class="memItemRight" valign="bottom"><b>MakeParametersForTwoPrimesOfEqualSize</b> (unsigned int productBitLength)</td></tr>
<tr class="separator:a6f2c28be97e3e4ad3d521f6213880a04"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ac1d98aa1d0ed1df97bf0dc194da5169a"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#ac1d98aa1d0ed1df97bf0dc194da5169a">GCD</a> (const <a class="el" href="class_integer.html">Integer</a> &a, const <a class="el" href="class_integer.html">Integer</a> &b)</td></tr>
<tr class="memdesc:ac1d98aa1d0ed1df97bf0dc194da5169a"><td class="mdescLeft"> </td><td class="mdescRight">Calculate the greatest common divisor. <a href="#ac1d98aa1d0ed1df97bf0dc194da5169a">More...</a><br /></td></tr>
<tr class="separator:ac1d98aa1d0ed1df97bf0dc194da5169a"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a1653aff24d226faac1ff141e665ef9e1"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a1653aff24d226faac1ff141e665ef9e1">RelativelyPrime</a> (const <a class="el" href="class_integer.html">Integer</a> &a, const <a class="el" href="class_integer.html">Integer</a> &b)</td></tr>
<tr class="memdesc:a1653aff24d226faac1ff141e665ef9e1"><td class="mdescLeft"> </td><td class="mdescRight">Determine relative primality. <a href="#a1653aff24d226faac1ff141e665ef9e1">More...</a><br /></td></tr>
<tr class="separator:a1653aff24d226faac1ff141e665ef9e1"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:adaa35c5ed3df59615477e3ae91cc8015"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#adaa35c5ed3df59615477e3ae91cc8015">LCM</a> (const <a class="el" href="class_integer.html">Integer</a> &a, const <a class="el" href="class_integer.html">Integer</a> &b)</td></tr>
<tr class="memdesc:adaa35c5ed3df59615477e3ae91cc8015"><td class="mdescLeft"> </td><td class="mdescRight">Calculate the least common multiple. <a href="#adaa35c5ed3df59615477e3ae91cc8015">More...</a><br /></td></tr>
<tr class="separator:adaa35c5ed3df59615477e3ae91cc8015"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:aa88bcc8ea0e0608098a17bec60abe61e"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#aa88bcc8ea0e0608098a17bec60abe61e">EuclideanMultiplicativeInverse</a> (const <a class="el" href="class_integer.html">Integer</a> &a, const <a class="el" href="class_integer.html">Integer</a> &b)</td></tr>
<tr class="memdesc:aa88bcc8ea0e0608098a17bec60abe61e"><td class="mdescLeft"> </td><td class="mdescRight">Calculate multiplicative inverse. <a href="#aa88bcc8ea0e0608098a17bec60abe61e">More...</a><br /></td></tr>
<tr class="separator:aa88bcc8ea0e0608098a17bec60abe61e"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ab3fae49135264b5b5afecd0331915040"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#ab3fae49135264b5b5afecd0331915040">CRT</a> (const <a class="el" href="class_integer.html">Integer</a> &xp, const <a class="el" href="class_integer.html">Integer</a> &p, const <a class="el" href="class_integer.html">Integer</a> &xq, const <a class="el" href="class_integer.html">Integer</a> &q, const <a class="el" href="class_integer.html">Integer</a> &u)</td></tr>
<tr class="memdesc:ab3fae49135264b5b5afecd0331915040"><td class="mdescLeft"> </td><td class="mdescRight">Chinese Remainder Theorem. <a href="#ab3fae49135264b5b5afecd0331915040">More...</a><br /></td></tr>
<tr class="separator:ab3fae49135264b5b5afecd0331915040"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:abffe3c03543252f53fcf59fdb2df765c"><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#abffe3c03543252f53fcf59fdb2df765c">Jacobi</a> (const <a class="el" href="class_integer.html">Integer</a> &a, const <a class="el" href="class_integer.html">Integer</a> &b)</td></tr>
<tr class="memdesc:abffe3c03543252f53fcf59fdb2df765c"><td class="mdescLeft"> </td><td class="mdescRight">Calculate the Jacobi symbol. <a href="#abffe3c03543252f53fcf59fdb2df765c">More...</a><br /></td></tr>
<tr class="separator:abffe3c03543252f53fcf59fdb2df765c"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a6f8b2f16d9cb4cdc4bfa5a785928044a"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a6f8b2f16d9cb4cdc4bfa5a785928044a">Lucas</a> (const <a class="el" href="class_integer.html">Integer</a> &e, const <a class="el" href="class_integer.html">Integer</a> &p, const <a class="el" href="class_integer.html">Integer</a> &n)</td></tr>
<tr class="memdesc:a6f8b2f16d9cb4cdc4bfa5a785928044a"><td class="mdescLeft"> </td><td class="mdescRight">Calculate the Lucas value. <a href="#a6f8b2f16d9cb4cdc4bfa5a785928044a">More...</a><br /></td></tr>
<tr class="separator:a6f8b2f16d9cb4cdc4bfa5a785928044a"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a9b5b91490b1ae3357ab4f0d863f103c1"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a9b5b91490b1ae3357ab4f0d863f103c1">InverseLucas</a> (const <a class="el" href="class_integer.html">Integer</a> &e, const <a class="el" href="class_integer.html">Integer</a> &m, const <a class="el" href="class_integer.html">Integer</a> &p, const <a class="el" href="class_integer.html">Integer</a> &q, const <a class="el" href="class_integer.html">Integer</a> &u)</td></tr>
<tr class="memdesc:a9b5b91490b1ae3357ab4f0d863f103c1"><td class="mdescLeft"> </td><td class="mdescRight">Calculate the inverse Lucas value. <a href="#a9b5b91490b1ae3357ab4f0d863f103c1">More...</a><br /></td></tr>
<tr class="separator:a9b5b91490b1ae3357ab4f0d863f103c1"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a1b800e2880542031bc81cbb7cd0bec3e"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a1b800e2880542031bc81cbb7cd0bec3e">ModularMultiplication</a> (const <a class="el" href="class_integer.html">Integer</a> &x, const <a class="el" href="class_integer.html">Integer</a> &y, const <a class="el" href="class_integer.html">Integer</a> &m)</td></tr>
<tr class="memdesc:a1b800e2880542031bc81cbb7cd0bec3e"><td class="mdescLeft"> </td><td class="mdescRight">Modular multiplication. <a href="#a1b800e2880542031bc81cbb7cd0bec3e">More...</a><br /></td></tr>
<tr class="separator:a1b800e2880542031bc81cbb7cd0bec3e"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a5365cc677fbc93221d9bdfaec442ca3d"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a5365cc677fbc93221d9bdfaec442ca3d">ModularExponentiation</a> (const <a class="el" href="class_integer.html">Integer</a> &x, const <a class="el" href="class_integer.html">Integer</a> &e, const <a class="el" href="class_integer.html">Integer</a> &m)</td></tr>
<tr class="memdesc:a5365cc677fbc93221d9bdfaec442ca3d"><td class="mdescLeft"> </td><td class="mdescRight">Modular exponentiation. <a href="#a5365cc677fbc93221d9bdfaec442ca3d">More...</a><br /></td></tr>
<tr class="separator:a5365cc677fbc93221d9bdfaec442ca3d"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:abb83c7bbd49b1761028d08a9a1016e68"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#abb83c7bbd49b1761028d08a9a1016e68">ModularSquareRoot</a> (const <a class="el" href="class_integer.html">Integer</a> &a, const <a class="el" href="class_integer.html">Integer</a> &p)</td></tr>
<tr class="memdesc:abb83c7bbd49b1761028d08a9a1016e68"><td class="mdescLeft"> </td><td class="mdescRight">Extract a modular square root. <a href="#abb83c7bbd49b1761028d08a9a1016e68">More...</a><br /></td></tr>
<tr class="separator:abb83c7bbd49b1761028d08a9a1016e68"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:aad7ca1c53c38a93997327226eddc0240"><td class="memItemLeft" align="right" valign="top"><a class="el" href="class_integer.html">Integer</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#aad7ca1c53c38a93997327226eddc0240">ModularRoot</a> (const <a class="el" href="class_integer.html">Integer</a> &a, const <a class="el" href="class_integer.html">Integer</a> &dp, const <a class="el" href="class_integer.html">Integer</a> &dq, const <a class="el" href="class_integer.html">Integer</a> &p, const <a class="el" href="class_integer.html">Integer</a> &q, const <a class="el" href="class_integer.html">Integer</a> &u)</td></tr>
<tr class="memdesc:aad7ca1c53c38a93997327226eddc0240"><td class="mdescLeft"> </td><td class="mdescRight">Extract a modular root. <a href="#aad7ca1c53c38a93997327226eddc0240">More...</a><br /></td></tr>
<tr class="separator:aad7ca1c53c38a93997327226eddc0240"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:aa308ad452a47cf22de4ac3204ab09e7d"><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#aa308ad452a47cf22de4ac3204ab09e7d">SolveModularQuadraticEquation</a> (<a class="el" href="class_integer.html">Integer</a> &r1, <a class="el" href="class_integer.html">Integer</a> &r2, const <a class="el" href="class_integer.html">Integer</a> &a, const <a class="el" href="class_integer.html">Integer</a> &b, const <a class="el" href="class_integer.html">Integer</a> &c, const <a class="el" href="class_integer.html">Integer</a> &p)</td></tr>
<tr class="memdesc:aa308ad452a47cf22de4ac3204ab09e7d"><td class="mdescLeft"> </td><td class="mdescRight">Solve a Modular Quadratic Equation. <a href="#aa308ad452a47cf22de4ac3204ab09e7d">More...</a><br /></td></tr>
<tr class="separator:aa308ad452a47cf22de4ac3204ab09e7d"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a0b8a9730d2aaeabc3c8582574ab9cf6d"><td class="memItemLeft" align="right" valign="top">unsigned int </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a0b8a9730d2aaeabc3c8582574ab9cf6d">DiscreteLogWorkFactor</a> (unsigned int bitlength)</td></tr>
<tr class="memdesc:a0b8a9730d2aaeabc3c8582574ab9cf6d"><td class="mdescLeft"> </td><td class="mdescRight">Estimate work factor. <a href="#a0b8a9730d2aaeabc3c8582574ab9cf6d">More...</a><br /></td></tr>
<tr class="separator:a0b8a9730d2aaeabc3c8582574ab9cf6d"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:a8e5a50115e2e7f5546884e4b9d9d1f30"><td class="memItemLeft" align="right" valign="top">unsigned int </td><td class="memItemRight" valign="bottom"><a class="el" href="nbtheory_8h.html#a8e5a50115e2e7f5546884e4b9d9d1f30">FactoringWorkFactor</a> (unsigned int bitlength)</td></tr>
<tr class="memdesc:a8e5a50115e2e7f5546884e4b9d9d1f30"><td class="mdescLeft"> </td><td class="mdescRight">Estimate work factor. <a href="#a8e5a50115e2e7f5546884e4b9d9d1f30">More...</a><br /></td></tr>
<tr class="separator:a8e5a50115e2e7f5546884e4b9d9d1f30"><td class="memSeparator" colspan="2"> </td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<div class="textblock"><p>Classes and functions for number theoretic operations. </p>
<p class="definition">Definition in file <a class="el" href="nbtheory_8h_source.html">nbtheory.h</a>.</p>
</div><h2 class="groupheader">Function Documentation</h2>
<a id="aa41f53fa846ea7546d7269b5d5c6a29f"></a>
<h2 class="memtitle"><span class="permalink"><a href="#aa41f53fa846ea7546d7269b5d5c6a29f">◆ </a></span>GetPrimeTable()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">const word16* GetPrimeTable </td>
<td>(</td>
<td class="paramtype">unsigned int & </td>
<td class="paramname"><em>size</em></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>The Small Prime table. </p>
<p>GetPrimeTable obtains pointer to small prime table and provides the size of the table. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00053">53</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a4f5215dbaaf83eacf300ef54f0e941fc"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a4f5215dbaaf83eacf300ef54f0e941fc">◆ </a></span>MaurerProvablePrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> MaurerProvablePrime </td>
<td>(</td>
<td class="paramtype"><a class="el" href="class_random_number_generator.html">RandomNumberGenerator</a> & </td>
<td class="paramname"><em>rng</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int </td>
<td class="paramname"><em>bits</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Generates a provable prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">rng</td><td>a <a class="el" href="class_random_number_generator.html" title="Interface for random number generators. ">RandomNumberGenerator</a> to produce random material </td></tr>
<tr><td class="paramname">bits</td><td>the number of bits in the prime number </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd><a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer()</a> meeting Maurer's tests for primality </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00510">510</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a40fab13239e32e04892023c81bb42597"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a40fab13239e32e04892023c81bb42597">◆ </a></span>MihailescuProvablePrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> MihailescuProvablePrime </td>
<td>(</td>
<td class="paramtype"><a class="el" href="class_random_number_generator.html">RandomNumberGenerator</a> & </td>
<td class="paramname"><em>rng</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int </td>
<td class="paramname"><em>bits</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Generates a provable prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">rng</td><td>a <a class="el" href="class_random_number_generator.html" title="Interface for random number generators. ">RandomNumberGenerator</a> to produce random material </td></tr>
<tr><td class="paramname">bits</td><td>the number of bits in the prime number </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd><a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer()</a> meeting Mihailescu's tests for primality</dd></dl>
<p>Mihailescu's methods performs a search using algorithmic progressions. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00470">470</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a7bfb6022241ff5fb96250e366c68d49e"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a7bfb6022241ff5fb96250e366c68d49e">◆ </a></span>IsSmallPrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool IsSmallPrime </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Tests whether a number is a small prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">p</td><td>a candidate prime to test </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if p is a small prime, false otherwise</dd></dl>
<p>Internally, the library maintains a table of the first 32719 prime numbers in sorted order. IsSmallPrime searches the table and returns true if p is in the table. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00060">60</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="aef5a456e724cba394ff8ad788eae777d"></a>
<h2 class="memtitle"><span class="permalink"><a href="#aef5a456e724cba394ff8ad788eae777d">◆ </a></span>TrialDivision()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool TrialDivision </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned </td>
<td class="paramname"><em>bound</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Tests whether a number is divisible by a small prime. </p>
<dl class="section return"><dt>Returns</dt><dd>true if p is divisible by some prime less than bound.</dd></dl>
<p><a class="el" href="nbtheory_8h.html#aef5a456e724cba394ff8ad788eae777d" title="Tests whether a number is divisible by a small prime. ">TrialDivision()</a> returns <code>true</code> if <code>p</code> is divisible by some prime less than <code>bound</code>. <code>bound</code> should not be greater than the largest entry in the prime table, which is 32719. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00071">71</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a7d7be62fa8075e10432f49cc08273707"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a7d7be62fa8075e10432f49cc08273707">◆ </a></span>SmallDivisorsTest()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool SmallDivisorsTest </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Tests whether a number is divisible by a small prime. </p>
<dl class="section return"><dt>Returns</dt><dd>true if p is NOT divisible by small primes.</dd></dl>
<p><a class="el" href="nbtheory_8h.html#a7d7be62fa8075e10432f49cc08273707" title="Tests whether a number is divisible by a small prime. ">SmallDivisorsTest()</a> returns <code>true</code> if <code>p</code> is NOT divisible by some prime less than 32719. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00089">89</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="abcaf62227292dc648e6f2f11f2a6e158"></a>
<h2 class="memtitle"><span class="permalink"><a href="#abcaf62227292dc648e6f2f11f2a6e158">◆ </a></span>IsFermatProbablePrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool IsFermatProbablePrime </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>n</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>b</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Determine if a number is probably prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">n</td><td>the number to test </td></tr>
<tr><td class="paramname">b</td><td>the base to exponentiate </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if the number n is probably prime, false otherwise.</dd></dl>
<p>IsFermatProbablePrime raises <code>b</code> to the <code>n-1</code> power and checks if the result is congruent to 1 modulo <code>n</code>.</p>
<p>These is no reason to use IsFermatProbablePrime, use IsStrongProbablePrime or IsStrongLucasProbablePrime instead. </p><dl class="section see"><dt>See also</dt><dd><a class="el" href="nbtheory_8h.html#a97c6199f98f7c5174373422d1e1c39af" title="Determine if a number is probably prime. ">IsStrongProbablePrime</a>, <a class="el" href="nbtheory_8h.html#a9167952dad6998d1b854dee8355b53a0" title="Determine if a number is probably prime. ">IsStrongLucasProbablePrime</a> </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00096">96</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="aada479f79cb8988f4df16df1e321fc7b"></a>
<h2 class="memtitle"><span class="permalink"><a href="#aada479f79cb8988f4df16df1e321fc7b">◆ </a></span>IsLucasProbablePrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool IsLucasProbablePrime </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>n</em></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Determine if a number is probably prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">n</td><td>the number to test </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if the number n is probably prime, false otherwise.</dd></dl>
<p>These is no reason to use IsLucasProbablePrime, use IsStrongProbablePrime or IsStrongLucasProbablePrime instead. </p><dl class="section see"><dt>See also</dt><dd><a class="el" href="nbtheory_8h.html#a97c6199f98f7c5174373422d1e1c39af" title="Determine if a number is probably prime. ">IsStrongProbablePrime</a>, <a class="el" href="nbtheory_8h.html#a9167952dad6998d1b854dee8355b53a0" title="Determine if a number is probably prime. ">IsStrongLucasProbablePrime</a> </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00155">155</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a97c6199f98f7c5174373422d1e1c39af"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a97c6199f98f7c5174373422d1e1c39af">◆ </a></span>IsStrongProbablePrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool IsStrongProbablePrime </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>n</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>b</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Determine if a number is probably prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">n</td><td>the number to test </td></tr>
<tr><td class="paramname">b</td><td>the base to exponentiate </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if the number n is probably prime, false otherwise. </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00105">105</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a9167952dad6998d1b854dee8355b53a0"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a9167952dad6998d1b854dee8355b53a0">◆ </a></span>IsStrongLucasProbablePrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool IsStrongLucasProbablePrime </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>n</em></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Determine if a number is probably prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">n</td><td>the number to test </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if the number n is probably prime, false otherwise. </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00182">182</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a637fa2abf1a48bc38f3c0d7c7edd679a"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a637fa2abf1a48bc38f3c0d7c7edd679a">◆ </a></span>RabinMillerTest()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool RabinMillerTest </td>
<td>(</td>
<td class="paramtype"><a class="el" href="class_random_number_generator.html">RandomNumberGenerator</a> & </td>
<td class="paramname"><em>rng</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>n</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int </td>
<td class="paramname"><em>rounds</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Determine if a number is probably prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">rng</td><td>a <a class="el" href="class_random_number_generator.html" title="Interface for random number generators. ">RandomNumberGenerator</a> to produce random material </td></tr>
<tr><td class="paramname">n</td><td>the number to test </td></tr>
<tr><td class="paramname">rounds</td><td>the number of tests to perform</td></tr>
</table>
</dd>
</dl>
<p>This is the Rabin-Miller primality test, i.e. repeating the strong probable prime test for several rounds with random bases </p><dl class="section see"><dt>See also</dt><dd><a href="https://crypto.stackexchange.com/q/17707/10496">Trial divisions before Miller-Rabin checks?</a> on Crypto Stack Exchange </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00138">138</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="ae8442dd787d99d3604436a91799552bf"></a>
<h2 class="memtitle"><span class="permalink"><a href="#ae8442dd787d99d3604436a91799552bf">◆ </a></span>IsPrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool IsPrime </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Verifies a number is probably prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">p</td><td>a candidate prime to test </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if p is a probable prime, false otherwise</dd></dl>
<p><a class="el" href="nbtheory_8h.html#ae8442dd787d99d3604436a91799552bf" title="Verifies a number is probably prime. ">IsPrime()</a> is suitable for testing candidate primes when creating them. Internally, <a class="el" href="nbtheory_8h.html#ae8442dd787d99d3604436a91799552bf" title="Verifies a number is probably prime. ">IsPrime()</a> utilizes <a class="el" href="nbtheory_8h.html#a7d7be62fa8075e10432f49cc08273707" title="Tests whether a number is divisible by a small prime. ">SmallDivisorsTest()</a>, <a class="el" href="nbtheory_8h.html#a97c6199f98f7c5174373422d1e1c39af" title="Determine if a number is probably prime. ">IsStrongProbablePrime()</a> and <a class="el" href="nbtheory_8h.html#a9167952dad6998d1b854dee8355b53a0" title="Determine if a number is probably prime. ">IsStrongLucasProbablePrime()</a>. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00237">237</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a633d17045e229eccc3614426df054463"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a633d17045e229eccc3614426df054463">◆ </a></span>VerifyPrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool VerifyPrime </td>
<td>(</td>
<td class="paramtype"><a class="el" href="class_random_number_generator.html">RandomNumberGenerator</a> & </td>
<td class="paramname"><em>rng</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">unsigned int </td>
<td class="paramname"><em>level</em> = <code>1</code> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Verifies a number is probably prime. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">rng</td><td>a <a class="el" href="class_random_number_generator.html" title="Interface for random number generators. ">RandomNumberGenerator</a> for randomized testing </td></tr>
<tr><td class="paramname">p</td><td>a candidate prime to test </td></tr>
<tr><td class="paramname">level</td><td>the level of thoroughness of testing </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if p is a strong probable prime, false otherwise</dd></dl>
<p><a class="el" href="nbtheory_8h.html#a633d17045e229eccc3614426df054463" title="Verifies a number is probably prime. ">VerifyPrime()</a> is suitable for testing candidate primes created by others. Internally, <a class="el" href="nbtheory_8h.html#a633d17045e229eccc3614426df054463" title="Verifies a number is probably prime. ">VerifyPrime()</a> utilizes <a class="el" href="nbtheory_8h.html#ae8442dd787d99d3604436a91799552bf" title="Verifies a number is probably prime. ">IsPrime()</a> and one-round <a class="el" href="nbtheory_8h.html#a637fa2abf1a48bc38f3c0d7c7edd679a" title="Determine if a number is probably prime. ">RabinMillerTest()</a>. If the candiate passes and level is greater than 1, then 10 round <a class="el" href="nbtheory_8h.html#a637fa2abf1a48bc38f3c0d7c7edd679a" title="Determine if a number is probably prime. ">RabinMillerTest()</a> primality testing is performed. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00247">247</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="aaef9ef9567713cd9935e468309ebcc9d"></a>
<h2 class="memtitle"><span class="permalink"><a href="#aaef9ef9567713cd9935e468309ebcc9d">◆ </a></span>FirstPrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool FirstPrime </td>
<td>(</td>
<td class="paramtype"><a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>max</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>equiv</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>mod</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_prime_selector.html">PrimeSelector</a> * </td>
<td class="paramname"><em>pSelector</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Finds a random prime of special form. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">p</td><td>an <a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer</a> reference to receive the prime </td></tr>
<tr><td class="paramname">max</td><td>the maximum value </td></tr>
<tr><td class="paramname">equiv</td><td>the equivalence class based on the parameter mod </td></tr>
<tr><td class="paramname">mod</td><td>the modulus used to reduce the equivalence class </td></tr>
<tr><td class="paramname">pSelector</td><td>pointer to a <a class="el" href="class_prime_selector.html" title="Application callback to signal suitability of a cabdidate prime. ">PrimeSelector</a> function for the application to signal suitability </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if and only if <a class="el" href="nbtheory_8h.html#aaef9ef9567713cd9935e468309ebcc9d" title="Finds a random prime of special form. ">FirstPrime()</a> finds a prime and returns the prime through p. If <a class="el" href="nbtheory_8h.html#aaef9ef9567713cd9935e468309ebcc9d" title="Finds a random prime of special form. ">FirstPrime()</a> returns false, then no such prime exists and the value of p is undefined</dd></dl>
<p><a class="el" href="nbtheory_8h.html#aaef9ef9567713cd9935e468309ebcc9d" title="Finds a random prime of special form. ">FirstPrime()</a> uses a fast sieve to find the first probable prime in <code>{x | p<=x<=max and xmod==equiv}</code> </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00379">379</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="ac1d98aa1d0ed1df97bf0dc194da5169a"></a>
<h2 class="memtitle"><span class="permalink"><a href="#ac1d98aa1d0ed1df97bf0dc194da5169a">◆ </a></span>GCD()</h2>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> GCD </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>a</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>b</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Calculate the greatest common divisor. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">a</td><td>the first term </td></tr>
<tr><td class="paramname">b</td><td>the second term </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the greatest common divisor if one exists, 0 otherwise. </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8h_source.html#l00142">142</a> of file <a class="el" href="nbtheory_8h_source.html">nbtheory.h</a>.</p>
</div>
</div>
<a id="a1653aff24d226faac1ff141e665ef9e1"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a1653aff24d226faac1ff141e665ef9e1">◆ </a></span>RelativelyPrime()</h2>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname">bool RelativelyPrime </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>a</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>b</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Determine relative primality. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">a</td><td>the first term </td></tr>
<tr><td class="paramname">b</td><td>the second term </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if <code>a</code> and <code>b</code> are relatively prime, false otherwise. </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8h_source.html#l00149">149</a> of file <a class="el" href="nbtheory_8h_source.html">nbtheory.h</a>.</p>
</div>
</div>
<a id="adaa35c5ed3df59615477e3ae91cc8015"></a>
<h2 class="memtitle"><span class="permalink"><a href="#adaa35c5ed3df59615477e3ae91cc8015">◆ </a></span>LCM()</h2>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> LCM </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>a</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>b</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Calculate the least common multiple. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">a</td><td>the first term </td></tr>
<tr><td class="paramname">b</td><td>the second term </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the least common multiple of <code>a</code> and <code>b</code>. </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8h_source.html#l00156">156</a> of file <a class="el" href="nbtheory_8h_source.html">nbtheory.h</a>.</p>
</div>
</div>
<a id="aa88bcc8ea0e0608098a17bec60abe61e"></a>
<h2 class="memtitle"><span class="permalink"><a href="#aa88bcc8ea0e0608098a17bec60abe61e">◆ </a></span>EuclideanMultiplicativeInverse()</h2>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> EuclideanMultiplicativeInverse </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>a</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>b</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Calculate multiplicative inverse. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">a</td><td>the number to test </td></tr>
<tr><td class="paramname">b</td><td>the modulus </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>an <a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer</a> <code>(a ^ -1) % n</code> or 0 if none exists.</dd></dl>
<p>EuclideanMultiplicativeInverse returns the multiplicative inverse of the <a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer</a> <code>*a</code> modulo the <a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer</a> <code>b</code>. If no <a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer</a> exists then <a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer</a> 0 is returned. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8h_source.html#l00165">165</a> of file <a class="el" href="nbtheory_8h_source.html">nbtheory.h</a>.</p>
</div>
</div>
<a id="ab3fae49135264b5b5afecd0331915040"></a>
<h2 class="memtitle"><span class="permalink"><a href="#ab3fae49135264b5b5afecd0331915040">◆ </a></span>CRT()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> CRT </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>xp</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>xq</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>q</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>u</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Chinese Remainder Theorem. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">xp</td><td>the first number, mod p </td></tr>
<tr><td class="paramname">p</td><td>the first prime modulus </td></tr>
<tr><td class="paramname">xq</td><td>the second number, mod q </td></tr>
<tr><td class="paramname">q</td><td>the second prime modulus </td></tr>
<tr><td class="paramname">u</td><td>inverse of p mod q </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the CRT value of the parameters</dd></dl>
<p>CRT uses the Chinese Remainder Theorem to calculate <code>x</code> given <code>x mod p</code> and <code>x mod q</code>, and <code>u</code> the inverse of <code>p mod q</code>. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00553">553</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="abffe3c03543252f53fcf59fdb2df765c"></a>
<h2 class="memtitle"><span class="permalink"><a href="#abffe3c03543252f53fcf59fdb2df765c">◆ </a></span>Jacobi()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">int Jacobi </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>a</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>b</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Calculate the Jacobi symbol. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">a</td><td>the first term </td></tr>
<tr><td class="paramname">b</td><td>the second term </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the the Jacobi symbol.</dd></dl>
<p>Jacobi symbols are calculated using the following rules:</p><ol type="1">
<li>if <code>b</code> is prime, then <code>Jacobi(a, b)</code>, then return 0</li>
<li>if <code>ab</code>==0 AND <code>a</code> is quadratic residue <code>mod b</code>, then return 1</li>
<li>return -1 otherwise</li>
</ol>
<p>Refer to a number theory book for what Jacobi symbol means when <code>b</code> is not prime. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00785">785</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a6f8b2f16d9cb4cdc4bfa5a785928044a"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a6f8b2f16d9cb4cdc4bfa5a785928044a">◆ </a></span>Lucas()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> Lucas </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>e</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>n</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Calculate the Lucas value. </p>
<dl class="section return"><dt>Returns</dt><dd>the Lucas value</dd></dl>
<p><a class="el" href="nbtheory_8h.html#a6f8b2f16d9cb4cdc4bfa5a785928044a" title="Calculate the Lucas value. ">Lucas()</a> calculates the Lucas function <code>V_e(p, 1) mod n</code>. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00812">812</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a9b5b91490b1ae3357ab4f0d863f103c1"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a9b5b91490b1ae3357ab4f0d863f103c1">◆ </a></span>InverseLucas()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> InverseLucas </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>e</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>m</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>q</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>u</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Calculate the inverse Lucas value. </p>
<dl class="section return"><dt>Returns</dt><dd>the inverse Lucas value</dd></dl>
<p><a class="el" href="nbtheory_8h.html#a9b5b91490b1ae3357ab4f0d863f103c1" title="Calculate the inverse Lucas value. ">InverseLucas()</a> calculates <code>x</code> such that <code>m==Lucas(e, x, p*q)</code>, <code>p q</code> primes, <code>u</code> is inverse of <code>p mod q</code>. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00998">998</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a1b800e2880542031bc81cbb7cd0bec3e"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a1b800e2880542031bc81cbb7cd0bec3e">◆ </a></span>ModularMultiplication()</h2>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> ModularMultiplication </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>x</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>y</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>m</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Modular multiplication. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">x</td><td>the first term </td></tr>
<tr><td class="paramname">y</td><td>the second term </td></tr>
<tr><td class="paramname">m</td><td>the modulus </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>an <a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer</a> <code>(x * y) % m</code>. </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8h_source.html#l00207">207</a> of file <a class="el" href="nbtheory_8h_source.html">nbtheory.h</a>.</p>
</div>
</div>
<a id="a5365cc677fbc93221d9bdfaec442ca3d"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a5365cc677fbc93221d9bdfaec442ca3d">◆ </a></span>ModularExponentiation()</h2>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> ModularExponentiation </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>x</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>e</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>m</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Modular exponentiation. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">x</td><td>the base </td></tr>
<tr><td class="paramname">e</td><td>the exponent </td></tr>
<tr><td class="paramname">m</td><td>the modulus </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>an <a class="el" href="class_integer.html" title="Multiple precision integer with arithmetic operations. ">Integer</a> <code>(a ^ b) % m</code>. </dd></dl>
<p class="definition">Definition at line <a class="el" href="nbtheory_8h_source.html#l00215">215</a> of file <a class="el" href="nbtheory_8h_source.html">nbtheory.h</a>.</p>
</div>
</div>
<a id="abb83c7bbd49b1761028d08a9a1016e68"></a>
<h2 class="memtitle"><span class="permalink"><a href="#abb83c7bbd49b1761028d08a9a1016e68">◆ </a></span>ModularSquareRoot()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> ModularSquareRoot </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>a</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Extract a modular square root. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">a</td><td>the number to extract square root </td></tr>
<tr><td class="paramname">p</td><td>the prime modulus </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the modular square root if it exists</dd></dl>
<p>ModularSquareRoot returns <code>x</code> such that <code>x*xp == a</code>, <code>p</code> prime </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00572">572</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="aad7ca1c53c38a93997327226eddc0240"></a>
<h2 class="memtitle"><span class="permalink"><a href="#aad7ca1c53c38a93997327226eddc0240">◆ </a></span>ModularRoot()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="class_integer.html">Integer</a> ModularRoot </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>a</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>dp</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>dq</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>q</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>u</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Extract a modular root. </p>
<dl class="section return"><dt>Returns</dt><dd>a modular root if it exists</dd></dl>
<p>ModularRoot returns <code>x</code> such that <code>a==ModularExponentiation(x, e, p*q)</code>, <code>p</code> <code>q</code> primes, and <code>e</code> relatively prime to <code>(p-1)*(q-1)</code>, <code>dp=d%(p-1)</code>, <code>dq=d%(q-1)</code>, (d is inverse of <code>e mod (p-1)*(q-1)</code>) and <code>u=inverse of p mod q</code>. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00646">646</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="aa308ad452a47cf22de4ac3204ab09e7d"></a>
<h2 class="memtitle"><span class="permalink"><a href="#aa308ad452a47cf22de4ac3204ab09e7d">◆ </a></span>SolveModularQuadraticEquation()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool SolveModularQuadraticEquation </td>
<td>(</td>
<td class="paramtype"><a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>r1</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>r2</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>a</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>b</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>c</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="class_integer.html">Integer</a> & </td>
<td class="paramname"><em>p</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Solve a Modular Quadratic Equation. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">r1</td><td>the first residue </td></tr>
<tr><td class="paramname">r2</td><td>the second residue </td></tr>
<tr><td class="paramname">a</td><td>the first coefficient </td></tr>
<tr><td class="paramname">b</td><td>the second coefficient </td></tr>
<tr><td class="paramname">c</td><td>the third constant </td></tr>
<tr><td class="paramname">p</td><td>the prime modulus </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>true if solutions exist</dd></dl>
<p><a class="el" href="nbtheory_8h.html#aa308ad452a47cf22de4ac3204ab09e7d" title="Solve a Modular Quadratic Equation. ">SolveModularQuadraticEquation()</a> finds <code>r1</code> and <code>r2</code> such that <code>ax^2 + bx + c == 0 (mod p)</code> for x in <code>{r1, r2}</code>, <code>p</code> prime. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l00621">621</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a0b8a9730d2aaeabc3c8582574ab9cf6d"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a0b8a9730d2aaeabc3c8582574ab9cf6d">◆ </a></span>DiscreteLogWorkFactor()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">unsigned int DiscreteLogWorkFactor </td>
<td>(</td>
<td class="paramtype">unsigned int </td>
<td class="paramname"><em>bitlength</em></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Estimate work factor. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">bitlength</td><td>the size of the number, in bits </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the estimated work factor, in operations</dd></dl>
<p>DiscreteLogWorkFactor returns log base 2 of estimated number of operations to calculate discrete log or factor a number. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l01027">1027</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
<a id="a8e5a50115e2e7f5546884e4b9d9d1f30"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a8e5a50115e2e7f5546884e4b9d9d1f30">◆ </a></span>FactoringWorkFactor()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">unsigned int FactoringWorkFactor </td>
<td>(</td>
<td class="paramtype">unsigned int </td>
<td class="paramname"><em>bitlength</em></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Estimate work factor. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">bitlength</td><td>the size of the number, in bits </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the estimated work factor, in operations</dd></dl>
<p>FactoringWorkFactor returns log base 2 of estimated number of operations to calculate discrete log or factor a number. </p>
<p class="definition">Definition at line <a class="el" href="nbtheory_8cpp_source.html#l01019">1019</a> of file <a class="el" href="nbtheory_8cpp_source.html">nbtheory.cpp</a>.</p>
</div>
</div>
</div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Sun Sep 16 2018 07:58:11 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
>
2466
