<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>/Volumes/unix-files/u/ntl-new/ntl-9.9.0dev/doc/lzz_p.cpp.html</title>
<meta name="Generator" content="Vim/7.1">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#ffffff" text="#000000"><font face="monospace">
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i>MODULE: zz_p</i></font><br>
<br>
<font color="#0000ed"><i>SUMMARY:</i></font><br>
<br>
<font color="#0000ed"><i>The class zz_p is used to represent integers mod p, where 1 <= p <</i></font><br>
<font color="#0000ed"><i>NTL_SP_BOUND. Note that NTL_SP_BOUND is usually 2^30 on 32-bit machines and</i></font><br>
<font color="#0000ed"><i>2^50 on 64-bit machines.</i></font><br>
<br>
<font color="#0000ed"><i>The modulus p may be any positive integer, not necessarily prime.</i></font><br>
<br>
<font color="#0000ed"><i>Objects of the class zz_p are represented as a long in the range 0..p-1.</i></font><br>
<br>
<font color="#0000ed"><i>An executing program maintains a "current modulus", which is set to p using</i></font><br>
<font color="#0000ed"><i>zz_p::init(p). The current modulus *must* be initialized before any operations</i></font><br>
<font color="#0000ed"><i>on zz_p's are performed. The modulus may be changed, and a mechanism is provided</i></font><br>
<font color="#0000ed"><i>for saving and restoring a modulus (see classes zz_pPush and zz_pContext below).</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/ZZ.h></font><br>
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/FFT.h></font><br>
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/SmartPtr.h></font><br>
<br>
<br>
<font color="#008b00"><b>class</b></font> zz_p {<br>
<font color="#b02f60"><b>public</b></font>:<br>
<br>
zz_p(); <font color="#0000ed"><i>// initial value 0</i></font><br>
<br>
zz_p(<font color="#008b00"><b>const</b></font> zz_p& a); <font color="#0000ed"><i>// copy constructor</i></font><br>
<font color="#008b00"><b>explicit</b></font> zz_p(<font color="#008b00"><b>long</b></font> a); <font color="#0000ed"><i>// promotion constructor</i></font><br>
<br>
zz_p& <font color="#b02f60"><b>operator</b></font>=(<font color="#008b00"><b>const</b></font> zz_p& a); <font color="#0000ed"><i>// assignment</i></font><br>
zz_p& <font color="#b02f60"><b>operator</b></font>=(<font color="#008b00"><b>long</b></font> a); <font color="#0000ed"><i>// assignment</i></font><br>
<br>
<font color="#008b00"><b>static</b></font> <font color="#008b00"><b>void</b></font> init(<font color="#008b00"><b>long</b></font> p); <br>
<font color="#0000ed"><i>// set the modulus to p, where p > 1. This must be called before any</i></font><br>
<font color="#0000ed"><i>// zz_p constructors are invoked.</i></font><br>
<font color="#0000ed"><i>// The number p must have at most NTL_SP_NBITS bits.</i></font><br>
<br>
<font color="#008b00"><b>static</b></font> <font color="#008b00"><b>long</b></font> modulus();<br>
<font color="#0000ed"><i>// zz_p::modulus() yields read-only reference to the current</i></font><br>
<font color="#0000ed"><i>// modulus</i></font><br>
<br>
<br>
<font color="#0000ed"><i>// typedefs to aid in generic programming</i></font><br>
<font color="#008b00"><b>typedef</b></font> <font color="#008b00"><b>long</b></font> rep_type;<br>
<font color="#008b00"><b>typedef</b></font> zz_pContext context_type;<br>
<font color="#008b00"><b>typedef</b></font> zz_pBak bak_type;<br>
<font color="#008b00"><b>typedef</b></font> zz_pPush push_type;<br>
<font color="#008b00"><b>typedef</b></font> zz_pX poly_type;<br>
<br>
};<br>
<br>
<br>
<font color="#008b00"><b>long</b></font> rep(zz_p a); <font color="#0000ed"><i>// read-only access to representation of a</i></font><br>
<br>
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Comparison</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<br>
<font color="#008b00"><b>long</b></font> <font color="#b02f60"><b>operator</b></font>==(zz_p a, zz_p b);<br>
<font color="#008b00"><b>long</b></font> <font color="#b02f60"><b>operator</b></font>!=(zz_p a, zz_p b);<br>
<br>
<font color="#008b00"><b>long</b></font> IsZero(zz_p a); <font color="#0000ed"><i>// test for 0</i></font><br>
<font color="#008b00"><b>long</b></font> IsOne(zz_p a); <font color="#0000ed"><i>// test for 1</i></font><br>
<br>
<font color="#0000ed"><i>// PROMOTIONS: operators ==, != promote long to zz_p on (a, b).</i></font><br>
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Addition </i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<font color="#0000ed"><i>// operator notation:</i></font><br>
<br>
zz_p <font color="#b02f60"><b>operator</b></font>+(zz_p a, zz_p b);<br>
zz_p <font color="#b02f60"><b>operator</b></font>-(zz_p a, zz_p b);<br>
<br>
zz_p <font color="#b02f60"><b>operator</b></font>-(zz_p a); <font color="#0000ed"><i>// unary -</i></font><br>
<br>
zz_p& <font color="#b02f60"><b>operator</b></font>+=(zz_p& x, zz_p a);<br>
zz_p& <font color="#b02f60"><b>operator</b></font>+=(zz_p& x, <font color="#008b00"><b>long</b></font> a);<br>
<br>
zz_p& <font color="#b02f60"><b>operator</b></font>-=(zz_p& x, zz_p a);<br>
zz_p& <font color="#b02f60"><b>operator</b></font>-=(zz_p& x, <font color="#008b00"><b>long</b></font> a);<br>
<br>
zz_p& <font color="#b02f60"><b>operator</b></font>++(zz_p& x); <font color="#0000ed"><i>// prefix</i></font><br>
<font color="#008b00"><b>void</b></font> <font color="#b02f60"><b>operator</b></font>++(zz_p& x, <font color="#008b00"><b>int</b></font>); <font color="#0000ed"><i>// postfix</i></font><br>
<br>
zz_p& <font color="#b02f60"><b>operator</b></font>--(zz_p& x); <font color="#0000ed"><i>// prefix</i></font><br>
<font color="#008b00"><b>void</b></font> <font color="#b02f60"><b>operator</b></font>--(zz_p& x, <font color="#008b00"><b>int</b></font>); <font color="#0000ed"><i>// postfix</i></font><br>
<br>
<font color="#0000ed"><i>// procedural versions:</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> add(zz_p& x, zz_p a, zz_p b); <font color="#0000ed"><i>// x = a + b</i></font><br>
<font color="#008b00"><b>void</b></font> sub(zz_p& x, zz_p a, zz_p b); <font color="#0000ed"><i>// x = a - b </i></font><br>
<font color="#008b00"><b>void</b></font> negate(zz_p& x, zz_p a); <font color="#0000ed"><i>// x = -a</i></font><br>
<br>
<font color="#0000ed"><i>// PROMOTIONS: binary +, -, and procedures add, sub promote</i></font><br>
<font color="#0000ed"><i>// from long to zz_p on (a, b).</i></font><br>
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Multiplication </i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<font color="#0000ed"><i>// operator notation:</i></font><br>
<br>
zz_p <font color="#b02f60"><b>operator</b></font>*(zz_p a, zz_p b);<br>
<br>
zz_p& <font color="#b02f60"><b>operator</b></font>*=(zz_p& x, zz_p a);<br>
zz_p& <font color="#b02f60"><b>operator</b></font>*=(zz_p& x, <font color="#008b00"><b>long</b></font> a);<br>
<br>
<font color="#0000ed"><i>// procedural versions:</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> mul(zz_p& x, zz_p a, zz_p b); <font color="#0000ed"><i>// x = a * b</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> sqr(zz_p& x, zz_p a); <font color="#0000ed"><i>// x = a^2</i></font><br>
zz_p sqr(zz_p a); <br>
<br>
<font color="#0000ed"><i>// PROMOTIONS: operator * and procedure mul promote from long to zz_p</i></font><br>
<font color="#0000ed"><i>// on (a, b).</i></font><br>
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Division</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<font color="#b02f60"><b>operator</b></font> notation:<br>
<br>
zz_p <font color="#b02f60"><b>operator</b></font>/(z_p a, zz_p b);<br>
<br>
zz_p& <font color="#b02f60"><b>operator</b></font>/=(zz_p& x, zz_p a);<br>
zz_p& <font color="#b02f60"><b>operator</b></font>/=(zz_p& x, <font color="#008b00"><b>long</b></font> a);<br>
<br>
procedural versions:<br>
<br>
<font color="#008b00"><b>void</b></font> div(zz_p& x, zz_p a, zz_p b);<br>
<font color="#0000ed"><i>// x = a/b</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> inv(zz_p& x, zz_p a);<br>
zz_p inv(zz_p a);<br>
<font color="#0000ed"><i>// x = 1/a</i></font><br>
<br>
<font color="#0000ed"><i>// PROMOTIONS: operator / and procedure div promote from long to zz_p</i></font><br>
<font color="#0000ed"><i>// on (a, b).</i></font><br>
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Exponentiation</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> power(zz_p& x, zz_p a, <font color="#008b00"><b>long</b></font> e); <font color="#0000ed"><i>// x = a^e (e may be negative)</i></font><br>
zz_p power(zz_p a, <font color="#008b00"><b>long</b></font> e); <br>
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Random Elements</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> random(zz_p& x);<br>
zz_p random_zz_p();<br>
<font color="#0000ed"><i>// x = random element in zz_p. Uses RandomBnd from ZZ.</i></font><br>
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Input/Output</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<br>
ostream& <font color="#b02f60"><b>operator</b></font><<(ostream& s, zz_p a);<br>
<br>
istream& <font color="#b02f60"><b>operator</b></font>>>(istream& s, zz_p& x);<br>
<font color="#0000ed"><i>// a ZZ is read and reduced mod p</i></font><br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Modulus Switching </i></font><br>
<br>
<font color="#0000ed"><i>A class zz_pPush is provided for "backing up" the current modulus</i></font><br>
<font color="#0000ed"><i>and installing a new one.</i></font><br>
<br>
<font color="#0000ed"><i>Here is what you do to save the current modulus, temporarily</i></font><br>
<font color="#0000ed"><i>set it to p, and automatically restore it:</i></font><br>
<br>
<font color="#0000ed"><i> { </i></font><br>
<font color="#0000ed"><i> zz_pPush push(p); </i></font><br>
<br>
<font color="#0000ed"><i> ...</i></font><br>
<br>
<font color="#0000ed"><i> }</i></font><br>
<br>
<font color="#0000ed"><i>The constructor for push will save the current modulus, and install p as the</i></font><br>
<font color="#0000ed"><i>current modulus. The destructor for push will restore the old modulus when the</i></font><br>
<font color="#0000ed"><i>scope enclosing it exits. This is the so-called RAII (resource acquisition is</i></font><br>
<font color="#0000ed"><i>initialization) paradigm.</i></font><br>
<br>
<font color="#0000ed"><i>You could also do the following:</i></font><br>
<br>
<font color="#0000ed"><i> {</i></font><br>
<font color="#0000ed"><i> zz_pPush push; // just backup current modulus</i></font><br>
<br>
<font color="#0000ed"><i> ...</i></font><br>
<br>
<font color="#0000ed"><i> zz_p::init(p1); // install p1 </i></font><br>
<br>
<font color="#0000ed"><i> ...</i></font><br>
<br>
<font color="#0000ed"><i> zz_p::init(p2); // install p2</i></font><br>
<br>
<font color="#0000ed"><i> // reinstall original modulus as close of scope</i></font><br>
<font color="#0000ed"><i> }</i></font><br>
<br>
<font color="#0000ed"><i> </i></font><br>
<font color="#0000ed"><i>The zz_pPush interface is good for implementing simple stack-like</i></font><br>
<font color="#0000ed"><i>modulus "context switching". For more general context switching,</i></font><br>
<font color="#0000ed"><i>see zz_pContext below. There is also an older zz_pBak class</i></font><br>
<font color="#0000ed"><i>that may also be useful.</i></font><br>
<br>
<font color="#0000ed"><i>..........................................................................</i></font><br>
<br>
<font color="#0000ed"><i>It is critical that zz_p objects created under one zz_p modulus are not used in</i></font><br>
<font color="#0000ed"><i>any non-trivial way "out of context", i.e., under a different (or undefined)</i></font><br>
<font color="#0000ed"><i>zz_p modulus. However, for ease-of-use, some operations may be safely</i></font><br>
<font color="#0000ed"><i>performed out of context. These safe operations include: the default and copy</i></font><br>
<font color="#0000ed"><i>constructor, the destructor, and the assignment operator. In addition is is</i></font><br>
<font color="#0000ed"><i>generally safe to read any zz_p object out of context (i.e., printing it out, or</i></font><br>
<font color="#0000ed"><i>fetching its underlying representive using the rep() function).</i></font><br>
<br>
<font color="#0000ed"><i>Any unsafe uses out of context are not in general checked, and may </i></font><br>
<font color="#0000ed"><i>lead to unpredictable behavior.</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<br>
<font color="#0000ed"><i>// A convenient interface for common cases:</i></font><br>
<br>
<font color="#008b00"><b>class</b></font> zz_pPush {<br>
<font color="#b02f60"><b>public</b></font>:<br>
<br>
zz_pPush(); <font color="#0000ed"><i>// just backup current modulus</i></font><br>
<br>
<font color="#008b00"><b>explicit</b></font> zz_pPush(<font color="#008b00"><b>long</b></font> p, <font color="#008b00"><b>long</b></font> maxroot=NTL_FFTMaxRoot);<br>
zz_pPush(INIT_FFT_TYPE, <font color="#008b00"><b>long</b></font> index); <br>
zz_pPush(INIT_USER_FFT_TYPE, <font color="#008b00"><b>long</b></font> p);<br>
<font color="#008b00"><b>explicit</b></font> zz_pPush(<font color="#008b00"><b>const</b></font> zz_pContext& context); <br>
<font color="#0000ed"><i>// backup current modulus and install the given one</i></font><br>
<font color="#0000ed"><i>// see documentation for zz_p::init for more details</i></font><br>
<br>
<font color="#b02f60"><b>private</b></font>:<br>
zz_pPush(<font color="#008b00"><b>const</b></font> zz_pPush&); <font color="#0000ed"><i>// disabled</i></font><br>
<font color="#008b00"><b>void</b></font> <font color="#b02f60"><b>operator</b></font>=(<font color="#008b00"><b>const</b></font> zz_pPush&); <font color="#0000ed"><i>// disabled</i></font><br>
<br>
};<br>
<br>
<br>
<br>
<font color="#0000ed"><i>// more general context switching:</i></font><br>
<font color="#0000ed"><i>// A zz_pContext object has a modulus q (possibly "null")</i></font><br>
<br>
<font color="#008b00"><b>class</b></font> zz_pContext {<br>
<br>
<br>
<font color="#b02f60"><b>public</b></font>:<br>
<br>
zz_pContext(); <font color="#0000ed"><i>// q = "null"</i></font><br>
<br>
<font color="#008b00"><b>explicit</b></font> zz_pContext(<font color="#008b00"><b>long</b></font> p); <br>
zz_pContext(INIT_FFT_TYPE, <font color="#008b00"><b>long</b></font> index); <br>
zz_pContext(INIT_USER_FFT_TYPE, <font color="#008b00"><b>long</b></font> p);<br>
<font color="#0000ed"><i>// q = the given modulus</i></font><br>
<font color="#0000ed"><i>// see documentation for zz_p::init for more details</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> save(); <font color="#0000ed"><i>// q = CurrentModulus</i></font><br>
<font color="#008b00"><b>void</b></font> restore() <font color="#008b00"><b>const</b></font>; <font color="#0000ed"><i>// CurrentModulus = q</i></font><br>
<br>
zz_pContext(<font color="#008b00"><b>const</b></font> zz_pContext&); <font color="#0000ed"><i>// copy</i></font><br>
zz_pContext& <font color="#b02f60"><b>operator</b></font>=(<font color="#008b00"><b>const</b></font> zz_pContext&); <font color="#0000ed"><i>// assignment</i></font><br>
~zz_pContext(); <font color="#0000ed"><i>// destructor</i></font><br>
<br>
<br>
};<br>
<br>
<br>
/ An older interface:<br>
<font color="#0000ed"><i>// To describe this logic, think of a zz_pBak object</i></font><br>
<font color="#0000ed"><i>// of having two components: a modulus q (possibly "null") and </i></font><br>
<font color="#0000ed"><i>// an "auto-restore bit" b.</i></font><br>
<br>
<font color="#008b00"><b>class</b></font> zz_pBak {<br>
<font color="#b02f60"><b>public</b></font>:<br>
<br>
<br>
zz_pBak(); <font color="#0000ed"><i>// q = "null", b = 0</i></font><br>
<br>
~zz_pBak(); <font color="#0000ed"><i>// if (b) CurrentModulus = q</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> save(); <font color="#0000ed"><i>// q = CurrentModulus, b = 1 </i></font><br>
<font color="#008b00"><b>void</b></font> restore(); <font color="#0000ed"><i>// CurrentModulus = q, b = 0</i></font><br>
<br>
<br>
<font color="#b02f60"><b>private</b></font>:<br>
zz_pBak(<font color="#008b00"><b>const</b></font> zz_pBak&); <font color="#0000ed"><i>// copy disabled</i></font><br>
<font color="#008b00"><b>void</b></font> <font color="#b02f60"><b>operator</b></font>=(<font color="#008b00"><b>const</b></font> zz_pBak&); <font color="#0000ed"><i>// assignment disabled</i></font><br>
};<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Miscellany</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> clear(zz_p& x); <font color="#0000ed"><i>// x = 0</i></font><br>
<font color="#008b00"><b>void</b></font> set(zz_p& x); <font color="#0000ed"><i>// x = 1</i></font><br>
<br>
<font color="#008b00"><b>static</b></font> mulmod_t zz_p::ModulusInverse();<br>
<font color="#0000ed"><i>// zz_p::ModulusInverse() returns PrepMulMod(zz_p::modulus()) </i></font><br>
<br>
<font color="#008b00"><b>static</b></font> zz_p zz_p::zero();<br>
<font color="#0000ed"><i>// zz_p::zero() yields a read-only reference to zero</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> swap(zz_p& x, zz_p& y);<br>
<font color="#0000ed"><i>// swap x and y </i></font><br>
<br>
<font color="#008b00"><b>static</b></font> <font color="#008b00"><b>void</b></font> zz_p::init(<font color="#008b00"><b>long</b></font> p, <font color="#008b00"><b>long</b></font> maxroot);<br>
<font color="#0000ed"><i>// Same as ordinary zz_p::init(p), but somewhat more efficient. If you are</i></font><br>
<font color="#0000ed"><i>// going to perform arithmetic modulo a degree n polynomial, in which</i></font><br>
<font color="#0000ed"><i>// case set maxroot to NextPowerOfTwo(n)+1. This is useful, for</i></font><br>
<font color="#0000ed"><i>// example, if you are going to factor a polynomial of degree n modulo</i></font><br>
<font color="#0000ed"><i>// p, and you know n in advance.</i></font><br>
<font color="#0000ed"><i>// If maxroot is set too low, the program will abort with an</i></font><br>
<font color="#0000ed"><i>// appropriate error message.</i></font><br>
<br>
<font color="#008b00"><b>static</b></font> <font color="#008b00"><b>void</b></font> zz_p::FFTInit(<font color="#008b00"><b>long</b></font> i);<br>
<font color="#0000ed"><i>// sets modulus to the i-th FFT prime (counting from 0). FFT primes</i></font><br>
<font color="#0000ed"><i>// are NTL_SP_NBITS-bit primes p, where p-1 is divisible by a high power</i></font><br>
<font color="#0000ed"><i>// of two. Thus, polynomial arithmetic mod p can be implemented</i></font><br>
<font color="#0000ed"><i>// particularly efficiently using the FFT. As i increases, the power</i></font><br>
<font color="#0000ed"><i>// of 2 that divides p-1 gets smaller, thus placing a more severe</i></font><br>
<font color="#0000ed"><i>// restriction on the degrees of the polynomials to be multiplied.</i></font><br>
<br>
<font color="#008b00"><b>static</b></font> <font color="#008b00"><b>void</b></font> zz_p::UserFFTInit(<font color="#008b00"><b>long</b></font> p);<br>
<font color="#0000ed"><i>// set the modulus to a user-provided FFT prime p. To be useful,</i></font><br>
<font color="#0000ed"><i>// p-1 should be divisibly by a high power of 2. </i></font><br>
<font color="#0000ed"><i>// The function is a utility routine that may be used to </i></font><br>
<font color="#0000ed"><i>// calculate this value (see below). </i></font><br>
<font color="#0000ed"><i>// If you are going to perform arithmetic modulo a degree n polynomial, </i></font><br>
<font color="#0000ed"><i>// you will want CalcMaxRoot(p) >= NextPowerOfTwo(n)+1. </i></font><br>
<br>
zz_pContext::zz_pContext(<font color="#008b00"><b>long</b></font> p, <font color="#008b00"><b>long</b></font> maxroot);<br>
<font color="#0000ed"><i>// constructor for a zz_pContext with same semantics</i></font><br>
<font color="#0000ed"><i>// as zz_p::init(p, maxroot) above.</i></font><br>
<br>
zz_pContext::zz_pContext(INIT_FFT_TYPE, <font color="#008b00"><b>long</b></font> i);<br>
<font color="#0000ed"><i>// constructor for a zz_pContext with same semantics</i></font><br>
<font color="#0000ed"><i>// as zz_p::FFTInit(i) above; invoke as zz_pContext(INIT_FFT, i).</i></font><br>
<br>
zz_pContext::zz_pContext(INIT_USER_FFT_TYPE, <font color="#008b00"><b>long</b></font> p);<br>
<font color="#0000ed"><i>// constructor for a zz_pContext with same semantics</i></font><br>
<font color="#0000ed"><i>// as zz_p::UserFFTInit(p) above; invoke as zz_pContext(INIT_USER_FFT, p).</i></font><br>
<br>
zz_p::zz_p(INIT_NO_ALLOC_TYPE);<br>
<font color="#0000ed"><i>// provided for consistency with other classes, initialize to zero</i></font><br>
<br>
zz_p::zz_p(INIT_ALLOC_TYPE);<br>
<font color="#0000ed"><i>// provided for consistency with other classes, initialize to zero</i></font><br>
<br>
zz_p::allocate();<br>
<font color="#0000ed"><i>// provided for consistency with other classes, no action</i></font><br>
<br>
<br>
<br>
<font color="#008b00"><b>long</b></font> CalcMaxRoot(<font color="#008b00"><b>long</b></font> p);<br>
<font color="#0000ed"><i>// p is assumed to be an odd prime.</i></font><br>
<font color="#0000ed"><i>// Returns the largest k such that 2^k divides p-1</i></font><br>
<font color="#0000ed"><i>// and such that k does not exceed an implementation defined</i></font><br>
<font color="#0000ed"><i>// constant. This represents the max power of two for which</i></font><br>
<font color="#0000ed"><i>// an FFT mod p is supported.</i></font><br>
<br>
<br>
<br>
<br>
<br>
</font></body>
</html>
