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