3 * $Id: mp.h,v 1.16 2002/10/15 22:57:22 mdw Exp $
5 * Simple multiprecision arithmetic
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.16 2002/10/15 22:57:22 mdw
34 * Handy new comparison macros.
36 * Revision 1.15 2002/10/15 19:18:31 mdw
37 * New operation to negate numbers.
39 * Revision 1.14 2002/10/15 00:19:40 mdw
40 * Bit setting and clearing functions.
42 * Revision 1.13 2002/10/06 22:52:50 mdw
43 * Pile of changes for supporting two's complement properly.
45 * Revision 1.12 2001/06/16 12:57:43 mdw
46 * Move the @mpmont_factor@ structure and rename it now that it's used for
47 * Barrett simultaneous exponentiation too.
49 * Revision 1.11 2001/04/03 19:36:05 mdw
50 * Add some simple bitwise operations so that Perl can use them.
52 * Revision 1.10 2000/10/08 12:03:16 mdw
53 * Provide @mp_eq@ and @MP_EQ@ for rapidly testing equality of two
56 * Revision 1.9 2000/07/29 17:03:31 mdw
57 * Add support for left-to-right bitscanning, for use in modular
60 * Revision 1.8 2000/06/22 19:02:01 mdw
63 * Revision 1.7 2000/06/17 11:45:09 mdw
64 * Major memory management overhaul. Added arena support. Use the secure
65 * arena for secret integers. Replace and improve the MP management macros
66 * (e.g., replace MP_MODIFY by MP_DEST).
68 * Revision 1.6 1999/12/10 23:19:46 mdw
69 * Minor bugfixes. New interface for suggested destinations.
71 * Revision 1.5 1999/11/22 20:50:37 mdw
72 * Add support for computing Jacobi symbols.
74 * Revision 1.4 1999/11/21 22:13:02 mdw
75 * Add mp version of MPX_BITS.
77 * Revision 1.3 1999/11/19 13:19:14 mdw
78 * Fix const annotation.
80 * Revision 1.2 1999/11/17 18:02:16 mdw
81 * New multiprecision integer arithmetic suite.
92 /*----- Header files ------------------------------------------------------*/
99 #ifndef CATACOMB_MPW_H
103 #ifndef CATACOMB_ARENA_H
107 #ifndef CATACOMB_MPARENA_H
108 # include "mparena.h"
111 #ifndef CATACOMB_MPX_H
115 /*----- Data structures ---------------------------------------------------*/
117 /* --- A multiprecision integer --- */
120 mpw
*v
, *vl
; /* Vector of digits, current limit */
121 size_t sz
; /* Size of digit buffer in words */
122 mparena
*a
; /* Arena for buffer allocation */
123 unsigned f
; /* Flags (see below) */
124 unsigned ref
; /* Reference counter */
127 #define MP_NEG 1u /* Negative (signed magnitude) */
128 #define MP_BURN 2u /* Secret (viral flag) */
129 #define MP_CONST 4u /* Uses strange memory allocation */
130 #define MP_UNDEF 8u /* Contains nothing interesting */
131 #define MP_DESTROYED 16u /* Has been destroyed */
133 /* --- A factor for simultaneous exponentation --- *
135 * Used by the Montgomery and Barrett exponentiators.
138 typedef struct mp_expfactor
{
143 /*----- Useful constants --------------------------------------------------*/
145 extern mp mp_const
[];
147 #define MP_ZERO (&mp_const[0])
148 #define MP_ONE (&mp_const[1])
149 #define MP_TWO (&mp_const[2])
150 #define MP_THREE (&mp_const[3])
151 #define MP_FOUR (&mp_const[4])
152 #define MP_FIVE (&mp_const[5])
153 #define MP_TEN (&mp_const[6])
154 #define MP_256 (&mp_const[7])
155 #define MP_MONE (&mp_const[8])
157 #define MP_NEW ((mp *)0)
158 #define MP_NEWSEC (&mp_const[9])
160 /*----- Trivial macros ----------------------------------------------------*/
162 /* --- @MP_LEN@ --- *
164 * Arguments: @mp *m@ = pointer to a multiprecision integer
166 * Returns: Length of the integer, in words.
169 #define MP_LEN(m) ((m)->vl - ((m)->v))
171 /*----- Memory management and reference counting --------------------------*/
173 /* --- @mp_new@ --- *
175 * Arguments: @size_t sz@ = size of vector required
176 * @unsigned f@ = flags to set
178 * Returns: Pointer to a new MP structure.
180 * Use: Allocates a new multiprecision integer. The data space is
181 * allocated from either the standard global or secret arena,
182 * depending on the initial flags requested.
185 extern mp
*mp_new(size_t /*sz*/, unsigned /*f*/);
187 /* --- @mp_create@ --- *
189 * Arguments: @size_t sz@ = size of vector required
191 * Returns: Pointer to pristine new MP structure with enough memory
194 * Use: Creates a new multiprecision integer with indeterminate
195 * contents. The integer has a single reference.
198 extern mp
*mp_create(size_t /*sz*/);
200 /* --- @mp_createsecure@ --- *
202 * Arguments: @size_t sz@ = size of vector required
204 * Returns: Pointer to pristine new MP structure with enough memory
207 * Use: Creates a new multiprecision integer with indeterminate
208 * contents. The integer has a single reference. The integer's
209 * data space is allocated from the secure arena. Its burn flag
213 extern mp
*mp_createsecure(size_t /*sz*/);
215 /* --- @mp_build@ --- *
217 * Arguments: @mp *m@ = pointer to an MP block to fill in
218 * @mpw *v@ = pointer to a word array
219 * @mpw *vl@ = pointer just past end of array
223 * Use: Creates a multiprecision integer representing some smallish
224 * number. You must provide storage for the number and dispose
225 * of it when you've finished with it. The number is marked as
226 * constant while it exists.
229 extern void mp_build(mp */
*m*/
, mpw */
*v*/
, mpw */
*vl*/
);
231 /* --- @mp_destroy@ --- *
233 * Arguments: @mp *m@ = pointer to a multiprecision integer
237 * Use: Destroys a multiprecision integer. The reference count isn't
238 * checked. Don't use this function if you don't know what
239 * you're doing: use @mp_drop@ instead.
242 extern void mp_destroy(mp */
*m*/
);
244 /* --- @mp_copy@ --- *
246 * Arguments: @mp *m@ = pointer to a multiprecision integer
248 * Returns: A copy of the given multiprecision integer.
250 * Use: Copies the given integer. In fact you just get another
251 * reference to the same old one again.
254 extern mp
*mp_copy(mp */
*m*/
);
256 #define MP_COPY(m) ((m)->ref++, (m))
258 /* --- @mp_drop@ --- *
260 * Arguments: @mp *m@ = pointer to a multiprecision integer
264 * Use: Drops a reference to an integer which isn't wanted any more.
265 * If there are no more references, the integer is destroyed.
268 extern void mp_drop(mp */
*m*/
);
270 #define MP_DROP(m) do { \
273 if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \
277 /* --- @mp_split@ --- *
279 * Arguments: @mp *m@ = pointer to a multiprecision integer
281 * Returns: A reference to the same integer, possibly with a different
284 * Use: Splits off a modifiable version of the integer referred to.
287 extern mp
*mp_split(mp */
*m*/
);
289 #define MP_SPLIT(m) do { \
291 if ((_m->f & MP_CONST) || _m->ref > 1) { \
292 size_t _len = MP_LEN(_m); \
293 mp *_mm = mp_new(_len, _m->f); \
294 if (!(_m->f & MP_UNDEF)) \
295 memcpy(_mm->v, _m->v, MPWS(_len)); \
302 /* --- @mp_resize@ --- *
304 * Arguments: @mp *m@ = pointer to a multiprecision integer
305 * @size_t sz@ = new size
309 * Use: Resizes the vector containing the integer's digits. The new
310 * size must be at least as large as the current integer's
311 * length. This isn't really intended for client use.
314 extern void mp_resize(mp */
*m*/
, size_t /*sz*/);
316 #define MP_RESIZE(m, ssz) do { \
318 size_t _sz = (ssz); \
319 mparena *_a = (_m->f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL; \
321 size_t _len = MP_LEN(_m); \
322 assert(((void)"can't make size less than length", _sz >= _len)); \
323 _v = mpalloc(_a, _sz); \
324 if (!(_m->f & MP_UNDEF)) \
325 memcpy(_v, _m->v, MPWS(_len)); \
326 if (_m->f & MP_BURN) \
327 memset(_m->v, 0, MPWS(_m->sz)); \
328 mpfree(_m->a, _m->v); \
331 _m->vl = _v + _len; \
334 /* --- @mp_ensure@ --- *
336 * Arguments: @mp *m@ = pointer to a multiprecision integer
337 * @size_t sz@ = required size
341 * Use: Ensures that the integer has enough space for @sz@ digits.
342 * The value is not changed.
345 extern void mp_ensure(mp */
*m*/
, size_t /*sz*/);
347 #define MP_ENSURE(m, ssz) do { \
349 size_t _ssz = (ssz); \
350 size_t _len = MP_LEN(_m); \
351 if (_ssz >= _len) { \
353 mp_resize(_m, _ssz); \
354 if (!(_m->f & MP_UNDEF) && _ssz > _len) \
355 memset(_m->vl, 0, MPWS(_ssz - _len)); \
356 _m->vl = _m->v + _ssz; \
360 /* --- @mp_dest@ --- *
362 * Arguments: @mp *m@ = a suggested destination integer
363 * @size_t sz@ = size required for result, in digits
364 * @unsigned f@ = various flags
366 * Returns: A pointer to an appropriate destination.
368 * Use: Converts a suggested destination into a real destination with
369 * the required properties. If the real destination is @d@,
370 * then the following properties will hold:
372 * * @d@ will have exactly one reference.
374 * * If @m@ is not @MP_NEW@, then the contents of @m@ will not
375 * change, unless @f@ has the @MP_UNDEF@ flag set.
377 * * If @m@ is not @MP_NEW@, then he reference count of @m@ on
378 * entry is equal to the sum of the counts of @d@ and @m@ on
381 * * The size of @d@ will be at least @sz@.
383 * * If @f@ has the @MP_BURN@ flag set, then @d@ will be
384 * allocated from @MPARENA_SECURE@.
386 * Understanding this function is crucial to using Catacomb's
387 * multiprecision integer library effectively.
390 extern mp
*mp_dest(mp */
*m*/
, size_t /*sz*/, unsigned /*f*/);
392 #define MP_DEST(m, ssz, f) do { \
394 size_t _ssz = (ssz); \
396 _m = mp_dest(_m, _ssz, _f); \
400 /*----- Size manipulation -------------------------------------------------*/
402 /* --- @mp_shrink@ --- *
404 * Arguments: @mp *m@ = pointer to a multiprecision integer
408 * Use: Reduces the recorded length of an integer. This doesn't
409 * reduce the amount of memory used, although it can improve
410 * performance a bit. To reduce memory, use @mp_minimize@
411 * instead. This can't change the value of an integer, and is
412 * therefore safe to use even when there are multiple
416 extern void mp_shrink(mp */
*m*/
);
418 #define MP_SHRINK(m) do { \
420 MPX_SHRINK(_mm->v, _mm->vl); \
425 /* --- @mp_minimize@ --- *
427 * Arguments: @mp *m@ = pointer to a multiprecision integer
431 * Use: Reduces the amount of memory an integer uses. It's best to
432 * do this to numbers which aren't going to change in the
436 extern void mp_minimize(mp */
*m*/
);
438 /*----- Bit scanning ------------------------------------------------------*/
440 #ifndef CATACOMB_MPSCAN_H
444 /* --- @mp_scan@ --- *
446 * Arguments: @mpscan *sc@ = pointer to bitscanner block
447 * @const mp *m@ = pointer to a multiprecision integer
451 * Use: Initializes a bitscanner on a multiprecision integer.
454 extern void mp_scan(mpscan */
*sc*/
, const mp */
*m*/
);
456 #define MP_SCAN(sc, m) do { \
457 const mp *_mm = (m); \
458 mpscan *_sc = (sc); \
459 MPSCAN_INITX(_sc, _mm->v, _mm->vl); \
462 /* --- @mp_rscan@ --- *
464 * Arguments: @mpscan *sc@ = pointer to bitscanner block
465 * @const mp *m@ = pointer to a multiprecision integer
469 * Use: Initializes a reverse bitscanner on a multiprecision
473 extern void mp_rscan(mpscan */
*sc*/
, const mp */
*m*/
);
475 #define MP_RSCAN(sc, m) do { \
476 const mp *_mm = (m); \
477 mpscan *_sc = (sc); \
478 MPSCAN_RINITX(_sc, _mm->v, _mm->vl); \
481 /* --- Other bitscanning aliases --- */
483 #define mp_step mpscan_step
484 #define mp_bit mpscan_bit
485 #define mp_rstep mpscan_rstep
486 #define mp_rbit mpscan_rbit
488 #define MP_STEP MPSCAN_STEP
489 #define MP_BIT MPSCAN_BIT
490 #define MP_RSTEP MPSCAN_RSTEP
491 #define MP_RBIT MPSCAN_RBIT
493 /*----- Loading and storing -----------------------------------------------*/
495 /* --- @mp_octets@ --- *
497 * Arguments: @const mp *m@ = a multiprecision integer
499 * Returns: The number of octets required to represent @m@.
501 * Use: Calculates the external storage required for a multiprecision
505 extern size_t mp_octets(const mp */
*m*/
);
507 /* --- @mp_octets2c@ --- *
509 * Arguments: @const mp *m@ = a multiprecision integer
511 * Returns: The number of octets required to represent @m@.
513 * Use: Calculates the external storage required for a multiprecision
514 * integer represented as two's complement.
517 extern size_t mp_octets2c(const mp */
*m*/
);
519 /* --- @mp_bits@ --- *
521 * Arguments: @const mp *m@ = a multiprecision integer
523 * Returns: The number of bits required to represent @m@.
525 * Use: Calculates the external storage required for a multiprecision
529 extern unsigned long mp_bits(const mp */
*m*/
);
531 /* --- @mp_loadl@ --- *
533 * Arguments: @mp *d@ = destination
534 * @const void *pv@ = pointer to source data
535 * @size_t sz@ = size of the source data
537 * Returns: Resulting multiprecision number.
539 * Use: Loads a multiprecision number from an array of octets. The
540 * first byte in the array is the least significant. More
541 * formally, if the bytes are %$b_0, b_1, \ldots, b_{n-1}$%
542 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
545 extern mp
*mp_loadl(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
547 /* --- @mp_storel@ --- *
549 * Arguments: @const mp *m@ = source
550 * @void *pv@ = pointer to output array
551 * @size_t sz@ = size of the output array
555 * Use: Stores a multiprecision number in an array of octets. The
556 * first byte in the array is the least significant. If the
557 * array is too small to represent the number, high-order bits
558 * are truncated; if the array is too large, high order bytes
559 * are filled with zeros. More formally, if the number is
560 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
561 * then the array is %$b_0, b_1, \ldots, b_{n-1}$%.
564 extern void mp_storel(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
566 /* --- @mp_loadb@ --- *
568 * Arguments: @mp *d@ = destination
569 * @const void *pv@ = pointer to source data
570 * @size_t sz@ = size of the source data
572 * Returns: Resulting multiprecision number.
574 * Use: Loads a multiprecision number from an array of octets. The
575 * last byte in the array is the least significant. More
576 * formally, if the bytes are %$b_{n-1}, b_{n-2}, \ldots, b_0$%
577 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
580 extern mp
*mp_loadb(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
582 /* --- @mp_storeb@ --- *
584 * Arguments: @const mp *m@ = source
585 * @void *pv@ = pointer to output array
586 * @size_t sz@ = size of the output array
590 * Use: Stores a multiprecision number in an array of octets. The
591 * last byte in the array is the least significant. If the
592 * array is too small to represent the number, high-order bits
593 * are truncated; if the array is too large, high order bytes
594 * are filled with zeros. More formally, if the number is
595 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
596 * then the array is %$b_{n-1}, b_{n-2}, \ldots, b_0$%.
599 extern void mp_storeb(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
601 /* --- @mp_loadl2c@ --- *
603 * Arguments: @mp *d@ = destination
604 * @const void *pv@ = pointer to source data
605 * @size_t sz@ = size of the source data
607 * Returns: Resulting multiprecision number.
609 * Use: Loads a multiprecision number from an array of octets as
610 * two's complement. The first byte in the array is the least
614 extern mp
*mp_loadl2c(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
616 /* --- @mp_storel2c@ --- *
618 * Arguments: @const mp *m@ = source
619 * @void *pv@ = pointer to output array
620 * @size_t sz@ = size of the output array
624 * Use: Stores a multiprecision number in an array of octets as two's
625 * complement. The first byte in the array is the least
626 * significant. If the array is too small to represent the
627 * number, high-order bits are truncated; if the array is too
628 * large, high order bytes are sign-extended.
631 extern void mp_storel2c(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
633 /* --- @mp_loadb2c@ --- *
635 * Arguments: @mp *d@ = destination
636 * @const void *pv@ = pointer to source data
637 * @size_t sz@ = size of the source data
639 * Returns: Resulting multiprecision number.
641 * Use: Loads a multiprecision number from an array of octets as
642 * two's complement. The last byte in the array is the least
646 extern mp
*mp_loadb2c(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
648 /* --- @mp_storeb2c@ --- *
650 * Arguments: @const mp *m@ = source
651 * @void *pv@ = pointer to output array
652 * @size_t sz@ = size of the output array
656 * Use: Stores a multiprecision number in an array of octets, as
657 * two's complement. The last byte in the array is the least
658 * significant. If the array is too small to represent the
659 * number, high-order bits are truncated; if the array is too
660 * large, high order bytes are sign-extended.
663 extern void mp_storeb2c(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
665 /*----- Bit operations ----------------------------------------------------*/
667 /* --- @mp_not@ --- *
669 * Arguments: @mp *d@ = destination
672 * Returns: The bitwise complement of the source.
675 extern mp
*mp_not(mp */
*d*/
, mp */
*a*/
);
677 /* --- @mp_bitop@ --- *
679 * Arguments: @mp *d@ = destination
680 * @mp *a, *b@ = sources
682 * Returns: The result of the given bitwise operation. These functions
683 * don't handle negative numbers at all sensibly. For that, use
684 * the @...2c@ variants. The functions are named after the
685 * truth tables they generate:
692 #define MP_BITDECL(string) \
693 extern mp *mp_bit##string(mp */*d*/, mp */*a*/, mp */*b*/);
694 MPX_DOBIN(MP_BITDECL
)
696 /* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- *
698 * Synonyms for the commonly-used functions.
701 #define mp_and mp_bit0001
702 #define mp_or mp_bit0111
703 #define mp_nand mp_bit1110
704 #define mp_nor mp_bit1000
705 #define mp_xor mp_bit0110
707 /* --- @mp_testbit@ --- *
709 * Arguments: @mp *x@ = a large integer
710 * @unsigned long n@ = which bit to test
712 * Returns: Nonzero if the bit is set, zero if not.
715 extern int mp_testbit(mp */
*x*/
, unsigned long /*n*/);
717 /* --- @mp_setbit@, @mp_clearbit@ --- *
719 * Arguments: @mp *d@ = a destination
720 * @mp *x@ = a large integer
721 * @unsigned long n@ = which bit to modify
723 * Returns: The argument @x@, with the appropriate bit set or cleared.
726 extern mp
*mp_setbit(mp */
*d*/
, mp */
*x*/
, unsigned long /*n*/);
727 extern mp
*mp_clearbit(mp */
*d*/
, mp */
*x*/
, unsigned long /*n*/);
729 /* --- @mp_lsl@, @mp_lsr@ --- *
731 * Arguments: @mp *d@ = destination
733 * @size_t n@ = number of bits to move
735 * Returns: Result, @a@ shifted left or right by @n@.
738 extern mp
*mp_lsl(mp */
*d*/
, mp */
*a*/
, size_t /*n*/);
739 extern mp
*mp_lsr(mp */
*d*/
, mp */
*a*/
, size_t /*n*/);
741 /* --- @mp_not2c@ --- *
743 * Arguments: @mp *d@ = destination
746 * Returns: The sign-extended complement of the argument.
749 extern mp
*mp_not2c(mp */
*d*/
, mp */
*a*/
);
751 /* --- @mp_bitop2c@ --- *
753 * Arguments: @mp *d@ = destination
754 * @mp *a, *b@ = sources
756 * Returns: The result of the given bitwise operation. Negative numbers
757 * are treated as two's complement, sign-extended infinitely to
758 * the left. The functions are named after the truth tables
766 #define MP_BIT2CDECL(string) \
767 extern mp *mp_bit##string##2c(mp */*d*/, mp */*a*/, mp */*b*/);
768 MPX_DOBIN(MP_BIT2CDECL
)
770 /* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- *
772 * Synonyms for the commonly-used functions.
775 #define mp_and2c mp_bit00012c
776 #define mp_or2c mp_bit01112c
777 #define mp_nand2c mp_bit11102c
778 #define mp_nor2c mp_bit10002c
779 #define mp_xor2c mp_bit01102c
781 /* --- @mp_lsl2c@, @mp_lsr2c@ --- *
783 * Arguments: @mp *d@ = destination
785 * @size_t n@ = number of bits to move
787 * Returns: Result, @a@ shifted left or right by @n@. Handles the
788 * pretence of sign-extension for negative numbers.
791 extern mp
*mp_lsl2c(mp */
*d*/
, mp */
*a*/
, size_t /*n*/);
792 extern mp
*mp_lsr2c(mp */
*d*/
, mp */
*a*/
, size_t /*n*/);
794 /* --- @mp_testbit2c@ --- *
796 * Arguments: @mp *x@ = a large integer
797 * @unsigned long n@ = which bit to test
799 * Returns: Nonzero if the bit is set, zero if not. Fakes up two's
800 * complement representation.
803 extern int mp_testbit2c(mp */
*x*/
, unsigned long /*n*/);
805 /* --- @mp_setbit2c@, @mp_clearbit2c@ --- *
807 * Arguments: @mp *d@ = a destination
808 * @mp *x@ = a large integer
809 * @unsigned long n@ = which bit to modify
811 * Returns: The argument @x@, with the appropriate bit set or cleared.
812 * Fakes up two's complement representation.
815 extern mp
*mp_setbit2c(mp */
*d*/
, mp */
*x*/
, unsigned long /*n*/);
816 extern mp
*mp_clearbit2c(mp */
*d*/
, mp */
*x*/
, unsigned long /*n*/);
818 /*----- Comparisons -------------------------------------------------------*/
822 * Arguments: @const mp *a, *b@ = two numbers
824 * Returns: Nonzero if the numbers are equal.
827 extern int mp_eq(const mp */
*a*/
, const mp */
*b*/
);
829 #define MP_EQ(a, b) \
830 ((((a)->f ^ (b)->f) & MP_NEG) == 0 && \
831 mpx_ueq((a)->v, (a)->vl, (b)->v, (b)->vl))
833 /* --- @mp_cmp@ --- *
835 * Arguments: @const mp *a, *b@ = two numbers
837 * Returns: Less than, equal to or greater than zero, according to
838 * whether @a@ is less than, equal to or greater than @b@.
841 extern int mp_cmp(const mp */
*a*/
, const mp */
*b*/
);
843 #define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0)
845 /* --- Other handy macros --- */
847 #define MP_ISNEG(x) ((x)->f & MP_NEG)
848 #define MP_ISZERO(x) MP_EQ((x), MP_ZERO)
849 #define MP_ISPOS(x) (!MP_ISNEG(x) && !MP_ISZERO(x))
851 /*----- Arithmetic operations ---------------------------------------------*/
853 /* --- @mp_neg@ --- *
855 * Arguments: @mp *d@ = destination
858 * Returns: The negation of the argument.
860 * Use: Negates its argument.
863 extern mp
*mp_neg(mp */
*d*/
, mp */
*a*/
);
865 /* --- @mp_add@ --- *
867 * Arguments: @mp *d@ = destination
868 * @mp *a, *b@ = sources
870 * Returns: Result, @a@ added to @b@.
873 extern mp
*mp_add(mp */
*d*/
, mp */
*a*/
, mp */
*b*/
);
875 /* --- @mp_sub@ --- *
877 * Arguments: @mp *d@ = destination
878 * @mp *a, *b@ = sources
880 * Returns: Result, @b@ subtracted from @a@.
883 extern mp
*mp_sub(mp */
*d*/
, mp */
*a*/
, mp */
*b*/
);
885 /* --- @mp_mul@ --- *
887 * Arguments: @mp *d@ = destination
888 * @mp *a, *b@ = sources
890 * Returns: Result, @a@ multiplied by @b@.
893 extern mp
*mp_mul(mp */
*d*/
, mp */
*a*/
, mp */
*b*/
);
895 /* --- @mp_sqr@ --- *
897 * Arguments: @mp *d@ = destination
900 * Returns: Result, @a@ squared.
903 extern mp
*mp_sqr(mp */
*d*/
, mp */
*a*/
);
905 /* --- @mp_div@ --- *
907 * Arguments: @mp **qq, **rr@ = destination, quotient and remainder
908 * @mp *a, *b@ = sources
910 * Use: Calculates the quotient and remainder when @a@ is divided by
914 extern void mp_div(mp
**/
*qq*/
, mp
**/
*rr*/
, mp */
*a*/
, mp */
*b*/
);
916 /* --- @mp_odd@ --- *
918 * Arguments: @mp *d@ = pointer to destination integer
919 * @mp *m@ = pointer to source integer
920 * @size_t *s@ = where to store the power of 2
922 * Returns: An odd integer integer %$t$% such that %$m = 2^s t$%.
924 * Use: Computes a power of two and an odd integer which, when
925 * multiplied, give a specified result. This sort of thing is
926 * useful in number theory quite often.
929 extern mp
*mp_odd(mp */
*d*/
, mp */
*m*/
, size_t */
*s*/
);
931 /*----- More advanced algorithms ------------------------------------------*/
933 /* --- @mp_sqrt@ --- *
935 * Arguments: @mp *d@ = pointer to destination integer
936 * @mp *a@ = (nonnegative) integer to take square root of
938 * Returns: The largest integer %$x$% such that %$x^2 \le a$%.
940 * Use: Computes integer square roots.
942 * The current implementation isn't very good: it uses the
943 * Newton-Raphson method to find an approximation to %$a$%. If
944 * there's any demand for a better version, I'll write one.
947 extern mp
*mp_sqrt(mp */
*d*/
, mp */
*a*/
);
949 /* --- @mp_gcd@ --- *
951 * Arguments: @mp **gcd, **xx, **yy@ = where to write the results
952 * @mp *a, *b@ = sources (must be nonzero)
956 * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
957 * @ax + by = gcd(a, b)@. This is useful for computing modular
958 * inverses. Neither @a@ nor @b@ may be zero.
961 extern void mp_gcd(mp
**/
*gcd*/
, mp
**/
*xx*/
, mp
**/
*yy*/
,
962 mp */
*a*/
, mp */
*b*/
);
964 /* --- @mp_jacobi@ --- *
966 * Arguments: @mp *a@ = an integer less than @n@
967 * @mp *n@ = an odd integer
969 * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
971 * Use: Computes the Jacobi symbol. If @n@ is prime, this is the
972 * Legendre symbol and is equal to 1 if and only if @a@ is a
973 * quadratic residue mod @n@. The result is zero if and only if
974 * @a@ and @n@ have a common factor greater than one.
977 extern int mp_jacobi(mp */
*a*/
, mp */
*n*/
);
979 /* --- @mp_modsqrt@ --- *
981 * Arguments: @mp *d@ = destination integer
982 * @mp *a@ = source integer
983 * @mp *p@ = modulus (must be prime)
985 * Returns: If %$a$% is a quadratic residue, a square root of %$a$%; else
988 * Use: Returns an integer %$x$% such that %$x^2 \equiv a \pmod{p}$%,
989 * if one exists; else a null pointer. This function will not
990 * work if %$p$% is composite: you must factor the modulus, take
991 * a square root mod each factor, and recombine the results
992 * using the Chinese Remainder Theorem.
995 extern mp
*mp_modsqrt(mp */
*d*/
, mp */
*a*/
, mp */
*p*/
);
997 /*----- Test harness support ----------------------------------------------*/
999 #include <mLib/testrig.h>
1001 #ifndef CATACOMB_MPTEXT_H
1002 # include "mptext.h"
1005 extern const test_type type_mp
;
1007 /*----- That's all, folks -------------------------------------------------*/