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

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