<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>~/ntl-11.4.2/doc/ZZ.cpp.html</title>
<meta name="Generator" content="Vim/8.0">
<meta name="plugin-version" content="vim7.4_v2">
<meta name="syntax" content="cpp">
<meta name="settings" content="use_css,pre_wrap,no_foldcolumn,expand_tabs,prevent_copy=">
<meta name="colorscheme" content="macvim">
<style type="text/css">
<!--
pre { white-space: pre-wrap; font-family: monospace; color: #000000; background-color: #ffffff; }
body { font-family: monospace; color: #000000; background-color: #ffffff; }
* { font-size: 1em; }
.String { color: #4a708b; }
.PreProc { color: #1874cd; }
.Constant { color: #ff8c00; }
.Statement { color: #b03060; font-weight: bold; }
.Comment { color: #0000ee; font-style: italic; }
.Type { color: #008b00; font-weight: bold; }
-->
</style>
<script type='text/javascript'>
<!--
-->
</script>
</head>
<body>
<pre id='vimCodeElement'>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment">MODULE: ZZ</span>
<span class="Comment">SUMMARY:</span>
<span class="Comment">The class ZZ is used to represent signed, arbitrary length integers.</span>
<span class="Comment">Routines are provided for all of the basic arithmetic operations, as</span>
<span class="Comment">well as for some more advanced operations such as primality testing.</span>
<span class="Comment">Space is automatically managed by the constructors and destructors.</span>
<span class="Comment">This module also provides routines for generating small primes, and</span>
<span class="Comment">fast routines for performing modular arithmetic on single-precision</span>
<span class="Comment">numbers.</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="PreProc">#include </span><span class="String"><NTL/tools.h></span>
<span class="Type">class</span> ZZ {
<span class="Statement">public</span>:
ZZ(); <span class="Comment">// initial value is 0</span>
ZZ(<span class="Type">const</span> ZZ& a); <span class="Comment">// copy constructor</span>
<span class="Type">explicit</span> ZZ(<span class="Type">long</span> a); <span class="Comment">// promotion constructor</span>
~ZZ(); <span class="Comment">// destructor</span>
ZZ& <span class="Statement">operator</span>=(<span class="Type">const</span> ZZ& a); <span class="Comment">// assignment operator</span>
ZZ& <span class="Statement">operator</span>=(<span class="Type">long</span> a);
ZZ(ZZ&& a);
<span class="Comment">// move constructor (C++11 only)</span>
<span class="Comment">// declared noexcept unless NTL_EXCEPTIONS flag is set</span>
ZZ& <span class="Statement">operator</span>=(ZZ&& a);
<span class="Comment">// move assignment (C++11 only)</span>
<span class="Comment">// declared noexcept unless NTL_EXCEPTIONS flag is set</span>
<span class="Comment">// typedefs to aid in generic programming</span>
<span class="Type">typedef</span> ZZ_p residue_type;
<span class="Type">typedef</span> ZZX poly_type;
<span class="Comment">// ...</span>
};
<span class="Comment">// NOTE: A ZZ is represented as a sequence of "limbs",</span>
<span class="Comment">// where each limb is between 0 and 2^{NTL_ZZ_NBITS-1}.</span>
<span class="Comment">// NTL_ZZ_NBITS is macros defined in <NTL/ZZ.h>.</span>
<span class="Comment">// SIZE INVARIANT: the number of bits in a ZZ is always less than</span>
<span class="Comment">// 2^(NTL_BITS_PER_LONG-4).</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Comparison</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Comment">// The usual comparison operators: </span>
<span class="Type">long</span> <span class="Statement">operator</span>==(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Type">long</span> <span class="Statement">operator</span>!=(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Type">long</span> <span class="Statement">operator</span><(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Type">long</span> <span class="Statement">operator</span>>(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Type">long</span> <span class="Statement">operator</span><=(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Type">long</span> <span class="Statement">operator</span>>=(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Comment">// other stuff:</span>
<span class="Type">long</span> sign(<span class="Type">const</span> ZZ& a); <span class="Comment">// returns sign of a (-1, 0, +1)</span>
<span class="Type">long</span> IsZero(<span class="Type">const</span> ZZ& a); <span class="Comment">// test for 0</span>
<span class="Type">long</span> IsOne(<span class="Type">const</span> ZZ& a); <span class="Comment">// test for 1</span>
<span class="Type">long</span> compare(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// returns sign of a-b (-1, 0, or 1).</span>
<span class="Comment">// PROMOTIONS: the comparison operators and the function compare</span>
<span class="Comment">// support promotion from long to ZZ on (a, b).</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Addition</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Comment">// operator notation:</span>
ZZ <span class="Statement">operator</span>+(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
ZZ <span class="Statement">operator</span>-(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
ZZ <span class="Statement">operator</span>-(<span class="Type">const</span> ZZ& a); <span class="Comment">// unary -</span>
ZZ& <span class="Statement">operator</span>+=(ZZ& x, <span class="Type">const</span> ZZ& a);
ZZ& <span class="Statement">operator</span>+=(ZZ& x, <span class="Type">long</span> a);
ZZ& <span class="Statement">operator</span>-=(ZZ& x, <span class="Type">const</span> ZZ& a);
ZZ& <span class="Statement">operator</span>-=(ZZ& x, <span class="Type">long</span> a);
ZZ& <span class="Statement">operator</span>++(ZZ& x); <span class="Comment">// prefix</span>
<span class="Type">void</span> <span class="Statement">operator</span>++(ZZ& x, <span class="Type">int</span>); <span class="Comment">// postfix</span>
ZZ& <span class="Statement">operator</span>--(ZZ& x); <span class="Comment">// prefix</span>
<span class="Type">void</span> <span class="Statement">operator</span>--(ZZ& x, <span class="Type">int</span>); <span class="Comment">// postfix</span>
<span class="Comment">// procedural versions:</span>
<span class="Type">void</span> add(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// x = a + b</span>
<span class="Type">void</span> sub(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// x = a - b</span>
<span class="Type">void</span> SubPos(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// x = a-b; assumes a >= b >= 0.</span>
<span class="Type">void</span> negate(ZZ& x, <span class="Type">const</span> ZZ& a); <span class="Comment">// x = -a</span>
<span class="Type">void</span> abs(ZZ& x, <span class="Type">const</span> ZZ& a); <span class="Comment">// x = |a|</span>
ZZ abs(<span class="Type">const</span> ZZ& a);
<span class="Comment">// PROMOTIONS: binary +, -, as well as the procedural versions add, sub</span>
<span class="Comment">// support promotions from long to ZZ on (a, b).</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Multiplication</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Comment">// operator notation:</span>
ZZ <span class="Statement">operator</span>*(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
ZZ& <span class="Statement">operator</span>*=(ZZ& x, <span class="Type">const</span> ZZ& a);
ZZ& <span class="Statement">operator</span>*=(ZZ& x, <span class="Type">long</span> a);
<span class="Comment">// procedural versions:</span>
<span class="Type">void</span> mul(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// x = a * b</span>
<span class="Type">void</span> sqr(ZZ& x, <span class="Type">const</span> ZZ& a); <span class="Comment">// x = a*a</span>
ZZ sqr(<span class="Type">const</span> ZZ& a);
<span class="Comment">// PROMOTIONS: operator * and procedure mul support promotion</span>
<span class="Comment">// from long to ZZ on (a, b).</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Combined Multiply and Add </span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">void</span> MulAddTo(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// x += a*b</span>
<span class="Type">void</span> MulAddTo(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> b); <span class="Comment">// x += a*b</span>
<span class="Type">void</span> MulSubFrom(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// x -= a*b</span>
<span class="Type">void</span> MulSubFrom(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> b); <span class="Comment">// x -= a*b</span>
<span class="Comment">// NOTE: these are provided for both convenience and efficiency.</span>
<span class="Comment">// The single-precision versions may be significantly</span>
<span class="Comment">// faster than the code sequence </span>
<span class="Comment">// mul(tmp, a, b); add(x, x, tmp);</span>
<span class="Comment">// However, for the single-precision version, the use-case</span>
<span class="Comment">// that is optimized is for |b| < 2^{NTL_WSP_BOUND}.</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Division</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Comment">// operator notation:</span>
ZZ <span class="Statement">operator</span>/(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
ZZ <span class="Statement">operator</span>/(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> b);
ZZ <span class="Statement">operator</span>%(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Type">long</span> <span class="Statement">operator</span>%(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> b);
ZZ& <span class="Statement">operator</span>/=(ZZ& x, <span class="Type">const</span> ZZ& b);
ZZ& <span class="Statement">operator</span>/=(ZZ& x, <span class="Type">long</span> b);
ZZ& <span class="Statement">operator</span>%=(ZZ& x, <span class="Type">const</span> ZZ& b);
<span class="Comment">// procedural versions:</span>
<span class="Type">void</span> DivRem(ZZ& q, ZZ& r, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Comment">// q = floor(a/b), r = a - b*q.</span>
<span class="Comment">// This implies that:</span>
<span class="Comment">// |r| < |b|, and if r != 0, sign(r) = sign(b)</span>
<span class="Type">void</span> div(ZZ& q, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Comment">// q = floor(a/b)</span>
<span class="Type">void</span> rem(ZZ& r, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Comment">// q = floor(a/b), r = a - b*q</span>
<span class="Comment">// single-precision variants:</span>
<span class="Type">long</span> DivRem(ZZ& q, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> b);
<span class="Comment">// q = floor(a/b), r = a - b*q, return value is r.</span>
<span class="Type">long</span> rem(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> b);
<span class="Comment">// q = floor(a/b), r = a - b*q, return value is r.</span>
<span class="Comment">// divisibility testing:</span>
<span class="Type">long</span> divide(ZZ& q, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Type">long</span> divide(ZZ& q, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> b);
<span class="Comment">// if b | a, sets q = a/b and returns 1; otherwise returns 0.</span>
<span class="Type">long</span> divide(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Type">long</span> divide(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> b);
<span class="Comment">// if b | a, returns 1; otherwise returns 0.</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> GCD's</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">void</span> GCD(ZZ& d, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
ZZ GCD(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Comment">// d = gcd(a, b) (which is always non-negative). Uses a binary GCD</span>
<span class="Comment">// algorithm.</span>
<span class="Type">void</span> XGCD(ZZ& d, ZZ& s, ZZ& t, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Comment">// d = gcd(a, b) = a*s + b*t.</span>
<span class="Comment">// The coefficients s and t are defined according to the standard</span>
<span class="Comment">// Euclidean algorithm applied to |a| and |b|, with the signs then</span>
<span class="Comment">// adjusted according to the signs of a and b.</span>
<span class="Comment">// The implementation may or may not Euclid's algorithm,</span>
<span class="Comment">// but the coefficients s and t are always computed as if </span>
<span class="Comment">// it did.</span>
<span class="Comment">// In particular, the following inequalties should hold:</span>
<span class="Comment">// |s| <= 1 OR |s| < |b|/(2*d)</span>
<span class="Comment">// |t| <= 1 OR |t| < |a|/(2*d)</span>
<span class="Comment">// special-purpose single-precision variants:</span>
<span class="Type">long</span> GCD(<span class="Type">long</span> a, <span class="Type">long</span> b);
<span class="Comment">// return value is gcd(a, b) (which is always non-negative)</span>
<span class="Type">void</span> XGCD(<span class="Type">long</span>& d, <span class="Type">long</span>& s, <span class="Type">long</span>& t, <span class="Type">long</span> a, <span class="Type">long</span> b);
<span class="Comment">// d = gcd(a, b) = a*s + b*t.</span>
<span class="Comment">// The coefficients s and t are defined according to the standard</span>
<span class="Comment">// Euclidean algorithm applied to |a| and |b|, with the signs then</span>
<span class="Comment">// adjusted according to the signs of a and b.</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Modular Arithmetic</span>
<span class="Comment">The following routines perform arithmetic mod n, where n > 1.</span>
<span class="Comment">All arguments (other than exponents) are assumed to be in the range</span>
<span class="Comment">0..n-1. Some routines may check this and raise an error if this</span>
<span class="Comment">does not hold. Others may not, and the behaviour is unpredictable</span>
<span class="Comment">in this case.</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">void</span> AddMod(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b, <span class="Type">const</span> ZZ& n); <span class="Comment">// x = (a+b)%n</span>
ZZ AddMod(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b, <span class="Type">const</span> ZZ& n);
<span class="Type">void</span> SubMod(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b, <span class="Type">const</span> ZZ& n); <span class="Comment">// x = (a-b)%n</span>
ZZ SubMod(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b, <span class="Type">const</span> ZZ& n);
<span class="Type">void</span> NegateMod(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n); <span class="Comment">// x = -a % n</span>
ZZ NegateMod(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n);
<span class="Type">void</span> MulMod(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b, <span class="Type">const</span> ZZ& n); <span class="Comment">// x = (a*b)%n</span>
ZZ MulMod(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b, <span class="Type">const</span> ZZ& n);
<span class="Type">void</span> SqrMod(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n); <span class="Comment">// x = a^2 % n</span>
ZZ SqrMod(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n);
<span class="Type">void</span> InvMod(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n);
ZZ InvMod(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n);
<span class="Comment">// x = a^{-1} mod n (0 <= x < n); error is raised occurs if inverse</span>
<span class="Comment">// not defined</span>
<span class="Comment">// If exceptions are enabled, an object of the following class </span>
<span class="Comment">// is throw by the InvMod routine if the inverse of a mod n is</span>
<span class="Comment">// not defined. The methods get_a() and get_n() give read-only</span>
<span class="Comment">// access to the offending values of a and n.</span>
<span class="Comment">// This also happens for any indirect call to InvMod, via PowerMod,</span>
<span class="Comment">// of via inverse computations in ZZ_p.</span>
<span class="Type">class</span> InvModErrorObject : <span class="Statement">public</span> ArithmeticErrorObject {
<span class="Statement">public</span>:
InvModErrorObject(<span class="Type">const</span> <span class="Type">char</span> *s, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n);
<span class="Type">const</span> ZZ& get_a() <span class="Type">const</span>;
<span class="Type">const</span> ZZ& get_n() <span class="Type">const</span>;
};
<span class="Type">long</span> InvModStatus(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n);
<span class="Comment">// if gcd(a,n) = 1, then return-value = 0, x = a^{-1} mod n;</span>
<span class="Comment">// otherwise, return-value = 1, x = gcd(a, n)</span>
<span class="Type">void</span> PowerMod(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& e, <span class="Type">const</span> ZZ& n);
ZZ PowerMod(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& e, <span class="Type">const</span> ZZ& n);
<span class="Type">void</span> PowerMod(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> e, <span class="Type">const</span> ZZ& n);
ZZ PowerMod(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> e, <span class="Type">const</span> ZZ& n);
<span class="Comment">// x = a^e % n (e may be negative)</span>
<span class="Comment">// PROMOTIONS: AddMod, SubMod, and MulMod (both procedural and functional</span>
<span class="Comment">// forms) support promotions from long to ZZ on (a, b).</span>
<a name="modarith"></a>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Single-precision modular arithmetic</span>
<span class="Comment">These routines implement single-precision modular arithmetic. If n is</span>
<span class="Comment">the modulus, all inputs should be in the range 0..n-1. The number n</span>
<span class="Comment">itself should be in the range 2..NTL_SP_BOUND-1.</span>
<span class="Comment">Most of these routines are, of course, implemented as fast inline</span>
<span class="Comment">functions. No checking is done that inputs are in range.</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">long</span> AddMod(<span class="Type">long</span> a, <span class="Type">long</span> b, <span class="Type">long</span> n); <span class="Comment">// return (a+b)%n</span>
<span class="Type">long</span> SubMod(<span class="Type">long</span> a, <span class="Type">long</span> b, <span class="Type">long</span> n); <span class="Comment">// return (a-b)%n</span>
<span class="Type">long</span> NegateMod(<span class="Type">long</span> a, <span class="Type">long</span> n); <span class="Comment">// return (-a)%n</span>
<span class="Type">long</span> MulMod(<span class="Type">long</span> a, <span class="Type">long</span> b, <span class="Type">long</span> n); <span class="Comment">// return (a*b)%n</span>
<span class="Type">long</span> MulMod(<span class="Type">long</span> a, <span class="Type">long</span> b, <span class="Type">long</span> n, mulmod_t ninv);
<span class="Comment">// return (a*b)%n. </span>
<span class="Comment">//</span>
<span class="Comment">// Usually faster than plain MulMod when n is fixed for many</span>
<span class="Comment">// invocations. The value ninv should be precomputed as </span>
<span class="Comment">// mulmod_t ninv = PrepMulMod(n);</span>
mulmod_t PrepMulMod(<span class="Type">long</span> n);
<span class="Comment">// Prepare auxiliary data for MulMod.</span>
<span class="Type">long</span> MulModPrecon(<span class="Type">long</span> a, <span class="Type">long</span> b, <span class="Type">long</span> n, mulmod_precon_t bninv);
<span class="Comment">// return (a*b)%n. </span>
<span class="Comment">//</span>
<span class="Comment">// Usually much faster than MulMod when both b and n are fixed for </span>
<span class="Comment">// many invocations. The value bninv should be precomputed as</span>
<span class="Comment">// mulmod_precon_t bninv = PrepMulModPrecon(b, n);</span>
<span class="Comment">// or as</span>
<span class="Comment">// mulmod_precon_t bninv = PrepMulModPrecon(b, n, ninv);</span>
<span class="Comment">// where ninv = PrepMulMod(n).</span>
mulmod_precon_t PrepMulModPrecon(<span class="Type">long</span> b, <span class="Type">long</span> n);
mulmod_precon_t PrepMulModPrecon(<span class="Type">long</span> b, <span class="Type">long</span> n, mulmod_t ninv);
<span class="Comment">// Prepare auxiliary data for MulModPrecon.</span>
<span class="Comment">// In the second version, ninv = PrepMulMod(n).</span>
<span class="Type">long</span> InvMod(<span class="Type">long</span> a, <span class="Type">long</span> n);
<span class="Comment">// computes a^{-1} mod n. Error is raised if undefined.</span>
<span class="Type">long</span> InvModStatus(<span class="Type">long</span>& x, <span class="Type">long</span> a, <span class="Type">long</span> n);
<span class="Comment">// if gcd(a,n) = 1, then return-value = 0, x = a^{-1} mod n;</span>
<span class="Comment">// otherwise, return-value = 1, x = gcd(a, n)</span>
<span class="Type">long</span> PowerMod(<span class="Type">long</span> a, <span class="Type">long</span> e, <span class="Type">long</span> n);
<span class="Comment">// computes a^e mod n (e may be negative)</span>
<span class="Comment">// The following are vector versions of the MulMod routines</span>
<span class="Comment">// They each compute x[i] = (a[i] * b)% n i = 0..k-1 </span>
<span class="Type">void</span> VectorMulMod(<span class="Type">long</span> k, <span class="Type">long</span> *x, <span class="Type">const</span> <span class="Type">long</span> *a, <span class="Type">long</span> b, <span class="Type">long</span> n);
<span class="Type">void</span> VectorMulMod(<span class="Type">long</span> k, <span class="Type">long</span> *x, <span class="Type">const</span> <span class="Type">long</span> *a, <span class="Type">long</span> b, <span class="Type">long</span> n,
mulmod_t ninv);
<span class="Comment">// ninv = PrepMulMod(n)</span>
<span class="Type">void</span> VectorMulModPrecon(<span class="Type">long</span> k, <span class="Type">long</span> *x, <span class="Type">const</span> <span class="Type">long</span> *a, <span class="Type">long</span> b, <span class="Type">long</span> n,
mulmod_precon_t bninv);
<span class="Comment">// bninv = MulModPrecon(b, n)</span>
<span class="Comment">// The following is provided for legacy support, but is not generally </span>
<span class="Comment">// recommended:</span>
<span class="Type">long</span> MulDivRem(<span class="Type">long</span>& q, <span class="Type">long</span> a, <span class="Type">long</span> b, <span class="Type">long</span> n, muldivrem_t bninv);
<span class="Comment">// return (a*b)%n, set q = (a*b)/n. </span>
<span class="Comment">// The value bninv should be precomputed as </span>
<span class="Comment">// muldivrem_t bninv = PrepMulDivRem(b, n);</span>
<span class="Comment">// or as</span>
<span class="Comment">// muldivrem_t bninv = PrepMulDivRem(b, n, ninv);</span>
<span class="Comment">// where ninv = PrepMod(n).</span>
muldivrem_t PrepMulDivRem(<span class="Type">long</span> b, <span class="Type">long</span> n);
muldivrem_t PrepMulDivRem(<span class="Type">long</span> b, <span class="Type">long</span> n, mulmod_t ninv);
<span class="Comment">// Prepare auxiliary data for MulDivRem.</span>
<span class="Comment">// In the second version, ninv = PrepMulMod(n).</span>
<span class="Comment">// NOTE: despite the similarity in the interface to MulModPrecon,</span>
<span class="Comment">// this routine is typically implemented in a very different way,</span>
<span class="Comment">// and usually much less efficient.</span>
<span class="Comment">// It was initially designed for specialized, internal use</span>
<span class="Comment">// within NTL, but has been a part of the documented NTL</span>
<span class="Comment">// interface for some time, and remains so even after the</span>
<span class="Comment">// v9.0 upgrade.</span>
<span class="Comment">//</span>
<span class="Comment">// Compatibility notes:</span>
<span class="Comment">//</span>
<span class="Comment">// The types mulmod_t and muldivrem_t were introduced in NTL v9.0, as were the</span>
<span class="Comment">// functions PrepMulMod and PrepMulDivRem. Prior to this, the built-in type</span>
<span class="Comment">// "double" played the role of these types, and the user was expected to</span>
<span class="Comment">// compute PrepMulMod(n) as 1/double(n) and PrepMulDivRem(b, n) as</span>
<span class="Comment">// double(b)/double(n).</span>
<span class="Comment">// </span>
<span class="Comment">// By abstracting these types, NTL is able to exploit a wider variety of</span>
<span class="Comment">// implementation strategies. Some old client code may break, but the compiler</span>
<span class="Comment">// will easily find the code that needs to be updated, and the updates are</span>
<span class="Comment">// quite mechanical (unless the old code implicitly made use of the assumption</span>
<span class="Comment">// that NTL_SP_NBITS <= NTL_DOUBLE_PRECISION-3).</span>
<span class="Comment">//</span>
<span class="Comment">// It is highly recommended that old client codes be updated. However, one may</span>
<span class="Comment">// build NTL with the configuration option NTL_LEGACY_SP_MULMOD=on, which will</span>
<span class="Comment">// cause the interfaces and implementations to revert to their pre-v9.0</span>
<span class="Comment">// definitions. This option will also make the following (obsolete) function</span>
<span class="Comment">// visible:</span>
<span class="Type">long</span> MulMod2(<span class="Type">long</span> a, <span class="Type">long</span> b, <span class="Type">long</span> n, <span class="Type">double</span> bninv);
<span class="Comment">// return (a*b)%n. bninv = ((double) b)/((double) n). This is faster</span>
<span class="Comment">// if both n and b are fixed for many multiplications.</span>
<span class="Comment">// Note: This is OBSOLETE -- use MulModPrecon.</span>
<span class="Comment">// As of v9.2 of NTL, this new interface allows for 60-bit moduli on most</span>
<span class="Comment">// 64-bit machines. The requirement is that a working 128-bit integer type is</span>
<span class="Comment">// available. For current versions of gcc, clang, and icc, this is available</span>
<span class="Comment">// vie the types __int128_t and __uint128_t. If this requirement is met (which</span>
<span class="Comment">// is verified during NTL installation), then a "long long" implementation for</span>
<span class="Comment">// MulMod is used. In versions 9.0 and 9.1 of NTL, a "long double"</span>
<span class="Comment">// implementation was introduced, which utilized the 80-bit extended double</span>
<span class="Comment">// precision hardware on x86 machines. This also allows for 60-bit moduli on</span>
<span class="Comment">// 64-bit machines.</span>
<span class="Comment">// If 128-bit integer types are not available, or if you build NTL with the</span>
<span class="Comment">// NTL_DISABLE_LONGLONG=on flag, NTL will attempt to use the extended double</span>
<span class="Comment">// precision hardware to still allow 60-bit moduli. If that is not possible,</span>
<span class="Comment">// or if you build NTL with the NTL_DISABLE_LONGDOUBLE=on flag, then NTL will</span>
<span class="Comment">// fall back to its "classical" implementation (pre-9.0) that relies on</span>
<span class="Comment">// double-precision arithmetic and imposes a 50-bit limit on moduli. </span>
<span class="Comment">// Note that in on 64-bit machines, either the "long long" or "long double"</span>
<span class="Comment">// implementations could support 62-bit moduli, rather than 60-bit moduli.</span>
<span class="Comment">// However, the restriction to 60-bits speeds up a few things, and so seems</span>
<span class="Comment">// like a good trade off. This is subject to change in the future.</span>
<span class="Comment">// Also note that all of these enhancements introduced since v9.0 are only</span>
<span class="Comment">// available to builds of NTL that use GMP. Builds that don't use GMP will</span>
<span class="Comment">// still be restricted to 50-bit moduli on 64-bit machines. </span>
<span class="Comment">// On machines with 32-bit longs, moduli will be resricted to 30 bits,</span>
<span class="Comment">// regardless on the implementation, which will be based on "long long"</span>
<span class="Comment">// arithmetic (if a 64-bit integer type is available), or on double-precision</span>
<span class="Comment">// floating point (otherwise).</span>
<span class="Comment">// One can detect the new (v9) interface by testing if the macro</span>
<span class="Comment">// NTL_HAVE_MULMOD_T is defined. The following code can be used to make</span>
<span class="Comment">// new-style NTL clients work with either older (pre-9.0) versions of NTL or</span>
<span class="Comment">// newer versions (post-9.0):</span>
<span class="PreProc">#ifndef NTL_HAVE_MULMOD_T</span>
<span class="Type">namespace</span> NTL {
<span class="Type">typedef</span> <span class="Type">double</span> mulmod_t;
<span class="Type">typedef</span> <span class="Type">double</span> muldivrem_t;
<span class="Type">static</span> <span class="Type">inline</span> <span class="Type">double</span> PrepMulMod(<span class="Type">long</span> n)
{ <span class="Statement">return</span> <span class="Type">double</span>(<span class="Constant">1L</span>)/<span class="Type">double</span>(n); }
<span class="Type">static</span> <span class="Type">inline</span> <span class="Type">double</span> PrepMulDivRem(<span class="Type">long</span> b, <span class="Type">long</span> n, <span class="Type">double</span> ninv)
{ <span class="Statement">return</span> <span class="Type">double</span>(b)*ninv; }
<span class="Type">static</span> <span class="Type">inline</span> <span class="Type">double</span> PrepMulDivRem(<span class="Type">long</span> b, <span class="Type">long</span> n)
{ <span class="Statement">return</span> <span class="Type">double</span>(b)/<span class="Type">double</span>(n); }
<span class="Type">static</span> <span class="Type">inline</span> <span class="Type">double</span> PrepMulModPrecon(<span class="Type">long</span> b, <span class="Type">long</span> n)
{ <span class="Statement">return</span> PrepMulModPrecon(b, n, PrepMulMod(n)); }
}
<span class="PreProc">#endif</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Shift Operations</span>
<span class="Comment">LeftShift by n means multiplication by 2^n</span>
<span class="Comment">RightShift by n means division by 2^n, with truncation toward zero</span>
<span class="Comment"> (so the sign is preserved).</span>
<span class="Comment">A negative shift amount reverses the direction of the shift.</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Comment">// operator notation:</span>
ZZ <span class="Statement">operator</span><<(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> n);
ZZ <span class="Statement">operator</span>>>(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> n);
ZZ& <span class="Statement">operator</span><<=(ZZ& x, <span class="Type">long</span> n);
ZZ& <span class="Statement">operator</span>>>=(ZZ& x, <span class="Type">long</span> n);
<span class="Comment">// procedural versions:</span>
<span class="Type">void</span> LeftShift(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> n);
ZZ LeftShift(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> n);
<span class="Type">void</span> RightShift(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> n);
ZZ RightShift(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> n);
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Bits and Bytes</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">long</span> MakeOdd(ZZ& x);
<span class="Comment">// removes factors of 2 from x, returns the number of 2's removed</span>
<span class="Comment">// returns 0 if x == 0</span>
<span class="Type">long</span> NumTwos(<span class="Type">const</span> ZZ& x);
<span class="Comment">// returns max e such that 2^e divides x if x != 0, and returns 0 if x == 0.</span>
<span class="Type">long</span> IsOdd(<span class="Type">const</span> ZZ& a); <span class="Comment">// test if a is odd</span>
<span class="Type">long</span> NumBits(<span class="Type">const</span> ZZ& a);
<span class="Type">long</span> NumBits(<span class="Type">long</span> a);
<span class="Comment">// returns the number of bits in binary represenation of |a|; </span>
<span class="Comment">// NumBits(0) = 0</span>
<span class="Type">long</span> bit(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> k);
<span class="Type">long</span> bit(<span class="Type">long</span> a, <span class="Type">long</span> k);
<span class="Comment">// returns bit k of |a|, position 0 being the low-order bit.</span>
<span class="Comment">// If k < 0 or k >= NumBits(a), returns 0.</span>
<span class="Type">void</span> trunc(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> k);
<span class="Comment">// x = low order k bits of |a|. </span>
<span class="Comment">// If k <= 0, x = 0.</span>
<span class="Comment">// two functional variants:</span>
ZZ trunc_ZZ(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> k);
<span class="Type">long</span> trunc_long(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> k);
<span class="Type">long</span> SetBit(ZZ& x, <span class="Type">long</span> p);
<span class="Comment">// returns original value of p-th bit of |a|, and replaces p-th bit of</span>
<span class="Comment">// a by 1 if it was zero; low order bit is bit 0; error if p < 0;</span>
<span class="Comment">// the sign of x is maintained</span>
<span class="Type">long</span> SwitchBit(ZZ& x, <span class="Type">long</span> p);
<span class="Comment">// returns original value of p-th bit of |a|, and switches the value</span>
<span class="Comment">// of p-th bit of a; low order bit is bit 0; error if p < 0</span>
<span class="Comment">// the sign of x is maintained</span>
<span class="Type">long</span> weight(<span class="Type">const</span> ZZ& a); <span class="Comment">// returns Hamming weight of |a|</span>
<span class="Type">long</span> weight(<span class="Type">long</span> a);
<span class="Comment">// bit-wise Boolean operations, procedural form:</span>
<span class="Type">void</span> bit_and(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// x = |a| AND |b|</span>
<span class="Type">void</span> bit_or(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// x = |a| OR |b|</span>
<span class="Type">void</span> bit_xor(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b); <span class="Comment">// x = |a| XOR |b|</span>
<span class="Comment">// bit-wise Boolean operations, operator notation:</span>
ZZ <span class="Statement">operator</span>&(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
ZZ <span class="Statement">operator</span>|(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
ZZ <span class="Statement">operator</span>^(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& b);
<span class="Comment">// PROMOTIONS: the above bit-wise operations (both procedural </span>
<span class="Comment">// and operator forms) provide promotions from long to ZZ on (a, b).</span>
ZZ& <span class="Statement">operator</span>&=(ZZ& x, <span class="Type">const</span> ZZ& b);
ZZ& <span class="Statement">operator</span>&=(ZZ& x, <span class="Type">long</span> b);
ZZ& <span class="Statement">operator</span>|=(ZZ& x, <span class="Type">const</span> ZZ& b);
ZZ& <span class="Statement">operator</span>|=(ZZ& x, <span class="Type">long</span> b);
ZZ& <span class="Statement">operator</span>^=(ZZ& x, <span class="Type">const</span> ZZ& b);
ZZ& <span class="Statement">operator</span>^=(ZZ& x, <span class="Type">long</span> b);
<span class="Comment">// conversions between byte sequences and ZZ's</span>
<span class="Type">void</span> ZZFromBytes(ZZ& x, <span class="Type">const</span> <span class="Type">unsigned</span> <span class="Type">char</span> *p, <span class="Type">long</span> n);
ZZ ZZFromBytes(<span class="Type">const</span> <span class="Type">unsigned</span> <span class="Type">char</span> *p, <span class="Type">long</span> n);
<span class="Comment">// x = sum(p[i]*256^i, i=0..n-1). </span>
<span class="Comment">// NOTE: in the unusual event that a char is more than 8 bits, </span>
<span class="Comment">// only the low order 8 bits of p[i] are used</span>
<span class="Type">void</span> BytesFromZZ(<span class="Type">unsigned</span> <span class="Type">char</span> *p, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> n);
<span class="Comment">// Computes p[0..n-1] such that abs(a) == sum(p[i]*256^i, i=0..n-1) mod 256^n.</span>
<span class="Type">long</span> NumBytes(<span class="Type">const</span> ZZ& a);
<span class="Type">long</span> NumBytes(<span class="Type">long</span> a);
<span class="Comment">// returns # of base 256 digits needed to represent abs(a).</span>
<span class="Comment">// NumBytes(0) == 0.</span>
<a name="prg"></a>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Pseudo-Random Numbers</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Comment">// Routines for generating pseudo-random numbers.</span>
<span class="Comment">// These routines generate high qualtity, cryptographically strong</span>
<span class="Comment">// pseudo-random numbers. They are implemented so that their behaviour</span>
<span class="Comment">// is completely independent of the underlying hardware and long </span>
<span class="Comment">// integer implementation. Note, however, that other routines </span>
<span class="Comment">// throughout NTL use pseudo-random numbers, and because of this,</span>
<span class="Comment">// the word size of the machine can impact the sequence of numbers</span>
<span class="Comment">// seen by a client program.</span>
<span class="Type">void</span> SetSeed(<span class="Type">const</span> ZZ& s);
<span class="Type">void</span> SetSeed(<span class="Type">const</span> <span class="Type">unsigned</span> <span class="Type">char</span> *data, <span class="Type">long</span> dlen);
<span class="Type">void</span> SetSeed(<span class="Type">const</span> RandomStream& s);
<span class="Comment">// Initializes generator with a "seed".</span>
<span class="Comment">// The first version hashes the binary representation of s to obtain a key for</span>
<span class="Comment">// a low-level RandomStream object (see below).</span>
<span class="Comment">// The second version does the same, hashing the first dlen bytes pointed to by</span>
<span class="Comment">// data to obtain a key for the RandomStream object.</span>
<span class="Comment">// The third version initializes the PRG state directly with the given</span>
<span class="Comment">// RandomStream object.</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">void</span> RandomBnd(ZZ& x, <span class="Type">const</span> ZZ& n);
ZZ RandomBnd(<span class="Type">const</span> ZZ& n);
<span class="Type">void</span> RandomBnd(<span class="Type">long</span>& x, <span class="Type">long</span> n);
<span class="Type">long</span> RandomBnd(<span class="Type">long</span> n);
<span class="Comment">// x = pseudo-random number in the range 0..n-1, or 0 if n <= 0</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">void</span> VectorRandomBnd(<span class="Type">long</span> k, <span class="Type">long</span> *x, <span class="Type">long</span> n);
<span class="Comment">// equivalent to x[i] = RandomBnd(n) for i in [0..k), but faster</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">void</span> VectorRandomWord(<span class="Type">long</span> k, <span class="Type">long</span> *x);
<span class="Comment">// equivalent to x[i] = RandomWord(n) for i in [0..k), but faster</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">void</span> RandomBits(ZZ& x, <span class="Type">long</span> l);
ZZ RandomBits_ZZ(<span class="Type">long</span> l);
<span class="Type">void</span> RandomBits(<span class="Type">long</span>& x, <span class="Type">long</span> l);
<span class="Type">long</span> RandomBits_long(<span class="Type">long</span> l);
<span class="Comment">// x = pseudo-random number in the range 0..2^l-1.</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">void</span> RandomLen(ZZ& x, <span class="Type">long</span> l);
ZZ RandomLen_ZZ(<span class="Type">long</span> l);
<span class="Type">void</span> RandomLen(<span class="Type">long</span>& x, <span class="Type">long</span> l);
<span class="Type">long</span> RandomLen_long(<span class="Type">long</span> l);
<span class="Comment">// x = psuedo-random number with precisely l bits,</span>
<span class="Comment">// or 0 of l <= 0.</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">unsigned</span> <span class="Type">long</span> RandomBits_ulong(<span class="Type">long</span> l);
<span class="Comment">// returns a pseudo-random number in the range 0..2^l-1</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">unsigned</span> <span class="Type">long</span> RandomWord();
<span class="Comment">// returns a word filled with pseudo-random bits.</span>
<span class="Comment">// Equivalent to RandomBits_ulong(NTL_BITS_PER_LONG).</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">class</span> RandomStream {
<span class="Comment">// The low-level pseudo-random generator (PRG).</span>
<span class="Comment">// After initializing it with a key, one can effectively read an unbounded</span>
<span class="Comment">// stream of pseudorandom bytes</span>
<span class="Statement">public</span>:
<span class="Type">explicit</span> RandomStream(<span class="Type">const</span> <span class="Type">unsigned</span> <span class="Type">char</span> *key);
<span class="Comment">// key should point to an array of NTL_PRG_KEYLEN bytes</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">void</span> get(<span class="Type">unsigned</span> <span class="Type">char</span> *res, <span class="Type">long</span> n);
<span class="Comment">// read the next n bytes from the stream and store to location pointed to by</span>
<span class="Comment">// res</span>
<span class="Comment">// EXCEPTIONS: throws a LogicError exception if n is negative</span>
RandomStream(<span class="Type">const</span> RandomStream&);
<span class="Comment">// EXCEPTIONS: strong ES</span>
RandomStream& <span class="Statement">operator</span>=(<span class="Type">const</span> RandomStream&);
<span class="Comment">// EXCEPTIONS: strong ES</span>
};
RandomStream& GetCurrentRandomStream();
<span class="Comment">// get reference to the current PRG state. If SetSeed has not been called, it</span>
<span class="Comment">// is called with a default value (which should be unique to each</span>
<span class="Comment">// process/thread). NOTE: this is a reference to a thread-local object, so</span>
<span class="Comment">// different threads will use different PRG's, and by default, each will be</span>
<span class="Comment">// initialized with a unique seed.</span>
<span class="Comment">// NOTE: using this reference, you can copy the current PRG state or assign a</span>
<span class="Comment">// different value to it; however, see the helper class RandomStreamPush below,</span>
<span class="Comment">// which may be more convenient.</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
<span class="Type">class</span> RandomStreamPush {
<span class="Comment">// RAII for saving/restoring current PRG state</span>
<span class="Statement">public</span>:
RandomStreamPush(); <span class="Comment">// save a copy of the current PRG state</span>
<span class="Comment">// EXCEPTIONS: strong ES</span>
~RandomStreamPush(); <span class="Comment">// restore the saved copy of the PRG state</span>
<span class="Statement">private</span>:
RandomStreamPush(<span class="Type">const</span> RandomStreamPush&); <span class="Comment">// disable</span>
<span class="Type">void</span> <span class="Statement">operator</span>=(<span class="Type">const</span> RandomStreamPush&); <span class="Comment">// disable</span>
};
<span class="Type">void</span> DeriveKey(<span class="Type">unsigned</span> <span class="Type">char</span> *key, <span class="Type">long</span> klen,
<span class="Type">const</span> <span class="Type">unsigned</span> <span class="Type">char</span> *data, <span class="Type">long</span> dlen);
<span class="Comment">// utility routine to derive from the byte string (data, dlen) a byte string</span>
<span class="Comment">// (key, klen). Heuristically, if (data, dlen) has high entropy, then (key,</span>
<span class="Comment">// klen) should be pseudorandom. This routine is also used internally to</span>
<span class="Comment">// derive PRG keys.</span>
<span class="Comment">// EXCEPTIONS: throws LogicError exception if klen < 0 or hlen < 0</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Incremental Chinese Remaindering</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">long</span> CRT(ZZ& a, ZZ& p, <span class="Type">const</span> ZZ& A, <span class="Type">const</span> ZZ& P);
<span class="Type">long</span> CRT(ZZ& a, ZZ& p, <span class="Type">long</span> A, <span class="Type">long</span> P);
<span class="Comment">// 0 <= A < P, (p, P) = 1; computes a' such that a' = a mod p, </span>
<span class="Comment">// a' = A mod P, and -p*P/2 < a' <= p*P/2; sets a := a', p := p*P, and</span>
<span class="Comment">// returns 1 if a's value has changed, otherwise 0</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Rational Reconstruction</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">long</span> ReconstructRational(ZZ& a, ZZ& b, <span class="Type">const</span> ZZ& x, <span class="Type">const</span> ZZ& m,
<span class="Type">const</span> ZZ& a_bound, <span class="Type">const</span> ZZ& b_bound);
<span class="Comment">// 0 <= x < m, m > 2 * a_bound * b_bound,</span>
<span class="Comment">// a_bound >= 0, b_bound > 0</span>
<span class="Comment">// This routine either returns 0, leaving a and b unchanged, </span>
<span class="Comment">// or returns 1 and sets a and b so that</span>
<span class="Comment">// (1) a = b x (mod m),</span>
<span class="Comment">// (2) |a| <= a_bound, 0 < b <= b_bound, and</span>
<span class="Comment">// (3) gcd(m, b) = gcd(a, b).</span>
<span class="Comment">// If there exist a, b satisfying (1), (2), and </span>
<span class="Comment">// (3') gcd(m, b) = 1,</span>
<span class="Comment">// then a, b are uniquely determined if we impose the additional</span>
<span class="Comment">// condition that gcd(a, b) = 1; moreover, if such a, b exist,</span>
<span class="Comment">// then these values are returned by the routine.</span>
<span class="Comment">// Unless the calling routine can *a priori* guarantee the existence</span>
<span class="Comment">// of a, b satisfying (1), (2), and (3'),</span>
<span class="Comment">// then to ensure correctness, the calling routine should check</span>
<span class="Comment">// that gcd(m, b) = 1, or equivalently, gcd(a, b) = 1.</span>
<span class="Comment">// This is implemented using a variant of Lehmer's extended</span>
<span class="Comment">// Euclidean algorithm.</span>
<span class="Comment">// Literature: see G. Collins and M. Encarnacion, J. Symb. Comp. 20:287-297, </span>
<span class="Comment">// 1995; P. Wang, M. Guy, and J. Davenport, SIGSAM Bulletin 16:2-3, 1982. </span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Primality Testing </span>
<span class="Comment"> and Prime Number Generation</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">void</span> GenPrime(ZZ& n, <span class="Type">long</span> l, <span class="Type">long</span> err = <span class="Constant">80</span>);
ZZ GenPrime_ZZ(<span class="Type">long</span> l, <span class="Type">long</span> err = <span class="Constant">80</span>);
<span class="Type">long</span> GenPrime_long(<span class="Type">long</span> l, <span class="Type">long</span> err = <span class="Constant">80</span>);
<span class="Comment">// GenPrime generates a random prime n of length l so that the</span>
<span class="Comment">// probability that the resulting n is composite is bounded by 2^(-err).</span>
<span class="Comment">// This calls the routine RandomPrime below, and uses results of </span>
<span class="Comment">// Damgard, Landrock, Pomerance to "optimize" </span>
<span class="Comment">// the number of Miller-Rabin trials at the end.</span>
<span class="Comment">// Note that the prime generated by GenPrime and RandomPrime </span>
<span class="Comment">// is not entirely platform independent. The behavior of the</span>
<span class="Comment">// algorithm can depend on the size parameters, such as NTL_SP_NBITS </span>
<span class="Comment">// NTL_ZZ_NBITS, and NTL_BITS_PER_LONG. However, on a given platform</span>
<span class="Comment">// you will always get the same prime if you run the algorithm</span>
<span class="Comment">// with the same RandomStream. </span>
<span class="Comment">// Note that RandomPrime and GenPrime are thread boosted.</span>
<span class="Comment">// Nevertheless, their behavior is independent of the number of</span>
<span class="Comment">// available threads and any indeterminacy arising from </span>
<span class="Comment">// concurrent computation.</span>
<span class="Type">void</span> GenGermainPrime(ZZ& n, <span class="Type">long</span> l, <span class="Type">long</span> err = <span class="Constant">80</span>);
ZZ GenGermainPrime_ZZ(<span class="Type">long</span> l, <span class="Type">long</span> err = <span class="Constant">80</span>);
<span class="Type">long</span> GenGermainPrime_long(<span class="Type">long</span> l, <span class="Type">long</span> err = <span class="Constant">80</span>);
<span class="Comment">// A (Sophie) Germain prime is a prime p such that p' = 2*p+1 is also a prime.</span>
<span class="Comment">// Such primes are useful for cryptographic applications...cryptographers</span>
<span class="Comment">// sometimes call p' a "strong" or "safe" prime.</span>
<span class="Comment">// GenGermainPrime generates a random Germain prime n of length l</span>
<span class="Comment">// so that the probability that either n or 2*n+1 is not a prime</span>
<span class="Comment">// is bounded by 2^(-err).</span>
<span class="Comment">// Note that GenGermainPrime is thread boosted.</span>
<span class="Comment">// Nevertheless, its behavior is independent of the number of</span>
<span class="Comment">// available threads and any indeterminacy arising from </span>
<span class="Comment">// concurrent computation.</span>
<span class="Type">long</span> ProbPrime(<span class="Type">const</span> ZZ& n, <span class="Type">long</span> NumTrials = <span class="Constant">10</span>);
<span class="Type">long</span> ProbPrime(<span class="Type">long</span> n, <span class="Type">long</span> NumTrials = <span class="Constant">10</span>);
<span class="Comment">// performs trial division, followed by one Miller-Rabin test</span>
<span class="Comment">// to the base 2, followed by NumTrials Miller-witness tests </span>
<span class="Comment">// with random bases.</span>
<span class="Type">void</span> RandomPrime(ZZ& n, <span class="Type">long</span> l, <span class="Type">long</span> NumTrials=<span class="Constant">10</span>);
ZZ RandomPrime_ZZ(<span class="Type">long</span> l, <span class="Type">long</span> NumTrials=<span class="Constant">10</span>);
<span class="Type">long</span> RandomPrime_long(<span class="Type">long</span> l, <span class="Type">long</span> NumTrials=<span class="Constant">10</span>);
<span class="Comment">// n = random l-bit prime. Uses ProbPrime with NumTrials.</span>
<span class="Type">void</span> NextPrime(ZZ& n, <span class="Type">const</span> ZZ& m, <span class="Type">long</span> NumTrials=<span class="Constant">10</span>);
ZZ NextPrime(<span class="Type">const</span> ZZ& m, <span class="Type">long</span> NumTrials=<span class="Constant">10</span>);
<span class="Comment">// n = smallest prime >= m. Uses ProbPrime with NumTrials.</span>
<span class="Type">long</span> NextPrime(<span class="Type">long</span> m, <span class="Type">long</span> NumTrials=<span class="Constant">10</span>);
<span class="Comment">// Single precision version of the above.</span>
<span class="Comment">// Result will always be bounded by NTL_ZZ_SP_BOUND, and an</span>
<span class="Comment">// error is raised if this cannot be satisfied.</span>
<span class="Type">long</span> MillerWitness(<span class="Type">const</span> ZZ& n, <span class="Type">const</span> ZZ& w);
<span class="Comment">// Tests if w is a witness to compositeness a la Miller. Assumption: n is</span>
<span class="Comment">// odd and positive, 0 <= w < n.</span>
<span class="Comment">// Return value of 1 implies n is composite.</span>
<span class="Comment">// Return value of 0 indicates n might be prime.</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Exponentiation</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">void</span> power(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">long</span> e); <span class="Comment">// x = a^e (e >= 0)</span>
ZZ power(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> e);
<span class="Type">void</span> power(ZZ& x, <span class="Type">long</span> a, <span class="Type">long</span> e);
<span class="Comment">// two functional variants:</span>
ZZ power_ZZ(<span class="Type">long</span> a, <span class="Type">long</span> e);
<span class="Type">long</span> power_long(<span class="Type">long</span> a, <span class="Type">long</span> e);
<span class="Type">void</span> power2(ZZ& x, <span class="Type">long</span> e); <span class="Comment">// x = 2^e (e >= 0)</span>
ZZ power2_ZZ(<span class="Type">long</span> e);
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Square Roots</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">void</span> SqrRoot(ZZ& x, <span class="Type">const</span> ZZ& a); <span class="Comment">// x = floor(a^{1/2}) (a >= 0)</span>
ZZ SqrRoot(<span class="Type">const</span> ZZ& a);
<span class="Type">long</span> SqrRoot(<span class="Type">long</span> a);
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Jacobi symbol and modular square roots</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">long</span> Jacobi(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n);
<span class="Comment">// compute Jacobi symbol of a and n; assumes 0 <= a < n, n odd</span>
<span class="Type">void</span> SqrRootMod(ZZ& x, <span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n);
ZZ SqrRootMod(<span class="Type">const</span> ZZ& a, <span class="Type">const</span> ZZ& n);
<span class="Comment">// computes square root of a mod n; assumes n is an odd prime, and</span>
<span class="Comment">// that a is a square mod n, with 0 <= a < n.</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Input/Output</span>
<span class="Comment">I/O Format:</span>
<span class="Comment">Numbers are written in base 10, with an optional minus sign.</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
istream& <span class="Statement">operator</span>>>(istream& s, ZZ& x);
ostream& <span class="Statement">operator</span><<(ostream& s, <span class="Type">const</span> ZZ& a);
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Miscellany</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Comment">// The following macros are defined:</span>
<span class="PreProc">#define NTL_ZZ_NBITS (...) </span><span class="Comment">// number of bits in a limb;</span>
<span class="Comment">// a ZZ is represented as a sequence of limbs.</span>
<span class="PreProc">#define NTL_SP_NBITS (...) </span><span class="Comment">// max number of bits in a "single-precision" number</span>
<span class="PreProc">#define NTL_WSP_NBITS (...) </span><span class="Comment">// max number of bits in a "wide single-precision"</span>
<span class="Comment">// number</span>
<span class="Comment">// The following relations hold:</span>
<span class="Comment">// 30 <= NTL_SP_NBITS <= NTL_WSP_NBITS </span>
<span class="Comment">// <= min(NTL_ZZ_NBITS, NTL_BITS_PER_LONG-2)</span>
<span class="Comment">// Note that NTL_ZZ_NBITS may be less than, equal to, or greater than</span>
<span class="Comment">// NTL_BITS_PER_LONG -- no particular relationship should be assumed to hold.</span>
<span class="Comment">// In particular, expressions like (1L << NTL_ZZ_BITS) might overflow.</span>
<span class="Comment">//</span>
<span class="Comment">// "single-precision" numbers are meant to be used in conjunction with the</span>
<span class="Comment">// single-precision modular arithmetic routines.</span>
<span class="Comment">//</span>
<span class="Comment">// "wide single-precision" numbers are meant to be used in conjunction</span>
<span class="Comment">// with the ZZ arithmetic routines for optimal efficiency.</span>
<span class="Comment">// The following auxiliary macros are also defined</span>
<span class="PreProc">#define NTL_FRADIX (...) </span><span class="Comment">// double-precision value of 2^NTL_ZZ_NBITS</span>
<span class="PreProc">#define NTL_SP_BOUND (</span><span class="Constant">1L</span><span class="PreProc"> << NTL_SP_NBITS)</span>
<span class="PreProc">#define NTL_WSP_BOUND (</span><span class="Constant">1L</span><span class="PreProc"> << NTL_WSP_NBITS)</span>
<span class="Comment">// Backward compatibility notes:</span>
<span class="Comment">//</span>
<span class="Comment">// Prior to version 5.0, the macro NTL_NBITS was defined,</span>
<span class="Comment">// along with the macro NTL_RADIX defined to be (1L << NTL_NBITS).</span>
<span class="Comment">// While these macros are still available when using NTL's traditional </span>
<span class="Comment">// long integer package (i.e., when NTL_GMP_LIP is not set), </span>
<span class="Comment">// they are not available when using the GMP as the primary long integer </span>
<span class="Comment">// package (i.e., when NTL_GMP_LIP is set).</span>
<span class="Comment">// Furthermore, when writing portable programs, one should avoid these macros.</span>
<span class="Comment">// Note that when using traditional long integer arithmetic, we have</span>
<span class="Comment">// NTL_ZZ_NBITS = NTL_SP_NBITS = NTL_WSP_NBITS = NTL_NBITS.</span>
<span class="Comment">//</span>
<span class="Comment">// Prior to version 9.0, one could also assume that </span>
<span class="Comment">// NTL_SP_NBITS <= NTL_DOUBLE_PRECISION-3;</span>
<span class="Comment">// however, this is no longer the case (unless NTL is build with he NTL_LEGACY_SP_MULMOD</span>
<span class="Comment">// flag turned on).</span>
<span class="Comment">// Here are some additional functions.</span>
<span class="Type">void</span> clear(ZZ& x); <span class="Comment">// x = 0</span>
<span class="Type">void</span> set(ZZ& x); <span class="Comment">// x = 1</span>
<span class="Type">void</span> swap(ZZ& x, ZZ& y);
<span class="Comment">// swap x and y (done by "pointer swapping", if possible).</span>
<span class="Type">double</span> log(<span class="Type">const</span> ZZ& a);
<span class="Comment">// returns double precision approximation to log(a)</span>
<span class="Type">long</span> NextPowerOfTwo(<span class="Type">long</span> m);
<span class="Comment">// returns least nonnegative k such that 2^k >= m</span>
<span class="Type">long</span> ZZ::size() <span class="Type">const</span>;
<span class="Comment">// a.size() returns the number of limbs of |a|; the</span>
<span class="Comment">// size of 0 is 0.</span>
<span class="Type">void</span> ZZ::SetSize(<span class="Type">long</span> k)
<span class="Comment">// a.SetSize(k) does not change the value of a, but simply pre-allocates</span>
<span class="Comment">// space for k limbs.</span>
<span class="Type">long</span> ZZ::SinglePrecision() <span class="Type">const</span>;
<span class="Comment">// a.SinglePrecision() is a predicate that tests if abs(a) < NTL_SP_BOUND</span>
<span class="Type">long</span> ZZ::WideSinglePrecision() <span class="Type">const</span>;
<span class="Comment">// a.WideSinglePrecision() is a predicate that tests if abs(a) < NTL_WSP_BOUND</span>
<span class="Type">long</span> digit(<span class="Type">const</span> ZZ& a, <span class="Type">long</span> k);
<span class="Comment">// returns k-th limb of |a|, position 0 being the low-order</span>
<span class="Comment">// limb.</span>
<span class="Comment">// OBSOLETE: this routine is only available when using NTL's traditional</span>
<span class="Comment">// long integer arithmetic, and should not be used in programs</span>
<span class="Comment">// that are meant to be portable. You should instead use the </span>
<span class="Comment">// routine ZZ_limbs_get, defined in ZZ_limbs.h.</span>
<span class="Type">void</span> ZZ::kill();
<span class="Comment">// a.kill() sets a to zero and frees the space held by a.</span>
<span class="Type">void</span> ZZ::swap(ZZ& x);
<span class="Comment">// swap method (done by "pointer swapping" if possible)</span>
ZZ::ZZ(INIT_SIZE_TYPE, <span class="Type">long</span> k);
<span class="Comment">// ZZ(INIT_SIZE, k) initializes to 0, but space is pre-allocated so</span>
<span class="Comment">// that numbers x with x.size() <= k can be stored without</span>
<span class="Comment">// re-allocation.</span>
<span class="Type">static</span> <span class="Type">const</span> ZZ& ZZ::zero();
<span class="Comment">// ZZ::zero() yields a read-only reference to zero, if you need it.</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Small Prime Generation</span>
<span class="Comment">primes are generated in sequence, starting at 2, and up to a maximum</span>
<span class="Comment">that is no more than min(NTL_SP_BOUND, 2^30).</span>
<span class="Comment">Example: print the primes up to 1000</span>
<span class="Comment">#include <NTL/ZZ.h></span>
<span class="Comment">main()</span>
<span class="Comment">{</span>
<span class="Comment"> PrimeSeq s;</span>
<span class="Comment"> long p;</span>
<span class="Comment"> p = s.next();</span>
<span class="Comment"> while (p <= 1000) {</span>
<span class="Comment"> cout << p << "\n";</span>
<span class="Comment"> p = s.next();</span>
<span class="Comment"> }</span>
<span class="Comment">}</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">class</span> PrimeSeq {
<span class="Statement">public</span>:
PrimeSeq();
~PrimeSeq();
<span class="Type">long</span> next();
<span class="Comment">// returns next prime in the sequence. returns 0 if list of small</span>
<span class="Comment">// primes is exhausted.</span>
<span class="Type">void</span> reset(<span class="Type">long</span> b);
<span class="Comment">// resets generator so that the next prime in the sequence is the</span>
<span class="Comment">// smallest prime >= b.</span>
<span class="Statement">private</span>:
PrimeSeq(<span class="Type">const</span> PrimeSeq&); <span class="Comment">// disabled</span>
<span class="Type">void</span> <span class="Statement">operator</span>=(<span class="Type">const</span> PrimeSeq&); <span class="Comment">// disabled</span>
};
</pre>
</body>
</html>
<!-- vim: set foldmethod=manual : -->
