doc/cln_7.html

   1 <HTML>
   2 <HEAD>
   3 <!-- Created by texi2html 1.56k from cln.texi on 2 June 2000 -->
   4
   5 <TITLE>CLN, a Class Library for Numbers - 7. Modular integers</TITLE>
   6 </HEAD>
   7 <BODY>
   8 Go to the <A HREF="cln_1.html">first</A>, <A HREF="cln_6.html">previous</A>, <A HREF="cln_8.html">next</A>, <A HREF="cln_13.html">last</A> section, <A HREF="cln_toc.html">table of contents</A>.
   9 <P><HR><P>
  10
  11
  12 <H1><A NAME="SEC49" HREF="cln_toc.html#TOC49">7. Modular integers</A></H1>
  13 <P>
  14 <A NAME="IDX241"></A>
  15
  16
  17
  18
  19 <H2><A NAME="SEC50" HREF="cln_toc.html#TOC50">7.1 Modular integer rings</A></H2>
  20 <P>
  21 <A NAME="IDX242"></A>
  22
  23
  24 <P>
  25 CLN implements modular integers, i.e. integers modulo a fixed integer N.
  26 The modulus is explicitly part of every modular integer. CLN doesn't
  27 allow you to (accidentally) mix elements of different modular rings,
  28 e.g. <CODE>(3 mod 4) + (2 mod 5)</CODE> will result in a runtime error.
  29 (Ideally one would imagine a generic data type <CODE>cl_MI(N)</CODE>, but C++
  30 doesn't have generic types. So one has to live with runtime checks.)
  31
  32
  33 <P>
  34 The class of modular integer rings is
  35
  36
  37
  38 <PRE>
  39                          Ring
  40                        cl_ring
  41                       &#60;cl_ring.h&#62;
  42                           |
  43                           |
  44                  Modular integer ring
  45                     cl_modint_ring
  46                    &#60;cl_modinteger.h&#62;
  47 </PRE>
  48
  49 <P>
  50 <A NAME="IDX243"></A>
  51
  52
  53 <P>
  54 and the class of all modular integers (elements of modular integer rings) is
  55
  56
  57
  58 <PRE>
  59                     Modular integer
  60                          cl_MI
  61                    &#60;cl_modinteger.h&#62;
  62 </PRE>
  63
  64 <P>
  65 Modular integer rings are constructed using the function
  66
  67
  68 <DL COMPACT>
  69
  70 <DT><CODE>cl_modint_ring cl_find_modint_ring (const cl_I&#38; N)</CODE>
  71 <DD>
  72 <A NAME="IDX244"></A>
  73 This function returns the modular ring <SAMP>`Z/NZ'</SAMP>. It takes care
  74 of finding out about special cases of <CODE>N</CODE>, like powers of two
  75 and odd numbers for which Montgomery multiplication will be a win,
  76 <A NAME="IDX245"></A>
  77 and precomputes any necessary auxiliary data for computing modulo <CODE>N</CODE>.
  78 There is a cache table of rings, indexed by <CODE>N</CODE> (or, more precisely,
  79 by <CODE>abs(N)</CODE>). This ensures that the precomputation costs are reduced
  80 to a minimum.
  81 </DL>
  82
  83 <P>
  84 Modular integer rings can be compared for equality:
  85
  86
  87 <DL COMPACT>
  88
  89 <DT><CODE>bool operator== (const cl_modint_ring&#38;, const cl_modint_ring&#38;)</CODE>
  90 <DD>
  91 <A NAME="IDX246"></A>
  92 <DT><CODE>bool operator!= (const cl_modint_ring&#38;, const cl_modint_ring&#38;)</CODE>
  93 <DD>
  94 <A NAME="IDX247"></A>
  95 These compare two modular integer rings for equality. Two different calls
  96 to <CODE>cl_find_modint_ring</CODE> with the same argument necessarily return the
  97 same ring because it is memoized in the cache table.
  98 </DL>
  99
 100
 101
 102 <H2><A NAME="SEC51" HREF="cln_toc.html#TOC51">7.2 Functions on modular integers</A></H2>
 103
 104 <P>
 105 Given a modular integer ring <CODE>R</CODE>, the following members can be used.
 106
 107
 108 <DL COMPACT>
 109
 110 <DT><CODE>cl_I R-&#62;modulus</CODE>
 111 <DD>
 112 <A NAME="IDX248"></A>
 113 This is the ring's modulus, normalized to be nonnegative: <CODE>abs(N)</CODE>.
 114
 115 <DT><CODE>cl_MI R-&#62;zero()</CODE>
 116 <DD>
 117 <A NAME="IDX249"></A>
 118 This returns <CODE>0 mod N</CODE>.
 119
 120 <DT><CODE>cl_MI R-&#62;one()</CODE>
 121 <DD>
 122 <A NAME="IDX250"></A>
 123 This returns <CODE>1 mod N</CODE>.
 124
 125 <DT><CODE>cl_MI R-&#62;canonhom (const cl_I&#38; x)</CODE>
 126 <DD>
 127 <A NAME="IDX251"></A>
 128 This returns <CODE>x mod N</CODE>.
 129
 130 <DT><CODE>cl_I R-&#62;retract (const cl_MI&#38; x)</CODE>
 131 <DD>
 132 <A NAME="IDX252"></A>
 133 This is a partial inverse function to <CODE>R-&#62;canonhom</CODE>. It returns the
 134 standard representative (<CODE>&#62;=0</CODE>, <CODE>&#60;N</CODE>) of <CODE>x</CODE>.
 135
 136 <DT><CODE>cl_MI R-&#62;random(cl_random_state&#38; randomstate)</CODE>
 137 <DD>
 138 <DT><CODE>cl_MI R-&#62;random()</CODE>
 139 <DD>
 140 <A NAME="IDX253"></A>
 141 This returns a random integer modulo <CODE>N</CODE>.
 142 </DL>
 143
 144 <P>
 145 The following operations are defined on modular integers.
 146
 147
 148 <DL COMPACT>
 149
 150 <DT><CODE>cl_modint_ring x.ring ()</CODE>
 151 <DD>
 152 <A NAME="IDX254"></A>
 153 Returns the ring to which the modular integer <CODE>x</CODE> belongs.
 154
 155 <DT><CODE>cl_MI operator+ (const cl_MI&#38;, const cl_MI&#38;)</CODE>
 156 <DD>
 157 <A NAME="IDX255"></A>
 158 Returns the sum of two modular integers. One of the arguments may also
 159 be a plain integer.
 160
 161 <DT><CODE>cl_MI operator- (const cl_MI&#38;, const cl_MI&#38;)</CODE>
 162 <DD>
 163 <A NAME="IDX256"></A>
 164 Returns the difference of two modular integers. One of the arguments may also
 165 be a plain integer.
 166
 167 <DT><CODE>cl_MI operator- (const cl_MI&#38;)</CODE>
 168 <DD>
 169 Returns the negative of a modular integer.
 170
 171 <DT><CODE>cl_MI operator* (const cl_MI&#38;, const cl_MI&#38;)</CODE>
 172 <DD>
 173 <A NAME="IDX257"></A>
 174 Returns the product of two modular integers. One of the arguments may also
 175 be a plain integer.
 176
 177 <DT><CODE>cl_MI square (const cl_MI&#38;)</CODE>
 178 <DD>
 179 <A NAME="IDX258"></A>
 180 Returns the square of a modular integer.
 181
 182 <DT><CODE>cl_MI recip (const cl_MI&#38; x)</CODE>
 183 <DD>
 184 <A NAME="IDX259"></A>
 185 Returns the reciprocal <CODE>x^-1</CODE> of a modular integer <CODE>x</CODE>. <CODE>x</CODE>
 186 must be coprime to the modulus, otherwise an error message is issued.
 187
 188 <DT><CODE>cl_MI div (const cl_MI&#38; x, const cl_MI&#38; y)</CODE>
 189 <DD>
 190 <A NAME="IDX260"></A>
 191 Returns the quotient <CODE>x*y^-1</CODE> of two modular integers <CODE>x</CODE>, <CODE>y</CODE>.
 192 <CODE>y</CODE> must be coprime to the modulus, otherwise an error message is issued.
 193
 194 <DT><CODE>cl_MI expt_pos (const cl_MI&#38; x, const cl_I&#38; y)</CODE>
 195 <DD>
 196 <A NAME="IDX261"></A>
 197 <CODE>y</CODE> must be &#62; 0. Returns <CODE>x^y</CODE>.
 198
 199 <DT><CODE>cl_MI expt (const cl_MI&#38; x, const cl_I&#38; y)</CODE>
 200 <DD>
 201 <A NAME="IDX262"></A>
 202 Returns <CODE>x^y</CODE>. If <CODE>y</CODE> is negative, <CODE>x</CODE> must be coprime to the
 203 modulus, else an error message is issued.
 204
 205 <DT><CODE>cl_MI operator&#60;&#60; (const cl_MI&#38; x, const cl_I&#38; y)</CODE>
 206 <DD>
 207 <A NAME="IDX263"></A>
 208 Returns <CODE>x*2^y</CODE>.
 209
 210 <DT><CODE>cl_MI operator&#62;&#62; (const cl_MI&#38; x, const cl_I&#38; y)</CODE>
 211 <DD>
 212 <A NAME="IDX264"></A>
 213 Returns <CODE>x*2^-y</CODE>. When <CODE>y</CODE> is positive, the modulus must be odd,
 214 or an error message is issued.
 215
 216 <DT><CODE>bool operator== (const cl_MI&#38;, const cl_MI&#38;)</CODE>
 217 <DD>
 218 <A NAME="IDX265"></A>
 219 <DT><CODE>bool operator!= (const cl_MI&#38;, const cl_MI&#38;)</CODE>
 220 <DD>
 221 <A NAME="IDX266"></A>
 222 Compares two modular integers, belonging to the same modular integer ring,
 223 for equality.
 224
 225 <DT><CODE>cl_boolean zerop (const cl_MI&#38; x)</CODE>
 226 <DD>
 227 <A NAME="IDX267"></A>
 228 Returns true if <CODE>x</CODE> is <CODE>0 mod N</CODE>.
 229 </DL>
 230
 231 <P>
 232 The following output functions are defined (see also the chapter on
 233 input/output).
 234
 235
 236 <DL COMPACT>
 237
 238 <DT><CODE>void fprint (cl_ostream stream, const cl_MI&#38; x)</CODE>
 239 <DD>
 240 <A NAME="IDX268"></A>
 241 <DT><CODE>cl_ostream operator&#60;&#60; (cl_ostream stream, const cl_MI&#38; x)</CODE>
 242 <DD>
 243 <A NAME="IDX269"></A>
 244 Prints the modular integer <CODE>x</CODE> on the <CODE>stream</CODE>. The output may depend
 245 on the global printer settings in the variable <CODE>cl_default_print_flags</CODE>.
 246 </DL>
 247
 248 <P><HR><P>
 249 Go to the <A HREF="cln_1.html">first</A>, <A HREF="cln_6.html">previous</A>, <A HREF="cln_8.html">next</A>, <A HREF="cln_13.html">last</A> section, <A HREF="cln_toc.html">table of contents</A>.
 250 </BODY>
 251 </HTML>