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

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