chiark - git - mdw - catacomb/blob - mp.h

   1 /* -*-c-*-
   2  *
   3  * $Id: mp.h,v 1.11 2001/04/03 19:36:05 mdw Exp $
   4  *
   5  * Simple multiprecision arithmetic
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: mp.h,v $
  33  * Revision 1.11  2001/04/03 19:36:05  mdw
  34  * Add some simple bitwise operations so that Perl can use them.
  35  *
  36  * Revision 1.10  2000/10/08 12:03:16  mdw
  37  * Provide @mp_eq@ and @MP_EQ@ for rapidly testing equality of two
  38  * integers.
  39  *
  40  * Revision 1.9  2000/07/29 17:03:31  mdw
  41  * Add support for left-to-right bitscanning, for use in modular
  42  * exponentiation.
  43  *
  44  * Revision 1.8  2000/06/22 19:02:01  mdw
  45  * Add new functions.
  46  *
  47  * Revision 1.7  2000/06/17 11:45:09  mdw
  48  * Major memory management overhaul.  Added arena support.  Use the secure
  49  * arena for secret integers.  Replace and improve the MP management macros
  50  * (e.g., replace MP_MODIFY by MP_DEST).
  51  *
  52  * Revision 1.6  1999/12/10 23:19:46  mdw
  53  * Minor bugfixes.  New interface for suggested destinations.
  54  *
  55  * Revision 1.5  1999/11/22 20:50:37  mdw
  56  * Add support for computing Jacobi symbols.
  57  *
  58  * Revision 1.4  1999/11/21 22:13:02  mdw
  59  * Add mp version of MPX_BITS.
  60  *
  61  * Revision 1.3  1999/11/19 13:19:14  mdw
  62  * Fix const annotation.
  63  *
  64  * Revision 1.2  1999/11/17 18:02:16  mdw
  65  * New multiprecision integer arithmetic suite.
  66  *
  67  */
  68
  69 #ifndef CATACOMB_MP_H
  70 #define CATACOMB_MP_H
  71
  72 #ifdef __cplusplus
  73   extern "C" {
  74 #endif
  75
  76 /*----- Header files ------------------------------------------------------*/
  77
  78 #include <assert.h>
  79 #include <string.h>
  80
  81 #include <mLib/sub.h>
  82
  83 #ifndef CATACOMB_MPW_H
  84 #  include "mpw.h"
  85 #endif
  86
  87 #ifndef CATACOMB_ARENA_H
  88 #  include "arena.h"
  89 #endif
  90
  91 #ifndef CATACOMB_MPARENA_H
  92 #  include "mparena.h"
  93 #endif
  94
  95 #ifndef CATACOMB_MPX_H
  96 #  include "mpx.h"
  97 #endif
  98
  99 /*----- Data structures ---------------------------------------------------*/
 100
 101 typedef struct mp {
 102   mpw *v, *vl;
 103   size_t sz;
 104   mparena *a;
 105   unsigned f;
 106   unsigned ref;
 107 } mp;
 108
 109 #define MP_NEG 1u
 110 #define MP_BURN 2u
 111 #define MP_CONST 4u
 112 #define MP_UNDEF 8u
 113 #define MP_DESTROYED 16u
 114
 115 /*----- Useful constants --------------------------------------------------*/
 116
 117 extern mp mp_const[];
 118
 119 #define MP_ZERO  (&mp_const[0])
 120 #define MP_ONE   (&mp_const[1])
 121 #define MP_TWO   (&mp_const[2])
 122 #define MP_THREE (&mp_const[3])
 123 #define MP_FOUR  (&mp_const[4])
 124 #define MP_FIVE  (&mp_const[5])
 125 #define MP_TEN   (&mp_const[6])
 126 #define MP_256   (&mp_const[7])
 127 #define MP_MONE  (&mp_const[8])
 128
 129 #define MP_NEW ((mp *)0)
 130 #define MP_NEWSEC (&mp_const[9])
 131
 132 /*----- Trivial macros ----------------------------------------------------*/
 133
 134 /* --- @MP_LEN@ --- *
 135  *
 136  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 137  *
 138  * Returns:     Length of the integer, in words.
 139  */
 140
 141 #define MP_LEN(m) ((m)->vl - ((m)->v))
 142
 143 /*----- Memory management and reference counting --------------------------*/
 144
 145 /* --- @mp_new@ --- *
 146  *
 147  * Arguments:   @size_t sz@ = size of vector required
 148  *              @unsigned f@ = flags to set
 149  *
 150  * Returns:     Pointer to a new MP structure.
 151  *
 152  * Use:         Allocates a new multiprecision integer.  The data space is
 153  *              allocated from either the standard global or secret arena,
 154  *              depending on the initial flags requested.
 155  */
 156
 157 extern mp *mp_new(size_t /*sz*/, unsigned /*f*/);
 158
 159 /* --- @mp_create@ --- *
 160  *
 161  * Arguments:   @size_t sz@ = size of vector required
 162  *
 163  * Returns:     Pointer to pristine new MP structure with enough memory
 164  *              bolted onto it.
 165  *
 166  * Use:         Creates a new multiprecision integer with indeterminate
 167  *              contents.  The integer has a single reference.
 168  */
 169
 170 extern mp *mp_create(size_t /*sz*/);
 171
 172 /* --- @mp_createsecure@ --- *
 173  *
 174  * Arguments:   @size_t sz@ = size of vector required
 175  *
 176  * Returns:     Pointer to pristine new MP structure with enough memory
 177  *              bolted onto it.
 178  *
 179  * Use:         Creates a new multiprecision integer with indeterminate
 180  *              contents.  The integer has a single reference.  The integer's
 181  *              data space is allocated from the secure arena.  Its burn flag
 182  *              is set.
 183  */
 184
 185 extern mp *mp_createsecure(size_t /*sz*/);
 186
 187 /* --- @mp_build@ --- *
 188  *
 189  * Arguments:   @mp *m@ = pointer to an MP block to fill in
 190  *              @mpw *v@ = pointer to a word array
 191  *              @mpw *vl@ = pointer just past end of array
 192  *
 193  * Returns:     ---
 194  *
 195  * Use:         Creates a multiprecision integer representing some smallish
 196  *              number.  You must provide storage for the number and dispose
 197  *              of it when you've finished with it.  The number is marked as
 198  *              constant while it exists.
 199  */
 200
 201 extern void mp_build(mp */*m*/, mpw */*v*/, mpw */*vl*/);
 202
 203 /* --- @mp_destroy@ --- *
 204  *
 205  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 206  *
 207  * Returns:     ---
 208  *
 209  * Use:         Destroys a multiprecision integer. The reference count isn't
 210  *              checked.  Don't use this function if you don't know what
 211  *              you're doing: use @mp_drop@ instead.
 212  */
 213
 214 extern void mp_destroy(mp */*m*/);
 215
 216 /* --- @mp_copy@ --- *
 217  *
 218  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 219  *
 220  * Returns:     A copy of the given multiprecision integer.
 221  *
 222  * Use:         Copies the given integer.  In fact you just get another
 223  *              reference to the same old one again.
 224  */
 225
 226 extern mp *mp_copy(mp */*m*/);
 227
 228 #define MP_COPY(m) ((m)->ref++, (m))
 229
 230 /* --- @mp_drop@ --- *
 231  *
 232  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 233  *
 234  * Returns:     ---
 235  *
 236  * Use:         Drops a reference to an integer which isn't wanted any more.
 237  *              If there are no more references, the integer is destroyed.
 238  */
 239
 240 extern void mp_drop(mp */*m*/);
 241
 242 #define MP_DROP(m) do {                                                 \
 243   mp *_mm = (m);                                                        \
 244   _mm->ref--;                                                           \
 245   if (_mm->ref == 0 && !(_mm->f & MP_CONST))                            \
 246     mp_destroy(_mm);                                                    \
 247 } while (0)
 248
 249 /* --- @mp_split@ --- *
 250  *
 251  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 252  *
 253  * Returns:     A reference to the same integer, possibly with a different
 254  *              address.
 255  *
 256  * Use:         Splits off a modifiable version of the integer referred to.
 257  */
 258
 259 extern mp *mp_split(mp */*m*/);
 260
 261 #define MP_SPLIT(m) do {                                                \
 262   mp *_m = (m);                                                         \
 263   if ((_m->f & MP_CONST) || _m->ref > 1) {                              \
 264     size_t _len = MP_LEN(_m);                                           \
 265     mp *_mm = mp_new(_len, _m->f);                                      \
 266     if (!(_m->f & MP_UNDEF))                                            \
 267       memcpy(_mm->v, _m->v, MPWS(_len));                                \
 268     _m->ref--;                                                          \
 269     _m = _mm;                                                           \
 270   }                                                                     \
 271   (m) = _m;                                                             \
 272 } while (0)
 273
 274 /* --- @mp_resize@ --- *
 275  *
 276  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 277  *              @size_t sz@ = new size
 278  *
 279  * Returns:     ---
 280  *
 281  * Use:         Resizes the vector containing the integer's digits.  The new
 282  *              size must be at least as large as the current integer's
 283  *              length.  This isn't really intended for client use.
 284  */
 285
 286 extern void mp_resize(mp */*m*/, size_t /*sz*/);
 287
 288 #define MP_RESIZE(m, ssz) do {                                          \
 289   mp *_m = (m);                                                         \
 290   size_t _sz = (ssz);                                                   \
 291   mparena *_a = (_m->f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL;    \
 292   mpw *_v;                                                              \
 293   size_t _len = MP_LEN(_m);                                             \
 294   assert(((void)"can't make size less than length", _sz >= _len));      \
 295   _v = mpalloc(_a, _sz);                                                \
 296   if (!(_m->f & MP_UNDEF))                                              \
 297     memcpy(_v, _m->v, MPWS(_len));                                      \
 298   if (_m->f & MP_BURN)                                                  \
 299     memset(_m->v, 0, MPWS(_m->sz));                                     \
 300   mpfree(_m->a, _m->v);                                                 \
 301   _m->a = _a;                                                           \
 302   _m->v = _v;                                                           \
 303   _m->vl = _v + _len;                                                   \
 304 } while (0)
 305
 306 /* --- @mp_ensure@ --- *
 307  *
 308  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 309  *              @size_t sz@ = required size
 310  *
 311  * Returns:     ---
 312  *
 313  * Use:         Ensures that the integer has enough space for @sz@ digits.
 314  *              The value is not changed.
 315  */
 316
 317 extern void mp_ensure(mp */*m*/, size_t /*sz*/);
 318
 319 #define MP_ENSURE(m, ssz) do {                                          \
 320   mp *_m = (m);                                                         \
 321   size_t _ssz = (ssz);                                                  \
 322   size_t _len = MP_LEN(_m);                                             \
 323   if (_ssz >= _len) {                                                   \
 324     if (_ssz > _m->sz)                                                  \
 325       mp_resize(_m, _ssz);                                              \
 326     if (!(_m->f & MP_UNDEF) && _ssz > _len)                             \
 327       memset(_m->vl, 0, MPWS(_ssz - _len));                             \
 328     _m->vl = _m->v + _ssz;                                              \
 329   }                                                                     \
 330 } while (0)
 331
 332 /* --- @mp_dest@ --- *
 333  *
 334  * Arguments:   @mp *m@ = a suggested destination integer
 335  *              @size_t sz@ = size required for result, in digits
 336  *              @unsigned f@ = various flags
 337  *
 338  * Returns:     A pointer to an appropriate destination.
 339  *
 340  * Use:         Converts a suggested destination into a real destination with
 341  *              the required properties.  If the real destination is @d@,
 342  *              then the following properties will hold:
 343  *
 344  *                * @d@ will have exactly one reference.
 345  *
 346  *                * If @m@ is not @MP_NEW@, then the contents of @m@ will not
 347  *                  change, unless @f@ has the @MP_UNDEF@ flag set.
 348  *
 349  *                * If @m@ is not @MP_NEW@, then he reference count of @m@ on
 350  *                  entry is equal to the sum of the counts of @d@ and @m@ on
 351  *                  exit.
 352  *
 353  *                * The size of @d@ will be at least @sz@.
 354  *
 355  *                * If @f@ has the @MP_BURN@ flag set, then @d@ will be
 356  *                  allocated from @MPARENA_SECURE@.
 357  *
 358  *              Understanding this function is crucial to using Catacomb's
 359  *              multiprecision integer library effectively.
 360  */
 361
 362 extern mp *mp_dest(mp */*m*/, size_t /*sz*/, unsigned /*f*/);
 363
 364 #define MP_DEST(m, ssz, f) do {                                         \
 365   mp *_m = (m);                                                         \
 366   size_t _ssz = (ssz);                                                  \
 367   unsigned _f = (f);                                                    \
 368   _m = mp_dest(_m, _ssz, _f);                                           \
 369   (m) = _m;                                                             \
 370 } while (0)
 371
 372 /*----- Size manipulation -------------------------------------------------*/
 373
 374 /* --- @mp_shrink@ --- *
 375  *
 376  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 377  *
 378  * Returns:     ---
 379  *
 380  * Use:         Reduces the recorded length of an integer.  This doesn't
 381  *              reduce the amount of memory used, although it can improve
 382  *              performance a bit.  To reduce memory, use @mp_minimize@
 383  *              instead.  This can't change the value of an integer, and is
 384  *              therefore safe to use even when there are multiple
 385  *              references.
 386  */
 387
 388 extern void mp_shrink(mp */*m*/);
 389
 390 #define MP_SHRINK(m) do {                                               \
 391   mp *_mm = (m);                                                        \
 392   MPX_SHRINK(_mm->v, _mm->vl);                                          \
 393   if (!MP_LEN(_mm))                                                     \
 394     _mm->f &= ~MP_NEG;                                                  \
 395 } while (0)
 396
 397 /* --- @mp_minimize@ --- *
 398  *
 399  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 400  *
 401  * Returns:     ---
 402  *
 403  * Use:         Reduces the amount of memory an integer uses.  It's best to
 404  *              do this to numbers which aren't going to change in the
 405  *              future.
 406  */
 407
 408 extern void mp_minimize(mp */*m*/);
 409
 410 /*----- Bit scanning ------------------------------------------------------*/
 411
 412 #ifndef CATACOMB_MPSCAN_H
 413 #  include "mpscan.h"
 414 #endif
 415
 416 /* --- @mp_scan@ --- *
 417  *
 418  * Arguments:   @mpscan *sc@ = pointer to bitscanner block
 419  *              @const mp *m@ = pointer to a multiprecision integer
 420  *
 421  * Returns:     ---
 422  *
 423  * Use:         Initializes a bitscanner on a multiprecision integer.
 424  */
 425
 426 extern void mp_scan(mpscan */*sc*/, const mp */*m*/);
 427
 428 #define MP_SCAN(sc, m) do {                                             \
 429   const mp *_mm = (m);                                                  \
 430   mpscan *_sc = (sc);                                                   \
 431   MPSCAN_INITX(_sc, _mm->v, _mm->vl);                                   \
 432 } while (0)
 433
 434 /* --- @mp_rscan@ --- *
 435  *
 436  * Arguments:   @mpscan *sc@ = pointer to bitscanner block
 437  *              @const mp *m@ = pointer to a multiprecision integer
 438  *
 439  * Returns:     ---
 440  *
 441  * Use:         Initializes a reverse bitscanner on a multiprecision
 442  *              integer.
 443  */
 444
 445 extern void mp_rscan(mpscan */*sc*/, const mp */*m*/);
 446
 447 #define MP_RSCAN(sc, m) do {                                            \
 448   const mp *_mm = (m);                                                  \
 449   mpscan *_sc = (sc);                                                   \
 450   MPSCAN_RINITX(_sc, _mm->v, _mm->vl);                                  \
 451 } while (0)
 452
 453 /* --- Other bitscanning aliases --- */
 454
 455 #define mp_step mpscan_step
 456 #define mp_bit mpscan_bit
 457 #define mp_rstep mpscan_rstep
 458 #define mp_rbit mpscan_rbit
 459
 460 #define MP_STEP MPSCAN_STEP
 461 #define MP_BIT MPSCAN_BIT
 462 #define MP_RSTEP MPSCAN_RSTEP
 463 #define MP_RBIT MPSCAN_RBIT
 464
 465 /*----- Loading and storing -----------------------------------------------*/
 466
 467 /* --- @mp_octets@ --- *
 468  *
 469  * Arguments:   @const mp *m@ = a multiprecision integer
 470  *
 471  * Returns:     The number of octets required to represent @m@.
 472  *
 473  * Use:         Calculates the external storage required for a multiprecision
 474  *              integer.
 475  */
 476
 477 extern size_t mp_octets(const mp */*m*/);
 478
 479 /* --- @mp_bits@ --- *
 480  *
 481  * Arguments:   @const mp *m@ = a multiprecision integer
 482  *
 483  * Returns:     The number of bits required to represent @m@.
 484  *
 485  * Use:         Calculates the external storage required for a multiprecision
 486  *              integer.
 487  */
 488
 489 extern unsigned long mp_bits(const mp */*m*/);
 490
 491 /* --- @mp_loadl@ --- *
 492  *
 493  * Arguments:   @mp *d@ = destination
 494  *              @const void *pv@ = pointer to source data
 495  *              @size_t sz@ = size of the source data
 496  *
 497  * Returns:     Resulting multiprecision number.
 498  *
 499  * Use:         Loads a multiprecision number from an array of octets.  The
 500  *              first byte in the array is the least significant.  More
 501  *              formally, if the bytes are %$b_0, b_1, \ldots, b_{n-1}$%
 502  *              then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
 503  */
 504
 505 extern mp *mp_loadl(mp */*d*/, const void */*pv*/, size_t /*sz*/);
 506
 507 /* --- @mp_storel@ --- *
 508  *
 509  * Arguments:   @const mp *m@ = source
 510  *              @void *pv@ = pointer to output array
 511  *              @size_t sz@ = size of the output array
 512  *
 513  * Returns:     ---
 514  *
 515  * Use:         Stores a multiprecision number in an array of octets.  The
 516  *              first byte in the array is the least significant.  If the
 517  *              array is too small to represent the number, high-order bits
 518  *              are truncated; if the array is too large, high order bytes
 519  *              are filled with zeros.  More formally, if the number is
 520  *              %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
 521  *              then the array is %$b_0, b_1, \ldots, b_{n-1}$%.
 522  */
 523
 524 extern void mp_storel(const mp */*m*/, void */*pv*/, size_t /*sz*/);
 525
 526 /* --- @mp_loadb@ --- *
 527  *
 528  * Arguments:   @mp *d@ = destination
 529  *              @const void *pv@ = pointer to source data
 530  *              @size_t sz@ = size of the source data
 531  *
 532  * Returns:     Resulting multiprecision number.
 533  *
 534  * Use:         Loads a multiprecision number from an array of octets.  The
 535  *              last byte in the array is the least significant.  More
 536  *              formally, if the bytes are %$b_{n-1}, b_{n-2}, \ldots, b_0$%
 537  *              then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
 538  */
 539
 540 extern mp *mp_loadb(mp */*d*/, const void */*pv*/, size_t /*sz*/);
 541
 542 /* --- @mp_storeb@ --- *
 543  *
 544  * Arguments:   @const mp *m@ = source
 545  *              @void *pv@ = pointer to output array
 546  *              @size_t sz@ = size of the output array
 547  *
 548  * Returns:     ---
 549  *
 550  * Use:         Stores a multiprecision number in an array of octets.  The
 551  *              last byte in the array is the least significant.  If the
 552  *              array is too small to represent the number, high-order bits
 553  *              are truncated; if the array is too large, high order bytes
 554  *              are filled with zeros.  More formally, if the number is
 555  *              %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
 556  *              then the array is %$b_{n-1}, b_{n-2}, \ldots, b_0$%.
 557  */
 558
 559 extern void mp_storeb(const mp */*m*/, void */*pv*/, size_t /*sz*/);
 560
 561 /*----- Simple arithmetic -------------------------------------------------*/
 562
 563 /* --- @mp_2c@ --- *
 564  *
 565  * Arguments:   @mp *d@ = destination
 566  *              @mp *a@ = source
 567  *
 568  * Returns:     Result, @a@ converted to two's complement notation.
 569  */
 570
 571 extern mp *mp_2c(mp */*d*/, mp */*a*/);
 572
 573 /* --- @mp_sm@ --- *
 574  *
 575  * Arguments:   @mp *d@ = destination
 576  *              @mp *a@ = source
 577  *
 578  * Returns:     Result, @a@ converted to the native signed-magnitude
 579  *              notation.
 580  */
 581
 582 extern mp *mp_sm(mp */*d*/, mp */*a*/);
 583
 584 /* --- @mp_lsl@ --- *
 585  *
 586  * Arguments:   @mp *d@ = destination
 587  *              @mp *a@ = source
 588  *              @size_t n@ = number of bits to move
 589  *
 590  * Returns:     Result, @a@ shifted left by @n@.
 591  */
 592
 593 extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/);
 594
 595 /* --- @mp_lsr@ --- *
 596  *
 597  * Arguments:   @mp *d@ = destination
 598  *              @mp *a@ = source
 599  *              @size_t n@ = number of bits to move
 600  *
 601  * Returns:     Result, @a@ shifted left by @n@.
 602  */
 603
 604 extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/);
 605
 606 /* --- @mp_eq@ --- *
 607  *
 608  * Arguments:   @const mp *a, *b@ = two numbers
 609  *
 610  * Returns:     Nonzero if the numbers are equal.
 611  */
 612
 613 extern int mp_eq(const mp */*a*/, const mp */*b*/);
 614
 615 #define MP_EQ(a, b)                                                     \
 616   ((((a)->f ^ (b)->f) & MP_NEG) == 0 &&                                 \
 617    mpx_ueq((a)->v, (a)->vl, (b)->v, (b)->vl))
 618
 619 /* --- @mp_cmp@ --- *
 620  *
 621  * Arguments:   @const mp *a, *b@ = two numbers
 622  *
 623  * Returns:     Less than, equal to or greater than zero, according to
 624  *              whether @a@ is less than, equal to or greater than @b@.
 625  */
 626
 627 extern int mp_cmp(const mp */*a*/, const mp */*b*/);
 628
 629 #define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0)
 630
 631 /* --- @mpx_and@, @mpx_or@, @mpx_xor@, @mpx_not@ --- *
 632  *
 633  * Arguments:   @mp *d@ = destination
 634  *              @mp *a, *b@ = sources
 635  *
 636  * Returns:     The result of the obvious bitwise operation.
 637  */
 638
 639 extern mp *mp_and(mp */*d*/, mp */*a*/, mp */*b*/);
 640 extern mp *mp_or(mp */*d*/, mp */*a*/, mp */*b*/);
 641 extern mp *mp_xor(mp */*d*/, mp */*a*/, mp */*b*/);
 642 extern mp *mp_not(mp */*d*/, mp */*a*/);
 643
 644 /* --- @mp_add@ --- *
 645  *
 646  * Arguments:   @mp *d@ = destination
 647  *              @mp *a, *b@ = sources
 648  *
 649  * Returns:     Result, @a@ added to @b@.
 650  */
 651
 652 extern mp *mp_add(mp */*d*/, mp */*a*/, mp */*b*/);
 653
 654 /* --- @mp_sub@ --- *
 655  *
 656  * Arguments:   @mp *d@ = destination
 657  *              @mp *a, *b@ = sources
 658  *
 659  * Returns:     Result, @b@ subtracted from @a@.
 660  */
 661
 662 extern mp *mp_sub(mp */*d*/, mp */*a*/, mp */*b*/);
 663
 664 /* --- @mp_mul@ --- *
 665  *
 666  * Arguments:   @mp *d@ = destination
 667  *              @mp *a, *b@ = sources
 668  *
 669  * Returns:     Result, @a@ multiplied by @b@.
 670  */
 671
 672 extern mp *mp_mul(mp */*d*/, mp */*a*/, mp */*b*/);
 673
 674 /* --- @mp_sqr@ --- *
 675  *
 676  * Arguments:   @mp *d@ = destination
 677  *              @mp *a@ = source
 678  *
 679  * Returns:     Result, @a@ squared.
 680  */
 681
 682 extern mp *mp_sqr(mp */*d*/, mp */*a*/);
 683
 684 /* --- @mp_div@ --- *
 685  *
 686  * Arguments:   @mp **qq, **rr@ = destination, quotient and remainder
 687  *              @mp *a, *b@ = sources
 688  *
 689  * Use:         Calculates the quotient and remainder when @a@ is divided by
 690  *              @b@.
 691  */
 692
 693 extern void mp_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/);
 694
 695 /* --- @mp_odd@ --- *
 696  *
 697  * Arguments:   @mp *d@ = pointer to destination integer
 698  *              @mp *m@ = pointer to source integer
 699  *              @size_t *s@ = where to store the power of 2
 700  *
 701  * Returns:     An odd integer integer %$t$% such that %$m = 2^s t$%.
 702  *
 703  * Use:         Computes a power of two and an odd integer which, when
 704  *              multiplied, give a specified result.  This sort of thing is
 705  *              useful in number theory quite often.
 706  */
 707
 708 extern mp *mp_odd(mp */*d*/, mp */*m*/, size_t */*s*/);
 709
 710 /*----- More advanced algorithms ------------------------------------------*/
 711
 712 /* --- @mp_sqrt@ --- *
 713  *
 714  * Arguments:   @mp *d@ = pointer to destination integer
 715  *              @mp *a@ = (nonnegative) integer to take square root of
 716  *
 717  * Returns:     The largest integer %$x$% such that %$x^2 \le a$%.
 718  *
 719  * Use:         Computes integer square roots.
 720  *
 721  *              The current implementation isn't very good: it uses the
 722  *              Newton-Raphson method to find an approximation to %$a$%.  If
 723  *              there's any demand for a better version, I'll write one.
 724  */
 725
 726 extern mp *mp_sqrt(mp */*d*/, mp */*a*/);
 727
 728 /* --- @mp_gcd@ --- *
 729  *
 730  * Arguments:   @mp **gcd, **xx, **yy@ = where to write the results
 731  *              @mp *a, *b@ = sources (must be nonzero)
 732  *
 733  * Returns:     ---
 734  *
 735  * Use:         Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
 736  *              @ax + by = gcd(a, b)@.  This is useful for computing modular
 737  *              inverses.  Neither @a@ nor @b@ may be zero.
 738  */
 739
 740 extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/,
 741                    mp */*a*/, mp */*b*/);
 742
 743 /* --- @mp_jacobi@ --- *
 744  *
 745  * Arguments:   @mp *a@ = an integer less than @n@
 746  *              @mp *n@ = an odd integer
 747  *
 748  * Returns:     @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
 749  *
 750  * Use:         Computes the Jacobi symbol.  If @n@ is prime, this is the
 751  *              Legendre symbol and is equal to 1 if and only if @a@ is a
 752  *              quadratic residue mod @n@.  The result is zero if and only if
 753  *              @a@ and @n@ have a common factor greater than one.
 754  */
 755
 756 extern int mp_jacobi(mp */*a*/, mp */*n*/);
 757
 758 /* --- @mp_modsqrt@ --- *
 759  *
 760  * Arguments:   @mp *d@ = destination integer
 761  *              @mp *a@ = source integer
 762  *              @mp *p@ = modulus (must be prime)
 763  *
 764  * Returns:     If %$a$% is a quadratic residue, a square root of %$a$%; else
 765  *              a null pointer.
 766  *
 767  * Use:         Returns an integer %$x$% such that %$x^2 \equiv a \pmod{p}$%,
 768  *              if one exists; else a null pointer.  This function will not
 769  *              work if %$p$% is composite: you must factor the modulus, take
 770  *              a square root mod each factor, and recombine the results
 771  *              using the Chinese Remainder Theorem.
 772  */
 773
 774 extern mp *mp_modsqrt(mp */*d*/, mp */*a*/, mp */*p*/);
 775
 776 /*----- Test harness support ----------------------------------------------*/
 777
 778 #include <mLib/testrig.h>
 779
 780 #ifndef CATACOMB_MPTEXT_H
 781 #  include "mptext.h"
 782 #endif
 783
 784 extern const test_type type_mp;
 785
 786 /*----- That's all, folks -------------------------------------------------*/
 787
 788 #ifdef __cplusplus
 789   }
 790 #endif
 791
 792 #endif