| 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 | |