| 1 | <html> |
|---|
| 2 | <head> |
|---|
| 3 | <title> |
|---|
| 4 | A Tour of NTL: Examples: Big Integers </title> |
|---|
| 5 | </head> |
|---|
| 6 | |
|---|
| 7 | <body bgcolor="#fff9e6"> |
|---|
| 8 | |
|---|
| 9 | <center> |
|---|
| 10 | <img src="arrow1.gif" alt="[Previous]" align=bottom> |
|---|
| 11 | <a href="tour-examples.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> |
|---|
| 12 | <a href="tour-ex2.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a> |
|---|
| 13 | </center> |
|---|
| 14 | |
|---|
| 15 | <h1> |
|---|
| 16 | <p align=center> |
|---|
| 17 | A Tour of NTL: Examples: Big Integers |
|---|
| 18 | </p> |
|---|
| 19 | </h1> |
|---|
| 20 | |
|---|
| 21 | <p> <hr> <p> |
|---|
| 22 | |
|---|
| 23 | The first example makes use of the class |
|---|
| 24 | <tt>ZZ</tt>, |
|---|
| 25 | which |
|---|
| 26 | represents "big integers": signed, arbitrary length integers. |
|---|
| 27 | This program reads two big integers <tt>a</tt> and <tt>b</tt>, |
|---|
| 28 | and prints <tt>(a+1)*(b+1)</tt>. |
|---|
| 29 | |
|---|
| 30 | <p> |
|---|
| 31 | <pre> |
|---|
| 32 | #include <NTL/ZZ.h> |
|---|
| 33 | |
|---|
| 34 | int main() |
|---|
| 35 | { |
|---|
| 36 | ZZ a, b, c; |
|---|
| 37 | |
|---|
| 38 | cin >> a; |
|---|
| 39 | cin >> b; |
|---|
| 40 | c = (a+1)*(b+1); |
|---|
| 41 | cout << c << "\n"; |
|---|
| 42 | } |
|---|
| 43 | </pre> |
|---|
| 44 | |
|---|
| 45 | <p> |
|---|
| 46 | |
|---|
| 47 | This program declares three variables <tt>a</tt>, <tt>b</tt>, |
|---|
| 48 | and <tt>c</tt> of type <tt>ZZ</tt>. |
|---|
| 49 | The values <tt>a</tt> and <tt>b</tt> are read from standard input. |
|---|
| 50 | The value <tt>c</tt> is then computed as <tt>(a+1)*(b+1)</tt>. |
|---|
| 51 | Finally, the value of <tt>c</tt> is printed to the standard output. |
|---|
| 52 | |
|---|
| 53 | <p> |
|---|
| 54 | Note that one can compute with <tt>ZZ</tt>s much as with ordinary |
|---|
| 55 | <tt>int</tt>s, in that most of the standard arithmetic and |
|---|
| 56 | assignment operators can be used in a direct and natural way. |
|---|
| 57 | The <tt>C++</tt> compiler and the NTL library routines |
|---|
| 58 | automatically take care |
|---|
| 59 | of all the bookkeeping involved |
|---|
| 60 | with memory management and temporary objects. |
|---|
| 61 | |
|---|
| 62 | <p> <hr> <p> |
|---|
| 63 | |
|---|
| 64 | Here's a program that reads a list of integers from standard |
|---|
| 65 | input and prints the sum of their squares. |
|---|
| 66 | |
|---|
| 67 | <p> |
|---|
| 68 | <pre> |
|---|
| 69 | #include <NTL/ZZ.h> |
|---|
| 70 | |
|---|
| 71 | int main() |
|---|
| 72 | { |
|---|
| 73 | ZZ acc, val; |
|---|
| 74 | |
|---|
| 75 | acc = 0; |
|---|
| 76 | while (SkipWhiteSpace(cin)) { |
|---|
| 77 | cin >> val; |
|---|
| 78 | acc += val*val; |
|---|
| 79 | } |
|---|
| 80 | |
|---|
| 81 | cout << acc << "\n"; |
|---|
| 82 | } |
|---|
| 83 | </pre> |
|---|
| 84 | |
|---|
| 85 | <p> |
|---|
| 86 | |
|---|
| 87 | The function <tt>SkipWhiteSpace</tt> is defined by NTL. |
|---|
| 88 | It skips over white space, and returns 1 if there is something |
|---|
| 89 | following it. |
|---|
| 90 | This function is useful, because |
|---|
| 91 | NTL's input operators raise an error if an input |
|---|
| 92 | is missing or ill-formed. |
|---|
| 93 | This is different from the standard I/O library, |
|---|
| 94 | which does not raise an error. |
|---|
| 95 | Personally, I find that not raising an error, or at least |
|---|
| 96 | an exception, is a bad idea, since the caller of the I/O |
|---|
| 97 | routine must constantly check the status of the input |
|---|
| 98 | stream. |
|---|
| 99 | |
|---|
| 100 | |
|---|
| 101 | |
|---|
| 102 | |
|---|
| 103 | <p> |
|---|
| 104 | <hr> |
|---|
| 105 | <p> |
|---|
| 106 | |
|---|
| 107 | Here's a simple modular exponentiation routine for computing |
|---|
| 108 | <tt>a^e mod n</tt>. |
|---|
| 109 | NTL already provides a more sophisticated one, though. |
|---|
| 110 | |
|---|
| 111 | <p> |
|---|
| 112 | <pre> |
|---|
| 113 | ZZ PowerMod(const ZZ& a, const ZZ& e, const ZZ& n) |
|---|
| 114 | { |
|---|
| 115 | if (e == 0) return to_ZZ(1); |
|---|
| 116 | |
|---|
| 117 | long k = NumBits(e); |
|---|
| 118 | |
|---|
| 119 | ZZ res; |
|---|
| 120 | res = 1; |
|---|
| 121 | |
|---|
| 122 | for (long i = k-1; i >= 0; i--) { |
|---|
| 123 | res = (res*res) % n; |
|---|
| 124 | if (bit(e, i) == 1) res = (res*a) % n; |
|---|
| 125 | } |
|---|
| 126 | |
|---|
| 127 | if (e < 0) |
|---|
| 128 | return InvMod(res, n); |
|---|
| 129 | else |
|---|
| 130 | return res; |
|---|
| 131 | } |
|---|
| 132 | </pre> |
|---|
| 133 | <p> |
|---|
| 134 | |
|---|
| 135 | Note that as an alternative, we could implement the inner loop |
|---|
| 136 | as follows: |
|---|
| 137 | |
|---|
| 138 | <pre> |
|---|
| 139 | res = SqrMod(res, n); |
|---|
| 140 | if (bit(e, i) == 1) res = MulMod(res, a, n); |
|---|
| 141 | </pre> |
|---|
| 142 | |
|---|
| 143 | We could also write this as: |
|---|
| 144 | |
|---|
| 145 | <pre> |
|---|
| 146 | SqrMod(res, res, n); |
|---|
| 147 | if (bit(e, i) == 1) MulMod(res, res, a, n); |
|---|
| 148 | </pre> |
|---|
| 149 | |
|---|
| 150 | This illustrates an important point about NTL's programming interface. |
|---|
| 151 | For every function in NTL, there is a procedural version that |
|---|
| 152 | stores its result in its first argument. |
|---|
| 153 | The reason for using the procedural variant is efficieny: |
|---|
| 154 | on every iteration through the above loop, the functional form |
|---|
| 155 | of <tt>SqrMod</tt> will cause a temporary <tt>ZZ</tt> object to |
|---|
| 156 | be created and destroyed, whereas the procedural version |
|---|
| 157 | will not create any temporaries. |
|---|
| 158 | Where performance is critical, the procedural version |
|---|
| 159 | is to be preferred. |
|---|
| 160 | Although it is usually silly to get too worked up about performance, |
|---|
| 161 | it may be reasonable to argue that modular exponentiation |
|---|
| 162 | is an important enough routine that it should be as fast as possible. |
|---|
| 163 | |
|---|
| 164 | <p> |
|---|
| 165 | |
|---|
| 166 | Note that when the functional version of a function |
|---|
| 167 | can be naturally named with an operator, this is done. |
|---|
| 168 | So for example, NTL provides a 3-argument <tt>mul</tt> routine |
|---|
| 169 | for <tt>ZZ</tt> multiplication, and a functional version |
|---|
| 170 | whose name is <tt>operator *</tt>, and not <tt>mul</tt>. |
|---|
| 171 | |
|---|
| 172 | <p> |
|---|
| 173 | |
|---|
| 174 | While we are taking about temporaries, consider the first version |
|---|
| 175 | of the inner loop. |
|---|
| 176 | Execution of the statement |
|---|
| 177 | <pre> |
|---|
| 178 | res = (res*res) % n; |
|---|
| 179 | </pre> |
|---|
| 180 | will result in the creation of two temporary objects, |
|---|
| 181 | one for the product, and one for the result of the mod operation, |
|---|
| 182 | whose value is copied into <tt>res</tt>. |
|---|
| 183 | Of course, the compiler automatically generates the code for |
|---|
| 184 | cleaning up temporaries and other local objects at the right time. |
|---|
| 185 | The programmer does not have to worry about this. |
|---|
| 186 | |
|---|
| 187 | |
|---|
| 188 | <p> <hr> <p> |
|---|
| 189 | |
|---|
| 190 | This example is a bit more interesting. |
|---|
| 191 | The following program prompts the user for an input, |
|---|
| 192 | and applies a simple probabilistic primality test. |
|---|
| 193 | Note that NTL already provides a slightly more sophisticated |
|---|
| 194 | prime test. |
|---|
| 195 | |
|---|
| 196 | <p> |
|---|
| 197 | <pre> |
|---|
| 198 | #include <NTL/ZZ.h> |
|---|
| 199 | |
|---|
| 200 | long witness(const ZZ& n, const ZZ& x) |
|---|
| 201 | { |
|---|
| 202 | ZZ m, y, z; |
|---|
| 203 | long j, k; |
|---|
| 204 | |
|---|
| 205 | if (x == 0) return 0; |
|---|
| 206 | |
|---|
| 207 | // compute m, k such that n-1 = 2^k * m, m odd: |
|---|
| 208 | |
|---|
| 209 | k = 1; |
|---|
| 210 | m = n/2; |
|---|
| 211 | while (m % 2 == 0) { |
|---|
| 212 | k++; |
|---|
| 213 | m /= 2; |
|---|
| 214 | } |
|---|
| 215 | |
|---|
| 216 | z = PowerMod(x, m, n); // z = x^m % n |
|---|
| 217 | if (z == 1) return 0; |
|---|
| 218 | |
|---|
| 219 | j = 0; |
|---|
| 220 | do { |
|---|
| 221 | y = z; |
|---|
| 222 | z = (y*y) % n; |
|---|
| 223 | j++; |
|---|
| 224 | } while (j < k && z != 1); |
|---|
| 225 | |
|---|
| 226 | return z != 1 || y != n-1; |
|---|
| 227 | } |
|---|
| 228 | |
|---|
| 229 | |
|---|
| 230 | long PrimeTest(const ZZ& n, long t) |
|---|
| 231 | { |
|---|
| 232 | if (n <= 1) return 0; |
|---|
| 233 | |
|---|
| 234 | // first, perform trial division by primes up to 2000 |
|---|
| 235 | |
|---|
| 236 | PrimeSeq s; // a class for quickly generating primes in sequence |
|---|
| 237 | long p; |
|---|
| 238 | |
|---|
| 239 | p = s.next(); // first prime is always 2 |
|---|
| 240 | while (p && p < 2000) { |
|---|
| 241 | if ((n % p) == 0) return (n == p); |
|---|
| 242 | p = s.next(); |
|---|
| 243 | } |
|---|
| 244 | |
|---|
| 245 | // second, perform t Miller-Rabin tests |
|---|
| 246 | |
|---|
| 247 | ZZ x; |
|---|
| 248 | long i; |
|---|
| 249 | |
|---|
| 250 | for (i = 0; i < t; i++) { |
|---|
| 251 | x = RandomBnd(n); // random number between 0 and n-1 |
|---|
| 252 | |
|---|
| 253 | if (witness(n, x)) |
|---|
| 254 | return 0; |
|---|
| 255 | } |
|---|
| 256 | |
|---|
| 257 | return 1; |
|---|
| 258 | } |
|---|
| 259 | |
|---|
| 260 | int main() |
|---|
| 261 | { |
|---|
| 262 | ZZ n; |
|---|
| 263 | |
|---|
| 264 | cout << "n: "; |
|---|
| 265 | cin >> n; |
|---|
| 266 | |
|---|
| 267 | if (PrimeTest(n, 10)) |
|---|
| 268 | cout << n << " is probably prime\n"; |
|---|
| 269 | else |
|---|
| 270 | cout << n << " is composite\n"; |
|---|
| 271 | } |
|---|
| 272 | </pre> |
|---|
| 273 | <p> |
|---|
| 274 | |
|---|
| 275 | Note that in NTL, there are typically a number of ways to |
|---|
| 276 | compute the same thing. |
|---|
| 277 | For example, consider the computation of <tt>m</tt> and <tt>k</tt> |
|---|
| 278 | in function <tt>witness</tt>. |
|---|
| 279 | We could have written it thusly: |
|---|
| 280 | |
|---|
| 281 | <pre> |
|---|
| 282 | k = 1; |
|---|
| 283 | m = n >> 1; |
|---|
| 284 | while (!IsOdd(m)) { |
|---|
| 285 | k++; |
|---|
| 286 | m >>= 1; |
|---|
| 287 | } |
|---|
| 288 | </pre> |
|---|
| 289 | |
|---|
| 290 | It turns out that this is actually not significantly more |
|---|
| 291 | efficient than the original version, because the implementation |
|---|
| 292 | optimizes multiplication and division by 2. |
|---|
| 293 | |
|---|
| 294 | <p> |
|---|
| 295 | |
|---|
| 296 | The following is more efficient: |
|---|
| 297 | |
|---|
| 298 | <pre> |
|---|
| 299 | k = 1; |
|---|
| 300 | while (bit(n, k) == 0) k++; |
|---|
| 301 | m = n >> k; |
|---|
| 302 | </pre> |
|---|
| 303 | |
|---|
| 304 | As it happens, there is a built-in NTL routine that does just what we want: |
|---|
| 305 | |
|---|
| 306 | <pre> |
|---|
| 307 | m = n-1; |
|---|
| 308 | k = MakeOdd(m); |
|---|
| 309 | </pre> |
|---|
| 310 | |
|---|
| 311 | |
|---|
| 312 | |
|---|
| 313 | <p> <hr> <p> |
|---|
| 314 | |
|---|
| 315 | Having seen a number of examples involving <tt>ZZ</tt>s, |
|---|
| 316 | let's look at the <tt>ZZ</tt> interface in a bit more detail. |
|---|
| 317 | |
|---|
| 318 | <p> |
|---|
| 319 | |
|---|
| 320 | <b> |
|---|
| 321 | Constructors, assignment, and conversions |
|---|
| 322 | </b> |
|---|
| 323 | |
|---|
| 324 | <p> |
|---|
| 325 | |
|---|
| 326 | When you declare an object of type <tt>ZZ</tt>, |
|---|
| 327 | the default constructor initializes to the value <tt>0</tt>. |
|---|
| 328 | As we have already seen, there is an assignment operator that |
|---|
| 329 | allows one to copy the value of one <tt>ZZ</tt> to another. |
|---|
| 330 | Note that these copies (like almost all copies in NTL) are "deep", |
|---|
| 331 | i.e., the actual data is copied, and not just a pointer. |
|---|
| 332 | Of course, if the amount of space allocated by the destination |
|---|
| 333 | of the assignment is insufficient to hold the value of the source, |
|---|
| 334 | space is automatically re-allocated. |
|---|
| 335 | |
|---|
| 336 | <p> |
|---|
| 337 | One can also assign a value of type <tt>long</tt> to a <tt>ZZ</tt>: |
|---|
| 338 | <pre> |
|---|
| 339 | ZZ x; |
|---|
| 340 | x = 1; |
|---|
| 341 | </pre> |
|---|
| 342 | |
|---|
| 343 | <p> |
|---|
| 344 | Note that one cannot write |
|---|
| 345 | <pre> |
|---|
| 346 | ZZ x = 1; // error |
|---|
| 347 | </pre> |
|---|
| 348 | to initialize a <tt>ZZ</tt>. |
|---|
| 349 | As a design principle, NTL avoids implicit conversions, and unfortunately, |
|---|
| 350 | the only way to allow initializations like this in <tt>C++</tt> |
|---|
| 351 | is to define an implicit conversion operator. |
|---|
| 352 | Instead, one could write |
|---|
| 353 | <pre> |
|---|
| 354 | ZZ x = to_ZZ(1); |
|---|
| 355 | </pre> |
|---|
| 356 | This is an example of one of NTL's conversion routines. |
|---|
| 357 | For very large constants, one can write: |
|---|
| 358 | <pre> |
|---|
| 359 | ZZ x = to_ZZ("99999999999999999999"); |
|---|
| 360 | </pre> |
|---|
| 361 | These examples illustrate conversion rountines in their |
|---|
| 362 | functional forms. |
|---|
| 363 | The corresponding procedural forms are all called <tt>conv</tt>, e.g., |
|---|
| 364 | <pre> |
|---|
| 365 | ZZ x; |
|---|
| 366 | conv(x, 1); |
|---|
| 367 | conv(x, "99999999999999999999"); |
|---|
| 368 | </pre> |
|---|
| 369 | |
|---|
| 370 | <p> |
|---|
| 371 | <b> |
|---|
| 372 | Functionality |
|---|
| 373 | </b> |
|---|
| 374 | <p> |
|---|
| 375 | |
|---|
| 376 | All of the basic arithmetic operators are supported, |
|---|
| 377 | including comparison, arithmetic, shift, and bit-wise logical operations. |
|---|
| 378 | One can mix <tt>ZZ</tt>s and <tt>long</tt>s in any expresion in |
|---|
| 379 | a natural way. |
|---|
| 380 | As was already mentioned, NTL does not support implicit type conversion; |
|---|
| 381 | rather, for basic operations, it simply overloads the operators |
|---|
| 382 | or functions in a way to achieve a kind of "promotion logic": |
|---|
| 383 | if one input is a <tt>ZZ</tt> and the other is a <tt>long</tt> |
|---|
| 384 | (or something that implicitly converts to a <tt>long</tt>, like |
|---|
| 385 | an <tt>int</tt>), the <tt>long</tt> input is effectively converted |
|---|
| 386 | to a <tt>ZZ</tt>. |
|---|
| 387 | Moreover, wherever possible, the implementation does this |
|---|
| 388 | as efficiently as possible, and usually avoids the creation |
|---|
| 389 | of a temporary <tt>ZZ</tt>. |
|---|
| 390 | |
|---|
| 391 | <p> |
|---|
| 392 | There are also procedural versions for all the basic arithmetic |
|---|
| 393 | operations: |
|---|
| 394 | <pre> |
|---|
| 395 | add, sub, negate, mul, sqr, div, rem, DivRem, |
|---|
| 396 | LeftShift, RightShift, |
|---|
| 397 | bit_and, bit_or, bit_xor |
|---|
| 398 | </pre> |
|---|
| 399 | |
|---|
| 400 | <p> |
|---|
| 401 | There are many other routines. |
|---|
| 402 | Here is a brief summary: |
|---|
| 403 | <ul> |
|---|
| 404 | <li> |
|---|
| 405 | <tt>GCD</tt> -- computes greatest common divisor of two integers |
|---|
| 406 | <li> |
|---|
| 407 | <tt>XGCD</tt> -- extended Euclidean algorithm |
|---|
| 408 | <li> |
|---|
| 409 | <tt>AddMod</tt>, <tt>SubMod</tt>, <tt>NegateMod</tt>, |
|---|
| 410 | <tt>MulMod</tt>, <tt>SqrMod</tt>, <tt>InvMod</tt>, |
|---|
| 411 | <tt>PowerMod</tt> -- routines for modular arithmetic, |
|---|
| 412 | including inversion and exponentiation |
|---|
| 413 | <li> |
|---|
| 414 | <tt>NumBits</tt> -- length of binary representation |
|---|
| 415 | <li> |
|---|
| 416 | <tt>bit</tt> -- extract a bit |
|---|
| 417 | <li> |
|---|
| 418 | <tt>ZZFromBytes</tt>, <tt>BytesFromZZ</tt> -- |
|---|
| 419 | convert between octet strings and <tt>ZZ</tt>s |
|---|
| 420 | <li> |
|---|
| 421 | <tt>RandomBnd</tt>, <tt>RandomBits</tt>, <tt>RandomLen</tt> -- |
|---|
| 422 | routines for generating pseudo-random numbers |
|---|
| 423 | <li> |
|---|
| 424 | <tt>GenPrime</tt>, <tt>ProbPrime</tt> -- routines for generating primes |
|---|
| 425 | and testing primality |
|---|
| 426 | <li> |
|---|
| 427 | <tt>power</tt> -- (non-modular) exponentiation |
|---|
| 428 | <li> |
|---|
| 429 | <tt>SqrRoot</tt> -- integer part of square root |
|---|
| 430 | <li> |
|---|
| 431 | <tt>Jacobi</tt>, <tt>SqrRootMod</tt> -- Jacobi symbol and modular |
|---|
| 432 | square root |
|---|
| 433 | </ul> |
|---|
| 434 | |
|---|
| 435 | <p> |
|---|
| 436 | Most of these functions also have pure <tt>long</tt> versions as |
|---|
| 437 | well, and as usual, there are both functional and procedural |
|---|
| 438 | variants. |
|---|
| 439 | |
|---|
| 440 | <p> |
|---|
| 441 | There are other functions as well. |
|---|
| 442 | See <a href="ZZ.txt"><tt>ZZ.txt</tt></a> for complete details. |
|---|
| 443 | Also see <a href="tools.txt"><tt>tools.txt</tt></a> for some basic |
|---|
| 444 | services provided by NTL. |
|---|
| 445 | |
|---|
| 446 | |
|---|
| 447 | <p> |
|---|
| 448 | <center> |
|---|
| 449 | <img src="arrow1.gif" alt="[Previous]" align=bottom> |
|---|
| 450 | <a href="tour-examples.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> |
|---|
| 451 | <a href="tour-ex2.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a> |
|---|
| 452 | </center> |
|---|
| 453 | |
|---|
| 454 | </body> |
|---|
| 455 | </html> |
|---|
