mdw@git.distorted.org.uk Git - catacomb-perl/blob - Catacomb::MP.pod

   1 =head1 NAME
   2
   3 Catacomb::MP - Multiprecision integer arithmetic
   4
   5 =head1 SYNOPSIS
   6
   7     use Catacomb qw(:const :mp :random :pgen);
   8
   9     $x = Catacomb::MP->new($str, [$radix]);
  10     $x = Catacomb::MP->new($i);
  11     $x = Catacomb::MP->loadb($bytes);
  12     $x = Catacomb::MP->loadl($bytes);
  13     $x = Catacomb::MP->loadb2c($bytes);
  14     $x = Catacomb::MP->loadl2c($bytes);
  15     ($x, $rest) = Catacomb::MP->fromstring($str, [$radix]);
  16     $x = mp($str, [$radix]);
  17     $x = mp($i);
  18     ($x, $rest) = mp_fromstring($str, [$radix]);
  19     $a = $b + $c;
  20     $a = $b - $c;
  21     $a = $b * $c;
  22     $a = $b / $c;
  23     $a = $b % $c;
  24     $a = $b ** $n;
  25     $a = $b << $n;
  26     $a = $b >> $n;
  27     $a = $b & $c;
  28     $a = $b | $c;
  29     $a = $b ^ $c;
  30     $a = ~$b;
  31     $p = $b == $c;
  32     $p = $b != $c;
  33     $p = $b < $c;
  34     $p = $b > $c;
  35     $p = $b <= $c;
  36     $p = $b >= $c;
  37     $a = sqrt($b);
  38     $a = -$b;
  39     $a = $b->add($c);
  40     $a = $b->sub($c);
  41     $a = $b->mul($c);
  42     ($q, $r) = $a->div($b);
  43     $a = $b->sqr();
  44     $a = $b->exp($c);
  45     $a = $b->sqrt();
  46     $a = $b->neg();
  47     $a = $b->not();
  48     $a = $b->not2c();
  49     $a = $b->mod($c);
  50     $p = $b->eq($c);
  51     $cmp = $b->cmp($c);
  52     $a = $b->and($c);
  53     $a = $b->and2c($c);
  54     $a = $b->or($c);
  55     $a = $b->or2c($c);
  56     $a = $b->xor($c);
  57     $a = $b->xor2c($c);
  58     $a = $b->nand($c);
  59     $a = $b->nand2c($c);
  60     $a = $b->nor($c);
  61     $a = $b->nor2c($c);
  62     $a = $b->not();
  63     $a = $b->not2c();
  64     $a = $b->lsl($n);
  65     $a = $b->lsl2c($n);
  66     $a = $b->lsr($n);
  67     $a = $b->lsr2c($n);
  68     $a = $b->setbit($n);
  69     $a = $b->setbit2c($n);
  70     $a = $b->clearbit($n);
  71     $a = $b->clearbit2c($n);
  72     $p = $b->testbit($n);
  73     $p = $b->testbit2c($n);
  74     $x = $y->copy(); # largely useless
  75     $g = $a->gcd($b);
  76     ($g, $u, $v) = $a->gcd($b);
  77     ($s, $t) = $m->odd(); # m = 2^s t
  78     $a = $p->modexp($x, $e);
  79     $a = $p->modinv($b);
  80     $r = $p->modsqrt($x);
  81     $q = $n->jac($a);
  82     $p = $x->primep([$rng]);
  83     $nbits = $x->bits();
  84     $nbytes = $x->octets();
  85     $bytes = $x->storeb([$nbytes]);
  86     $bytes = $x->storel([$nbytes]);
  87     $bytes = $x->storeb2c([$nbytes]);
  88     $bytes = $x->storel2c([$nbytes]);
  89     $str = $x->tostring([$radix]);
  90     $n = $x->toint();
  91
  92     $barrett = Catacomb::MP::Barrett->new($p);
  93     $barrett = $p->barrett();
  94     $p = $barrett->m();
  95     $x = $barrett->reduce($y);
  96     $a = $barrett->exp($x, $y);
  97
  98     $mont = Catacomb::MP::Mont->new($p);
  99     $mont = $p->mont();
 100     $r = $mont->r();
 101     $r2 = $mont->r2();
 102     $p = $mont->m();
 103     $x = $mont->in($y);
 104     $a = $mont->mul($x, $y);
 105     $a = $mont->expr($x, $y);
 106     $a = $mont->mexpr($x0, $e0, $x1, $e1, ...);
 107     $x = $mont->reduce($y);
 108     $x = $mont->out($y);
 109     $a = $mont->exp($x, $y);
 110     $a = $mont->mexp($x0, $e0, $x1, $e1, ...);
 111
 112     $reduce = Catacomb::MP::Reduce->new($p);
 113     $reduce = $p->mkreduce();
 114     $p = $reduce->m();
 115     $x = $reduce->reduce($y);
 116     $a = $barrett->exp($x, $y);
 117
 118     $crt = Catacomb::MP::CRT->new(@n);
 119     $n = $crt->product();
 120     @n = $crt->moduli();
 121     $x = $crt->solve(@r);
 122
 123 =head1 DESCRIPTION
 124
 125 This is a full-featured multiprecision maths library.  Integer objects
 126 belong to the class C<Catacomb::MP>.  Most standard arithmetic operators
 127 are overloaded and do the Right Thing.  See below for more details.
 128
 129 Note that multiprecision integers are I<immutable>.  No operation can
 130 change the value of an integer.
 131
 132 =head2 Constructors
 133
 134 =over
 135
 136 =item B<Catacomb::MP-E<gt>new(>i<int>B<)>
 137
 138 =item B<mp(>I<int>B<)>
 139
 140 Return the multiprecision integer whose value is I<int>.
 141
 142 =item B<Catacomb::MP-E<gt>new(>I<string>, [I<radix>]B<)>
 143
 144 =item B<mp(>I<string>, [I<radix>]B<)>
 145
 146 Returns the multiprecision integer whose value is represented by
 147 I<string>, in the given I<radix>.  If I<radix> is 0, as it is by
 148 default, then I<string> may have a prefix giving its radix: it may be
 149 B<0> for octal, B<0x> for hex, or I<r>B<_> for radix I<r>.  If the
 150 argument is invalid, B<undef> is returned.
 151
 152 =item B<Catacomb::MP-E<gt>loadb(>I<bytes>B<)>
 153
 154 =item B<Catacomb::MP-E<gt>loadl(>I<bytes>B<)>
 155
 156 =item B<mp_loadb(>I<bytes>B<)>
 157
 158 =item B<mp_loadl(>I<bytes>B<)>
 159
 160 Returns the multiprecision integer whose value is represented in big- or
 161 little-endian base-256 form by I<bytes>.  This will always be
 162 nonnegative.
 163
 164 Returns the multiprecision integer whose value is represented in
 165 little-endian base-256 form by I<bytes>.  This will always be
 166 nonnegative.
 167
 168 =item B<Catacomb::MP-E<gt>loadb2c(>I<bytes>B<)>
 169
 170 =item B<Catacomb::MP-E<gt>loadl2c(>I<bytes>B<)>
 171
 172 =item B<mp_loadb2c(>I<bytes>B<)>
 173
 174 =item B<mp_loadl2c(>I<bytes>B<)>
 175
 176 Returns the multiprecision integer whose value is represented in
 177 two's complement big- or little-endian base-256 form by I<bytes>.
 178
 179 =item B<Catacomb::MP-E<gt>fromstring(>I<string>, [I<radix>]B<)>
 180
 181 =item B<mp_fromstring(>I<string>, [I<radix>]B<)>
 182
 183 Returns the multiprecision integer whose value is represented by
 184 I<string>, and (in a list context) the remainder of I<string>.  If
 185 I<radix> is 0 then I<string> may have a prefix, as for B<new()>.  If
 186 I<string> is invalid, an empty list is returned.
 187
 188 =back
 189
 190 =head2 Methods
 191
 192 The B<Catacomb::MP> package overloads the standard arithmetic
 193 operators.  As long as one operand is a B<Catacomb::MP> object, the
 194 other may be any argument acceptable to B<new()>.  As a special
 195 exception, either argument to B<*> may be a B<Catacomb::EC::Pt> object,
 196 to perform elliptic curve point multiplication.
 197
 198 =over
 199
 200 =item I<a>B<-E<gt>add(>I<b>B<)>
 201
 202 =item I<a>B<-E<gt>sub(>I<b>B<)>
 203
 204 =item I<a>B<-E<gt>mul(>I<b>B<)>
 205
 206 =item I<a>B<-E<gt>div(>I<b>B<)>
 207
 208 =item I<a>B<-E<gt>mod(>I<b>B<)>
 209
 210 The basic algorithms.  The argument I<b> may be any value acceptable to
 211 the B<new()> constructor.
 212
 213 In an array context, the B<div()> method returns a two values: the
 214 quotient and remainder.  The quotient returned is the I<floor> of the
 215 true quotient: the remainder therefore has the same sign as the divisor.
 216 This is usually the right result for number-theoretic purposes.
 217
 218 =item I<a>B<-E<gt>sqr()>
 219
 220 Returns the square of its argument.  Usually faster than multiplying it
 221 by itself.
 222
 223 =item I<a>B<-E<gt>exp(>I<b>B<)>
 224
 225 Returns the result I<a>^I<b>.  Theoretically, I<b> can be a
 226 multiprecision integer, but the result will be impossibly huge if this
 227 is the case.  The exponent I<b> may not be negative.
 228
 229 =item I<a>B<-E<gt>sqrt()>
 230
 231 Returns the integer square-root of I<a> -- i.e., the largest integer
 232 less than or equal to the true square root.
 233
 234 =item I<a>B<-E<gt>eq(>I<b>B<)>
 235
 236 Returns true if I<a> and I<b> are equal; or false otherwise.
 237
 238 =item I<a>B<-E<gt>cmp(>I<b>B<)>
 239
 240 Returns -1, 0 or +1 according to whether I<a> is less than, equal to or
 241 greater than I<b>.
 242
 243 =item I<a>B<-E<gt>and(>I<b>B<)>
 244
 245 =item I<a>B<-E<gt>and2c(>I<b>B<)>
 246
 247 =item I<a>B<-E<gt>or(>I<b>B<)>
 248
 249 =item I<a>B<-E<gt>or2c(>I<b>B<)>
 250
 251 =item I<a>B<-E<gt>xor(>I<b>B<)>
 252
 253 =item I<a>B<-E<gt>xor2c(>I<b>B<)>
 254
 255 =item I<a>B<-E<gt>nand(>I<b>B<)>
 256
 257 =item I<a>B<-E<gt>nand2c(>I<b>B<)>
 258
 259 =item I<a>B<-E<gt>nor(>I<b>B<)>
 260
 261 =item I<a>B<-E<gt>nor2c(>I<b>B<)>
 262
 263 =item I<a>B<-E<gt>not()>
 264
 265 =item I<a>B<-E<gt>not2c()>
 266
 267 Standard bitwise operators.  The unadorned methods ignore the sign of
 268 their operands and use only the absolute values.  The B<2c> versions use
 269 a two's complement representation, with the sign bit repeated
 270 infinitely.
 271
 272 =item I<a>B<-E<gt>lsl(>I<n>B<)>
 273
 274 =item I<a>B<-E<gt>lsl2c(>I<n>B<)>
 275
 276 =item I<a>B<-E<gt>lsr(>I<n>B<)>
 277
 278 =item I<a>B<-E<gt>lsr2c(>I<n>B<)>
 279
 280 Standard shifting operators.  The unadorned methods treat only absolute
 281 values, while the B<2c> versions use a two's complement representation,
 282 with the sign bit repeated infinitely.
 283
 284 =item I<a>B<-E<gt>setbit(>I<n>B<)>
 285
 286 =item I<a>B<-E<gt>setbit2c(>I<n>B<)>
 287
 288 =item I<a>B<-E<gt>clearbit(>I<n>B<)>
 289
 290 =item I<a>B<-E<gt>clearbit2c(>I<n>B<)>
 291
 292 Returns a copy of the argument I<a> with bit I<n> set or clear.  The
 293 unadorned methods treat only absolute values, while the B<2c> variants
 294 use a two's complement representation with the sign bit repeated
 295 infinitely.
 296
 297 =item I<a>B<-E<gt>testbit(>I<n>B<)>
 298
 299 =item I<a>B<-E<gt>testbit2c(>I<n>B<)>
 300
 301 Returns true or false according to whether I<a> has bit I<n> set or
 302 clear.  The unadorned methods treat only absolute values, while the
 303 B<2c> variant uses a two's complement representation with the sign bit
 304 repeated infinitely.
 305
 306 =item I<a>B<-E<gt>copy()>
 307
 308 Returns a copy of I<a>.  Not useful: use assignment instead.
 309
 310 =item I<a>B<-E<gt>gcd(>I<b>B<)>
 311
 312 Returns the greatest common divisor of I<a> and I<b>.  This will never
 313 be negative.  In a list context, it also returns two further results,
 314 I<u> and I<v>: if the GCD is I<g> then we have I<a> I<u> + I<b> I<v> =
 315 I<g>.  Furthermore, I<v> will have the same sign as I<b>.
 316
 317 =item I<a>B<-E<gt>odd()>
 318
 319 Returns a pair of numbers I<s> and I<t>, so that I<a> = I<t> << I<s>,
 320 with I<t> odd and I<s> as large as possible.  I<t> will be
 321 multiprecision; I<s> will be a standard Perl integer.
 322
 323 =item I<a>B<-E<gt>modexp(>I<b>B<,> I<n>B<)>
 324
 325 Returns I<b>^I<n> mod I<a>.
 326
 327 =item I<a>B<-E<gt>modinv(>I<b>B<)>
 328
 329 Returns the inverse of I<b> modulo I<a>.  If no inverse exists then
 330 report an error.
 331
 332 =item I<a>B<-E<gt>modsqrt(>I<b>B<)>
 333
 334 If I<a> is prime, and I<b> is a quadratic residue mod I<a>, then return
 335 a square root of I<b> mod I<a>.  If I<a> is not prime, does something
 336 arbitrary; if I<b> is a nonresidue then report an error.
 337
 338 =item I<a>B<-E<gt>jac(>I<b>B<)>
 339
 340 Returns the Jacobi symbol (I<b>/I<a>).  If I<a> is prime, then this is
 341 I<b>^((I<a> - 1)/2), i.e., 0 if I<b> is a multiple of I<a>, +1 if I<b>
 342 is a quadratic residue modulo I<a>, or -1 if I<b> is a quadratic
 343 nonresidue mod I<a>.
 344
 345 =item I<a>B<-E<gt>primep(>[I<rng>]I<)>
 346
 347 Returns true or false, depending on whether I<a> is (probably) prime.
 348 If I<rng> is specified, it must be a random number generator -- see
 349 Catacomb::Crypto(3).
 350
 351 =item I<a>B<-E<gt>bits()>
 352
 353 Returns the smallest number of bits required to represent the integer
 354 I<a>.
 355
 356 =item I<a>B<-E<gt>octets()>
 357
 358 Returns the smallest number of bytes required to represent the integer
 359 I<a>, ignoring sign.
 360
 361 =item I<a>B<-E<gt>octets2c()>
 362
 363 Returns the smallest number of bytes required to represent the integer
 364 I<a> as two's complement.  This may be one greater than the result
 365 returned by B<octets()> in the case where the top bit of I<a> is the top
 366 bit of an octet.
 367
 368 =item I<a>B<-E<gt>storeb(>[I<nbytes>]B<)>
 369
 370 =item I<a>B<-E<gt>storel(>[I<nbytes>]B<)>
 371
 372 Return (the absolute value of) I<a> as a raw base-256 string in big- or
 373 little-endian order.  The returned string has length I<nbytes>, which
 374 defaults to the smallest nonzero length necessary to represent the
 375 argument.  If I<nbytes> is too small, more significant bits are silently
 376 discarded.  The sign is ignored.
 377
 378 =item I<a>B<-E<gt>storeb2c(>[I<nbytes>]B<)>
 379
 380 =item I<a>B<-E<gt>storel2c(>[I<nbytes>]B<)>
 381
 382 Return I<a> as a raw two's complement base-256 string in big- or
 383 little-endian order.    The returned string has length I<nbytes>, which
 384 defaults to the smallest nonzero length necessary to represent the
 385 argument.  If I<nbytes> is too small, more significant bits are silently
 386 discarded.  An alternative way to look at this operation is that the
 387 returned value is congruent to I<a> modulo 2^(8 I<nbytes>).
 388
 389 =item I<a>B<-E<gt>tostring(>[I<radix>]B<)>
 390
 391 Return I<a> expressed as a base-I<radix> string.  The default I<radix>
 392 is 10.  The result may be preceded by a minus sign if I<a> is negative.
 393 No leading zeroes or other radix prefix are prepended.
 394
 395 =item I<a>B<-E<gt>toint()>
 396
 397 Returns I<a> as a Perl integer.  If I<a> cannot be represented as a Perl
 398 integer then an undefined result is returned.
 399
 400 =back
 401
 402 =head2 Barrett reduction
 403
 404 Barrett reduction is an efficient way of doing modular reduction on
 405 numbers which aren't too much bigger than the modulus.  Barrett
 406 reduction isn't as efficient as Montgomery reduction (see below) but is
 407 simpler and works on even moduli.
 408
 409 The precomputed information used to perform Barrett reduction are stored
 410 in an object of type B<Catacomb::MP::Barrett>.
 411
 412 =over
 413
 414 =item B<Catacomb::MP::Barrett-E<gt>new(>I<m>B<)>
 415
 416 =item I<m>B<-E<gt>barrett()>
 417
 418 Create a new Barrett reduction context, set up for reducing modulo I<m>.
 419
 420 =item I<b>B<-E<gt>m()>
 421
 422 Returns the modulus stored in the reduction context I<b>.
 423
 424 =item I<b>B<-E<gt>reduce(>I<x>B<)>
 425
 426 Let I<m> be the modulus stored in the reduction context I<b>.  Then, if
 427 I<x> is nonnegative and less then I<m>^2, returns I<x> mod I<m>.
 428 Otherwise the return value is undefined.
 429
 430 =item I<b>B<-E<gt>exp(>I<x>B<,> I<n>B<)>
 431
 432 Let I<m> be the modulus stored in the reduction context I<b>.  Then
 433 return I<x>^I<n> mod I<m>.  If I<n> is negative then I<x> must have an
 434 inverse modulo I<m>; otherwise you'll get a big mess.
 435
 436 =back
 437
 438 =head2 Montgomery reduction
 439
 440 Montgomery reduction is a clever and efficient way of doing modular
 441 reduction on numbers which aren't too much bigger than the modulus.  It
 442 only works if the modulus is positive and odd, and it's a little
 443 complicated.
 444
 445 Let I<m> be the modulus in question.  There is a value I<R> which is
 446 computed in some way from I<m>.  The Montgomery reduction operation,
 447 given a number I<x>, actually returns I<x> I<R>^(-1) mod I<m>, which
 448 doesn't sound useful.  However, if you multiply all your numbers by a
 449 factor of I<R> then the cleverness becomes clear: if you reduce I<x>
 450 I<y> I<R>^2, you get I<x> I<y> I<R> mod I<m>.  Indeed, there's an
 451 efficient multiply-and-reduce operation which takes two operands, each
 452 with a factor of I<R> and returns a result with the factor of I<R>.  One
 453 more reduction step drops off the final factor of I<R> to give you the
 454 real answer.  Getting numbers into the required form involves
 455 multiplying by I<R>^2 mod I<m> and reducing: conveniently, I<R>^2 mod
 456 I<m> is precomputed.  Addition and subtraction leave the factor of I<R>
 457 where it was, so you can just test-and-subtract to reduce.  One final
 458 tip, if you're just multiplying two numbers, multiply them together
 459 first, and then multiply the result by I<R>^2 to fix the answer.
 460
 461 If that all sounded too difficult, then you can use the B<in()> method to
 462 convert to internal form, B<mul()> to multiply numbers in internal form,
 463 B<expr()> and B<mexpr()> to do modular exponentiation, and B<out()> to
 464 convert the result to external form.
 465
 466 The precomputed information used to perform Montgomery reduction are
 467 stored in an object of type B<Catacomb::MP::Mont>.
 468
 469 =over
 470
 471 =item B<Catacomb::MP::Mont-E<gt>new(>I<m>B<)>
 472
 473 =item I<m>B<-E<gt>mont()>
 474
 475 Constructs a Montgomery reduction context for reduction modulo I<m>.
 476 Returns B<undef> unless I<m> is an odd positive integer.
 477
 478 =item I<mm>B<-E<gt>r()>
 479
 480 Returns the Montgomery reduction factor I<R>.
 481
 482 =item I<mm>B<-E<gt>r2()>
 483
 484 Returns the Montgomerization factor I<R>^2.
 485
 486 =item I<mm>B<-E<gt>m()>
 487
 488 Returns the modulus I<m>.
 489
 490 =item I<mm>B<-E<gt>in(>I<x>B<)>
 491
 492 Returns the Montgomerized form of I<x>, i.e., I<x> I<R> mod I<m>.  I<x>
 493 can be any integer.
 494
 495 =item I<mm>B<-E<gt>mul(>I<x>B<,> I<y>B<)>
 496
 497 Montgomery multiplication.  If I<x> and I<y> are Montgomerized, then
 498 returns their Montgomerized product; i.e., I<x> I<y> I<R>^(-1) mod I<m>.
 499
 500 =item I<mm>B<-E<gt>expr(>I<x>B<,> I<n>B<)>
 501
 502 Montgomery exponentiation.  If I<x> is Montgomerized, then returns the
 503 Montgomerized value of I<x>^I<n> mod I<m>; i.e., if I<x> = I<x'> I<R>,
 504 it returns I<x'>^I<n> I<R> mod I<m>.  Here, if I<n> is negative, then
 505 I<x> must have an inverse modulo I<m>; otherwise there'll be a big mess.
 506
 507 =item I<mm>B<-E<gt>mexpr(>I<x0>B<,> I<n0>B<,> I<x1>B<,> I<n1>B<,> ...B<)>
 508
 509 Simultaneous Montgomery exponentiation.  If the I<xi> are Montgomerized,
 510 then returns the Montgomerized value of I<x0>^I<n0> I<x1>^I<n1> ... mod
 511 I<m>; i.e., if I<xi> = I<xi'> I<R>, it returns I<x0'>^I<n0> I<x1'>^I<n1>
 512 ... I<R> mod I<m>.  Here, if some I<ni> is negative, then the
 513 corresponding I<xi> must have an inverse modulo I<m>; otherwise there'll
 514 be a big mess.
 515
 516 =item I<mm>B<-E<gt>reduce(>I<x>B<)>
 517
 518 =item I<mm>B<-E<gt>out(>I<x>B<)>
 519
 520 Returns the unMontgomerized form of I<x>; i.e., I<x> I<R>^(-1) mod I<m>.
 521
 522 =item I<mm>B<-E<gt>expr(>I<x>B<,> I<n>B<)>
 523
 524 Modular exponentiation.  Returns I<x>^I<n> mod I<m>.  Here, if I<n> is
 525 negative, then I<x> must have an inverse modulo I<m>; otherwise there'll
 526 be a big mess.
 527
 528 =item I<mm>B<-E<gt>mexpr(>I<x0>B<,> I<n0>B<,> I<x1>B<,> I<n1>B<,> ...B<)>
 529
 530 Simultaneous modular exponentiation.  Returns I<x0>^I<n0> I<x1>^I<n1>
 531 ... mod I<m>.  Here, if some I<ni> is negative, then the corresponding
 532 I<xi> must have an inverse modulo I<m>; otherwise there'll be a big
 533 mess.
 534
 535 =back
 536
 537 =head2 Nice prime reduction
 538
 539 For some numbers, we can do modular reduction quite rapidly.
 540 Specifically, these are numbers of the form
 541
 542 =over
 543
 544 2^I<n0> - 2^I<n1> +/- 2^I<n2> +/- ... +/- 2^I<nk>
 545
 546 =back
 547
 548 where I<n0> > I<n1> > ... I<nk>, for small values of I<k>.  We call such
 549 numbers `nice' (that's specific to Catacomb, not a term in general use).
 550 Usually, numbers of interest to us will be prime; hence, we shall speak
 551 of `nice primes'.
 552
 553 Information for efficient reduction modulo a nice number is stored in an
 554 object of type B<Catacomb::MP::Reduce>.
 555
 556 =over
 557
 558 =item B<Catacomb::MP::Reduce-E<gt>new(>I<m>B<)>
 559
 560 =item I<m>B<-E<gt>mkreduce()>
 561
 562 Create a new nice-modulus reduction context, set up for reducing modulo
 563 I<m>.
 564
 565 =item I<r>B<-E<gt>m()>
 566
 567 Returns the modulus stored in the reduction context I<r>.
 568
 569 =item I<r>B<-E<gt>reduce(>I<x>B<)>
 570
 571 Let I<m> be the modulus stored in the reduction context I<r>.  Then, if
 572 I<x>, returns I<x> mod I<m>.  Otherwise the return value is undefined.
 573
 574 =item I<r>B<-E<gt>exp(>I<x>B<,> I<n>B<)>
 575
 576 Let I<m> be the modulus stored in the reduction context I<r>.  Then
 577 return I<x>^I<n> mod I<m>.  If I<n> is negative then I<x> must have an
 578 inverse modulo I<m>; otherwise you'll get a big mess.
 579
 580 =back
 581
 582 =head2 Chinese Remainder Theorem solution
 583
 584 Catacomb can solve simultaneous congruence problems, i.e., of the form
 585 I<x> = I<ri> (mod I<ni>) using the Chinese Remainder Theorem (CRT).  It
 586 is required that the I<ni> be positive and pairwise relatively prime;
 587 otherwise you'll get an unpleasant mess.
 588
 589 =over
 590
 591 =item B<Catacomb::MP::CRT-E<gt>new(>I<n0>B<,> I<n1>B<,> ...B<)>
 592
 593 Construct a new CRT solving context, for solving congruences mod the
 594 I<ni>, and return it.
 595
 596 =item I<crt>B<-E<gt>product()>
 597
 598 Returns the product of the moduli I<ni>.  In a scalar context, return
 599 the number of moduli.
 600
 601 =item I<crt>B<-E<gt>moduli()>
 602
 603 Returns a list of the I<ni>, as passed to B<new()>.
 604
 605 =item I<crt>B<-E<gt>solve(>I<r0>B<,> I<r1>B<,>, ...B<)>
 606
 607 Returns the unique answer I<x> (modulo the product of the I<ni>) to the
 608 congruences I<x> = I<ri> (mod I<ni>).  You will get an unhelpful answer
 609 if any I<ri> >= I<ni>, and an error if you pass the wrong number of
 610 I<ri> arguments.
 611
 612 =back
 613
 614 =head1 SEE ALSO
 615
 616 Catacomb(3).
 617
 618 =head1 AUTHOR
 619
 620 Mark Wooding, <mdw@nsict.org>
 621