X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/f09e814abfcb58c0bb5423589e2940c205106e8d..f52f2db067dc1388b16ab00ddb53e26a381a6e3e:/mp.h diff --git a/mp.h b/mp.h index c405bca..13f97d1 100644 --- a/mp.h +++ b/mp.h @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: mp.h,v 1.13 2002/10/06 22:52:50 mdw Exp $ + * $Id$ * * Simple multiprecision arithmetic * * (c) 1999 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,64 +15,18 @@ * it under the terms of the GNU Library General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. - * + * * Catacomb is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Library General Public License for more details. - * + * * You should have received a copy of the GNU Library General Public * License along with Catacomb; if not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* - * - * $Log: mp.h,v $ - * Revision 1.13 2002/10/06 22:52:50 mdw - * Pile of changes for supporting two's complement properly. - * - * Revision 1.12 2001/06/16 12:57:43 mdw - * Move the @mpmont_factor@ structure and rename it now that it's used for - * Barrett simultaneous exponentiation too. - * - * Revision 1.11 2001/04/03 19:36:05 mdw - * Add some simple bitwise operations so that Perl can use them. - * - * Revision 1.10 2000/10/08 12:03:16 mdw - * Provide @mp_eq@ and @MP_EQ@ for rapidly testing equality of two - * integers. - * - * Revision 1.9 2000/07/29 17:03:31 mdw - * Add support for left-to-right bitscanning, for use in modular - * exponentiation. - * - * Revision 1.8 2000/06/22 19:02:01 mdw - * Add new functions. - * - * Revision 1.7 2000/06/17 11:45:09 mdw - * Major memory management overhaul. Added arena support. Use the secure - * arena for secret integers. Replace and improve the MP management macros - * (e.g., replace MP_MODIFY by MP_DEST). - * - * Revision 1.6 1999/12/10 23:19:46 mdw - * Minor bugfixes. New interface for suggested destinations. - * - * Revision 1.5 1999/11/22 20:50:37 mdw - * Add support for computing Jacobi symbols. - * - * Revision 1.4 1999/11/21 22:13:02 mdw - * Add mp version of MPX_BITS. - * - * Revision 1.3 1999/11/19 13:19:14 mdw - * Fix const annotation. - * - * Revision 1.2 1999/11/17 18:02:16 mdw - * New multiprecision integer arithmetic suite. - * - */ - #ifndef CATACOMB_MP_H #define CATACOMB_MP_H @@ -136,14 +90,14 @@ typedef struct mp_expfactor { extern mp mp_const[]; #define MP_ZERO (&mp_const[0]) -#define MP_ONE (&mp_const[1]) -#define MP_TWO (&mp_const[2]) +#define MP_ONE (&mp_const[1]) +#define MP_TWO (&mp_const[2]) #define MP_THREE (&mp_const[3]) -#define MP_FOUR (&mp_const[4]) -#define MP_FIVE (&mp_const[5]) -#define MP_TEN (&mp_const[6]) +#define MP_FOUR (&mp_const[4]) +#define MP_FIVE (&mp_const[5]) +#define MP_TEN (&mp_const[6]) #define MP_256 (&mp_const[7]) -#define MP_MONE (&mp_const[8]) +#define MP_MONE (&mp_const[8]) #define MP_NEW ((mp *)0) #define MP_NEWSEC (&mp_const[9]) @@ -264,7 +218,7 @@ extern void mp_drop(mp */*m*/); if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \ mp_destroy(_mm); \ } while (0) - + /* --- @mp_split@ --- * * * Arguments: @mp *m@ = pointer to a multiprecision integer @@ -409,7 +363,7 @@ extern void mp_shrink(mp */*m*/); #define MP_SHRINK(m) do { \ mp *_mm = (m); \ MPX_SHRINK(_mm->v, _mm->vl); \ - if (!MP_LEN(_mm)) \ + if (MP_ZEROP(_mm)) \ _mm->f &= ~MP_NEG; \ } while (0) @@ -653,118 +607,97 @@ extern mp *mp_loadb2c(mp */*d*/, const void */*pv*/, size_t /*sz*/); extern void mp_storeb2c(const mp */*m*/, void */*pv*/, size_t /*sz*/); -/*----- Simple arithmetic -------------------------------------------------*/ +/*----- Bit operations ----------------------------------------------------*/ -/* --- @mp_lsl@, @mp_lsr@ --- * +/* --- @mp_not@ --- * * * Arguments: @mp *d@ = destination * @mp *a@ = source - * @size_t n@ = number of bits to move * - * Returns: Result, @a@ shifted left or right by @n@. + * Returns: The bitwise complement of the source. */ -extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/); -extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/); +extern mp *mp_not(mp */*d*/, mp */*a*/); -/* --- @mp_lsl2c@, @mp_lsr2c@ --- * +/* --- @mp_bitop@ --- * * * Arguments: @mp *d@ = destination - * @mp *a@ = source - * @size_t n@ = number of bits to move - * - * Returns: Result, @a@ shifted left or right by @n@. Handles the - * pretence of sign-extension for negative numbers. - */ - -extern mp *mp_lsl2c(mp */*d*/, mp */*a*/, size_t /*n*/); -extern mp *mp_lsr2c(mp */*d*/, mp */*a*/, size_t /*n*/); - -/* --- @mp_testbit@ --- * + * @mp *a, *b@ = sources * - * Arguments: @mp *x@ = a large integer - * @size_t n@ = which bit to test + * Returns: The result of the given bitwise operation. These functions + * don't handle negative numbers at all sensibly. For that, use + * the @...2c@ variants. The functions are named after the + * truth tables they generate: * - * Returns: Nonzero if the bit is set, zero if not. + * a: 0011 + * b: 0101 + * @mpx_bitXXXX@ */ -extern int mp_testbit(mp */*x*/, size_t /*n*/); +#define MP_BITDECL(string) \ + extern mp *mp_bit##string(mp */*d*/, mp */*a*/, mp */*b*/); +MPX_DOBIN(MP_BITDECL) -/* --- @mp_testbit2c@ --- * - * - * Arguments: @mp *x@ = a large integer - * @size_t n@ = which bit to test +/* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- * * - * Returns: Nonzero if the bit is set, zero if not. Fakes up two's - * complement representation. + * Synonyms for the commonly-used functions. */ -extern int mp_testbit2c(mp */*x*/, size_t /*n*/); +#define mp_and mp_bit0001 +#define mp_or mp_bit0111 +#define mp_nand mp_bit1110 +#define mp_nor mp_bit1000 +#define mp_xor mp_bit0110 -/* --- @mp_eq@ --- * +/* --- @mp_testbit@ --- * * - * Arguments: @const mp *a, *b@ = two numbers + * Arguments: @mp *x@ = a large integer + * @unsigned long n@ = which bit to test * - * Returns: Nonzero if the numbers are equal. + * Returns: Nonzero if the bit is set, zero if not. */ -extern int mp_eq(const mp */*a*/, const mp */*b*/); - -#define MP_EQ(a, b) \ - ((((a)->f ^ (b)->f) & MP_NEG) == 0 && \ - mpx_ueq((a)->v, (a)->vl, (b)->v, (b)->vl)) +extern int mp_testbit(mp */*x*/, unsigned long /*n*/); -/* --- @mp_cmp@ --- * +/* --- @mp_setbit@, @mp_clearbit@ --- * * - * Arguments: @const mp *a, *b@ = two numbers + * Arguments: @mp *d@ = a destination + * @mp *x@ = a large integer + * @unsigned long n@ = which bit to modify * - * Returns: Less than, equal to or greater than zero, according to - * whether @a@ is less than, equal to or greater than @b@. + * Returns: The argument @x@, with the appropriate bit set or cleared. */ -extern int mp_cmp(const mp */*a*/, const mp */*b*/); - -#define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0) +extern mp *mp_setbit(mp */*d*/, mp */*x*/, unsigned long /*n*/); +extern mp *mp_clearbit(mp */*d*/, mp */*x*/, unsigned long /*n*/); -/* --- @mp_bitop@ --- * +/* --- @mp_lsl@, @mp_lslc@, @mp_lsr@ --- * * * Arguments: @mp *d@ = destination - * @mp *a, *b@ = sources - * - * Returns: The result of the given bitwise operation. These functions - * don't handle negative numbers at all sensibly. For that, use - * the @...2c@ variants. The functions are named after the - * truth tables they generate: + * @mp *a@ = source + * @size_t n@ = number of bits to move * - * a: 0011 - * b: 0101 - * @mpx_bitXXXX@ - */ - -#define MP_BITDECL(string) \ - extern mp *mp_bit##string(mp */*d*/, mp */*a*/, mp */*b*/); -MPX_DOBIN(MP_BITDECL) - -/* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- * + * Returns: Result, @a@ shifted left or right by @n@. * - * Synonyms for the commonly-used functions. + * Use: Bitwise shift operators. @mp_lslc@ fills the bits introduced + * on the right with ones instead of zeroes: it's used + * internally by @mp_lsl2c@, though it may be useful on its + * own. */ -#define mp_and mp_bit0001 -#define mp_or mp_bit0111 -#define mp_nand mp_bit1110 -#define mp_nor mp_bit1000 -#define mp_xor mp_bit0110 +extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/); +extern mp *mp_lslc(mp */*d*/, mp */*a*/, size_t /*n*/); +extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/); -/* --- @mp_not@ --- * +/* --- @mp_not2c@ --- * * * Arguments: @mp *d@ = destination * @mp *a@ = source * - * Returns: The bitwise complement of the source. - */ + * Returns: The sign-extended complement of the argument. + */ -extern mp *mp_not(mp */*d*/, mp */*a*/); +extern mp *mp_not2c(mp */*d*/, mp */*a*/); /* --- @mp_bitop2c@ --- * * @@ -791,20 +724,96 @@ MPX_DOBIN(MP_BIT2CDECL) */ #define mp_and2c mp_bit00012c -#define mp_or2c mp_bit01112c +#define mp_or2c mp_bit01112c #define mp_nand2c mp_bit11102c #define mp_nor2c mp_bit10002c #define mp_xor2c mp_bit01102c -/* --- @mp_not2c@ --- * +/* --- @mp_lsl2c@, @mp_lsr2c@ --- * * * Arguments: @mp *d@ = destination * @mp *a@ = source + * @size_t n@ = number of bits to move * - * Returns: The sign-extended complement of the argument. + * Returns: Result, @a@ shifted left or right by @n@. Handles the + * pretence of sign-extension for negative numbers. */ -extern mp *mp_not2c(mp */*d*/, mp */*a*/); +extern mp *mp_lsl2c(mp */*d*/, mp */*a*/, size_t /*n*/); +extern mp *mp_lsr2c(mp */*d*/, mp */*a*/, size_t /*n*/); + +/* --- @mp_testbit2c@ --- * + * + * Arguments: @mp *x@ = a large integer + * @unsigned long n@ = which bit to test + * + * Returns: Nonzero if the bit is set, zero if not. Fakes up two's + * complement representation. + */ + +extern int mp_testbit2c(mp */*x*/, unsigned long /*n*/); + +/* --- @mp_setbit2c@, @mp_clearbit2c@ --- * + * + * Arguments: @mp *d@ = a destination + * @mp *x@ = a large integer + * @unsigned long n@ = which bit to modify + * + * Returns: The argument @x@, with the appropriate bit set or cleared. + * Fakes up two's complement representation. + */ + +extern mp *mp_setbit2c(mp */*d*/, mp */*x*/, unsigned long /*n*/); +extern mp *mp_clearbit2c(mp */*d*/, mp */*x*/, unsigned long /*n*/); + +/*----- Comparisons -------------------------------------------------------*/ + +/* --- @mp_eq@ --- * + * + * Arguments: @const mp *a, *b@ = two numbers + * + * Returns: Nonzero if the numbers are equal. + */ + +extern int mp_eq(const mp */*a*/, const mp */*b*/); + +#define MP_EQ(a, b) \ + ((((a)->f ^ (b)->f) & MP_NEG) == 0 && \ + mpx_ueq((a)->v, (a)->vl, (b)->v, (b)->vl)) + +/* --- @mp_cmp@ --- * + * + * Arguments: @const mp *a, *b@ = two numbers + * + * Returns: Less than, equal to or greater than zero, according to + * whether @a@ is less than, equal to or greater than @b@. + */ + +extern int mp_cmp(const mp */*a*/, const mp */*b*/); + +#define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0) + +/* --- Other handy macros --- */ + +#define MP_NEGP(x) ((x)->f & MP_NEG) +#define MP_ZEROP(x) (!MP_LEN(x)) +#define MP_POSP(x) (!MP_NEGP(x) && !MP_ZEROP(x)) +#define MP_ODDP(x) (!MP_ZEROP(x) && ((x)->v[0] & 1u)) +#define MP_EVENP(x) (!MP_ODDP(x)) + +/*----- Arithmetic operations ---------------------------------------------*/ + +/* --- @mp_neg@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a@ = argument + * + * Returns: The negation of the argument. + * + * Use: Negates its argument. + */ + +extern mp *mp_neg(mp */*d*/, mp */*a*/); /* --- @mp_add@ --- * * @@ -857,6 +866,17 @@ extern mp *mp_sqr(mp */*d*/, mp */*a*/); extern void mp_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/); +/* --- @mp_exp@ --- * + * + * Arguments: @mp *d@ = fake destination + * @mp *a@ = base + * @mp *e@ = exponent + * + * Returns: Result, %$a^e$%. + */ + +extern mp *mp_exp(mp */*d*/, mp */*a*/, mp */*e*/); + /* --- @mp_odd@ --- * * * Arguments: @mp *d@ = pointer to destination integer @@ -905,17 +925,51 @@ extern mp *mp_sqrt(mp */*d*/, mp */*a*/); extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/, mp */*a*/, mp */*b*/); +/* -- @mp_modinv@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *x@ = argument + * @mp *p@ = modulus + * + * Returns: The inverse %$x^{-1} \bmod p$%. + * + * Use: Computes a modular inverse. An assertion fails if %$p$% + * has no inverse. + */ + +extern mp *mp_modinv(mp */*d*/, mp */*x*/, mp */*p*/); + /* --- @mp_jacobi@ --- * * - * Arguments: @mp *a@ = an integer less than @n@ - * @mp *n@ = an odd integer + * Arguments: @mp *a@ = an integer + * @mp *n@ = another integer * * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%. * - * Use: Computes the Jacobi symbol. If @n@ is prime, this is the - * Legendre symbol and is equal to 1 if and only if @a@ is a - * quadratic residue mod @n@. The result is zero if and only if - * @a@ and @n@ have a common factor greater than one. + * Use: Computes the Kronecker symbol %$\jacobi{a}{n}$%. If @n@ is + * prime, this is the Legendre symbol and is equal to 1 if and + * only if @a@ is a quadratic residue mod @n@. The result is + * zero if and only if @a@ and @n@ have a common factor greater + * than one. + * + * If @n@ is composite, then this computes the Kronecker symbol + * + * %$\jacobi{a}{n}=\jacobi{a}{u}\prod_i\jacobi{a}{p_i}^{e_i}$% + * + * where %$n = u p_0^{e_0} \ldots p_{n-1}^{e_{n-1}}$% is the + * prime factorization of %$n$%. The missing bits are: + * + * * %$\jacobi{a}{1} = 1$%; + * * %$\jacobi{a}{-1} = 1$% if @a@ is negative, or 1 if + * positive; + * * %$\jacobi{a}{0} = 0$%; + * * %$\jacobi{a}{2}$ is 0 if @a@ is even, 1 if @a@ is + * congruent to 1 or 7 (mod 8), or %$-1$% otherwise. + * + * If %$n$% is positive and odd, then this is the Jacobi + * symbol. (The Kronecker symbol is a consistant domain + * extension; the Jacobi symbol was implemented first, and the + * name stuck.) */ extern int mp_jacobi(mp */*a*/, mp */*n*/); @@ -934,10 +988,25 @@ extern int mp_jacobi(mp */*a*/, mp */*n*/); * work if %$p$% is composite: you must factor the modulus, take * a square root mod each factor, and recombine the results * using the Chinese Remainder Theorem. + * + * We guarantee that the square root returned is the smallest + * one (i.e., the `positive' square root). */ extern mp *mp_modsqrt(mp */*d*/, mp */*a*/, mp */*p*/); +/* --- @mp_modexp@ --- * + * + * Arguments: @mp *d@ = fake destination + * @mp *x@ = base of exponentiation + * @mp *e@ = exponent + * @mp *n@ = modulus (must be positive) + * + * Returns: The value %$x^e \bmod n$%. + */ + +extern mp *mp_modexp(mp */*d*/, mp */*x*/, mp */*e*/, mp */*n*/); + /*----- Test harness support ----------------------------------------------*/ #include