X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/5b00a0eafb523750b8a262eedac97f2dd4f63187..6ec3a4cf4aaa7cd375e1aa18f85861986259b8e5:/mp.h diff --git a/mp.h b/mp.h index dce8128..13f97d1 100644 --- a/mp.h +++ b/mp.h @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: mp.h,v 1.5 1999/11/22 20:50:37 mdw Exp $ + * $Id$ * * Simple multiprecision arithmetic * * (c) 1999 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,37 +15,20 @@ * 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.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 MP_H -#define MP_H +#ifndef CATACOMB_MP_H +#define CATACOMB_MP_H #ifdef __cplusplus extern "C" { @@ -58,114 +41,108 @@ #include -#ifndef MPW_H +#ifndef CATACOMB_MPW_H # include "mpw.h" #endif -#ifndef MPX_H +#ifndef CATACOMB_ARENA_H +# include "arena.h" +#endif + +#ifndef CATACOMB_MPARENA_H +# include "mparena.h" +#endif + +#ifndef CATACOMB_MPX_H # include "mpx.h" #endif /*----- Data structures ---------------------------------------------------*/ +/* --- A multiprecision integer --- */ + typedef struct mp { - mpw *v, *vl; - size_t sz; - unsigned f; - unsigned ref; + mpw *v, *vl; /* Vector of digits, current limit */ + size_t sz; /* Size of digit buffer in words */ + mparena *a; /* Arena for buffer allocation */ + unsigned f; /* Flags (see below) */ + unsigned ref; /* Reference counter */ } mp; -#define MP_NEG 1u -#define MP_BURN 2u -#define MP_CONST 4u -#define MP_UNDEF 8u +#define MP_NEG 1u /* Negative (signed magnitude) */ +#define MP_BURN 2u /* Secret (viral flag) */ +#define MP_CONST 4u /* Uses strange memory allocation */ +#define MP_UNDEF 8u /* Contains nothing interesting */ +#define MP_DESTROYED 16u /* Has been destroyed */ + +/* --- A factor for simultaneous exponentation --- * + * + * Used by the Montgomery and Barrett exponentiators. + */ + +typedef struct mp_expfactor { + mp *base; + mp *exp; +} mp_expfactor; /*----- Useful constants --------------------------------------------------*/ 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_MONE (&mp_const[7]) +#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_NEW ((mp *)0) +#define MP_NEWSEC (&mp_const[9]) -/*----- Memory allocation hooks -------------------------------------------*/ - -#ifndef MPARENA_H -# include "mparena.h" -#endif - -/* --- @MP_ARENA@ --- * - * - * This selects where memory is allocated from. Tweak to use more fancy - * things like custom arenas. - */ - -#ifndef MP_ARENA -# define MP_ARENA MPARENA_GLOBAL -#endif - -/* --- @MP_ALLOC@ --- * - * - * Arguments: @size_t sz@ = size required - * - * Returns: Pointer to an allocated vector of the requested size. - * - * Use: Hook for vector allocation. - */ - -#ifndef MP_ALLOC -# define MP_ALLOC(sz) mpalloc(MP_ARENA, (sz)) -#endif +/*----- Trivial macros ----------------------------------------------------*/ -/* --- @MP_FREE@ --- * - * - * Arguments: @mpw *v@ = pointer to vector +/* --- @MP_LEN@ --- * * - * Returns: --- + * Arguments: @mp *m@ = pointer to a multiprecision integer * - * Use: Hook for vector deallocation. + * Returns: Length of the integer, in words. */ -#ifndef MP_FREE -# define MP_FREE(v) mpfree(MP_ARENA, (v)) -#endif +#define MP_LEN(m) ((m)->vl - ((m)->v)) -/*----- Paranoia management -----------------------------------------------*/ +/*----- Memory management and reference counting --------------------------*/ -/* --- @mp_burn@ --- * +/* --- @mp_new@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer + * Arguments: @size_t sz@ = size of vector required + * @unsigned f@ = flags to set * - * Returns: --- + * Returns: Pointer to a new MP structure. * - * Use: Marks the integer as `burn-after-use'. When the integer's - * memory is deallocated, it is deleted so that traces can't - * remain in the swap file. In theory. + * Use: Allocates a new multiprecision integer. The data space is + * allocated from either the standard global or secret arena, + * depending on the initial flags requested. */ -extern void mp_burn(mp */*m*/); - -/*----- Trivial macros ----------------------------------------------------*/ +extern mp *mp_new(size_t /*sz*/, unsigned /*f*/); -/* --- @MP_LEN@ --- * +/* --- @mp_create@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer + * Arguments: @size_t sz@ = size of vector required * - * Returns: Length of the integer, in words. + * Returns: Pointer to pristine new MP structure with enough memory + * bolted onto it. + * + * Use: Creates a new multiprecision integer with indeterminate + * contents. The integer has a single reference. */ -#define MP_LEN(m) ((m)->vl - ((m)->v)) - -/*----- Memory management and reference counting --------------------------*/ +extern mp *mp_create(size_t /*sz*/); -/* --- @mp_create@ --- * +/* --- @mp_createsecure@ --- * * * Arguments: @size_t sz@ = size of vector required * @@ -173,10 +150,12 @@ extern void mp_burn(mp */*m*/); * bolted onto it. * * Use: Creates a new multiprecision integer with indeterminate - * contents. The integer has a single reference. + * contents. The integer has a single reference. The integer's + * data space is allocated from the secure arena. Its burn flag + * is set. */ -extern mp *mp_create(size_t /*sz*/); +extern mp *mp_createsecure(size_t /*sz*/); /* --- @mp_build@ --- * * @@ -235,12 +214,11 @@ extern void mp_drop(mp */*m*/); #define MP_DROP(m) do { \ mp *_mm = (m); \ - if (_mm->ref > 1) \ - _mm->ref--; \ - else if (!(_mm->f & MP_CONST)) \ + _mm->ref--; \ + if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \ mp_destroy(_mm); \ } while (0) - + /* --- @mp_split@ --- * * * Arguments: @mp *m@ = pointer to a multiprecision integer @@ -254,16 +232,16 @@ extern void mp_drop(mp */*m*/); extern mp *mp_split(mp */*m*/); #define MP_SPLIT(m) do { \ - mp *_mm = (m); \ - if ((_mm->f & MP_CONST) || _mm->ref != 1) { \ - mp *_dd = mp_create(_mm->sz); \ - _dd->vl = _dd->v + MP_LEN(_mm); \ - _dd->f = _mm->f & (MP_NEG | MP_BURN); \ - memcpy(_dd->v, _mm->v, MPWS(MP_LEN(_mm))); \ - _dd->ref = 1; \ - _mm->ref--; \ - (m) = _dd; \ + mp *_m = (m); \ + if ((_m->f & MP_CONST) || _m->ref > 1) { \ + size_t _len = MP_LEN(_m); \ + mp *_mm = mp_new(_len, _m->f); \ + if (!(_m->f & MP_UNDEF)) \ + memcpy(_mm->v, _m->v, MPWS(_len)); \ + _m->ref--; \ + _m = _mm; \ } \ + (m) = _m; \ } while (0) /* --- @mp_resize@ --- * @@ -275,9 +253,7 @@ extern mp *mp_split(mp */*m*/); * * Use: Resizes the vector containing the integer's digits. The new * size must be at least as large as the current integer's - * length. The integer's length is increased and new digits are - * filled with zeroes. This isn't really intended for client - * use. + * length. This isn't really intended for client use. */ extern void mp_resize(mp */*m*/, size_t /*sz*/); @@ -285,15 +261,19 @@ extern void mp_resize(mp */*m*/, size_t /*sz*/); #define MP_RESIZE(m, ssz) do { \ mp *_m = (m); \ size_t _sz = (ssz); \ + mparena *_a = (_m->f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL; \ + mpw *_v; \ size_t _len = MP_LEN(_m); \ - mpw *_v = MP_ALLOC(_sz); \ - memcpy(_v, _m->v, MPWS(_len)); \ + assert(((void)"can't make size less than length", _sz >= _len)); \ + _v = mpalloc(_a, _sz); \ + if (!(_m->f & MP_UNDEF)) \ + memcpy(_v, _m->v, MPWS(_len)); \ if (_m->f & MP_BURN) \ memset(_m->v, 0, MPWS(_m->sz)); \ - MP_FREE(_m->v); \ + mpfree(_m->a, _m->v); \ + _m->a = _a; \ _m->v = _v; \ _m->vl = _v + _len; \ - _m->sz = _sz; \ } while (0) /* --- @mp_ensure@ --- * @@ -310,41 +290,55 @@ extern void mp_resize(mp */*m*/, size_t /*sz*/); extern void mp_ensure(mp */*m*/, size_t /*sz*/); #define MP_ENSURE(m, ssz) do { \ - mp *_mm = (m); \ + mp *_m = (m); \ size_t _ssz = (ssz); \ - size_t _len = MP_LEN(_mm); \ - if (_ssz > _mm->sz) \ - MP_RESIZE(_mm, _ssz); \ - if (!(_mm->f & MP_UNDEF) && _ssz > _len) { \ - memset(_mm->vl, 0, MPWS(_ssz - _len)); \ - _mm->vl = _mm->v + _ssz; \ + size_t _len = MP_LEN(_m); \ + if (_ssz >= _len) { \ + if (_ssz > _m->sz) \ + mp_resize(_m, _ssz); \ + if (!(_m->f & MP_UNDEF) && _ssz > _len) \ + memset(_m->vl, 0, MPWS(_ssz - _len)); \ + _m->vl = _m->v + _ssz; \ } \ } while (0) -/* --- @mp_modify@ --- * +/* --- @mp_dest@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer - * @size_t sz@ = size required + * Arguments: @mp *m@ = a suggested destination integer + * @size_t sz@ = size required for result, in digits + * @unsigned f@ = various flags + * + * Returns: A pointer to an appropriate destination. + * + * Use: Converts a suggested destination into a real destination with + * the required properties. If the real destination is @d@, + * then the following properties will hold: + * + * * @d@ will have exactly one reference. + * + * * If @m@ is not @MP_NEW@, then the contents of @m@ will not + * change, unless @f@ has the @MP_UNDEF@ flag set. + * + * * If @m@ is not @MP_NEW@, then he reference count of @m@ on + * entry is equal to the sum of the counts of @d@ and @m@ on + * exit. + * + * * The size of @d@ will be at least @sz@. * - * Returns: Pointer to the integer (possibly different). + * * If @f@ has the @MP_BURN@ flag set, then @d@ will be + * allocated from @MPARENA_SECURE@. * - * Use: Prepares an integer to be overwritten. It's split off from - * other references to the same integer, and sufficient space is - * allocated. + * Understanding this function is crucial to using Catacomb's + * multiprecision integer library effectively. */ -extern mp *mp_modify(mp */*m*/, size_t /*sz*/); +extern mp *mp_dest(mp */*m*/, size_t /*sz*/, unsigned /*f*/); -#define MP_MODIFY(m, sz) do { \ - size_t _rq = (sz); \ +#define MP_DEST(m, ssz, f) do { \ mp *_m = (m); \ - if (_m == MP_NEW) \ - _m = mp_create(_rq); \ - else { \ - MP_SPLIT(_m); \ - MP_ENSURE(_m, _rq); \ - } \ - _m->vl = _m->v + _rq; \ + size_t _ssz = (ssz); \ + unsigned _f = (f); \ + _m = mp_dest(_m, _ssz, _f); \ (m) = _m; \ } while (0) @@ -369,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) @@ -388,7 +382,7 @@ extern void mp_minimize(mp */*m*/); /*----- Bit scanning ------------------------------------------------------*/ -#ifndef MPSCAN_H +#ifndef CATACOMB_MPSCAN_H # include "mpscan.h" #endif @@ -410,13 +404,36 @@ extern void mp_scan(mpscan */*sc*/, const mp */*m*/); MPSCAN_INITX(_sc, _mm->v, _mm->vl); \ } while (0) +/* --- @mp_rscan@ --- * + * + * Arguments: @mpscan *sc@ = pointer to bitscanner block + * @const mp *m@ = pointer to a multiprecision integer + * + * Returns: --- + * + * Use: Initializes a reverse bitscanner on a multiprecision + * integer. + */ + +extern void mp_rscan(mpscan */*sc*/, const mp */*m*/); + +#define MP_RSCAN(sc, m) do { \ + const mp *_mm = (m); \ + mpscan *_sc = (sc); \ + MPSCAN_RINITX(_sc, _mm->v, _mm->vl); \ +} while (0) + /* --- Other bitscanning aliases --- */ #define mp_step mpscan_step #define mp_bit mpscan_bit +#define mp_rstep mpscan_rstep +#define mp_rbit mpscan_rbit #define MP_STEP MPSCAN_STEP #define MP_BIT MPSCAN_BIT +#define MP_RSTEP MPSCAN_RSTEP +#define MP_RBIT MPSCAN_RBIT /*----- Loading and storing -----------------------------------------------*/ @@ -432,6 +449,18 @@ extern void mp_scan(mpscan */*sc*/, const mp */*m*/); extern size_t mp_octets(const mp */*m*/); +/* --- @mp_octets2c@ --- * + * + * Arguments: @const mp *m@ = a multiprecision integer + * + * Returns: The number of octets required to represent @m@. + * + * Use: Calculates the external storage required for a multiprecision + * integer represented as two's complement. + */ + +extern size_t mp_octets2c(const mp */*m*/); + /* --- @mp_bits@ --- * * * Arguments: @const mp *m@ = a multiprecision integer @@ -514,50 +543,243 @@ extern mp *mp_loadb(mp */*d*/, const void */*pv*/, size_t /*sz*/); extern void mp_storeb(const mp */*m*/, void */*pv*/, size_t /*sz*/); -/*----- Simple arithmetic -------------------------------------------------*/ +/* --- @mp_loadl2c@ --- * + * + * Arguments: @mp *d@ = destination + * @const void *pv@ = pointer to source data + * @size_t sz@ = size of the source data + * + * Returns: Resulting multiprecision number. + * + * Use: Loads a multiprecision number from an array of octets as + * two's complement. The first byte in the array is the least + * significant. + */ + +extern mp *mp_loadl2c(mp */*d*/, const void */*pv*/, size_t /*sz*/); -/* --- @mp_2c@ --- * +/* --- @mp_storel2c@ --- * + * + * Arguments: @const mp *m@ = source + * @void *pv@ = pointer to output array + * @size_t sz@ = size of the output array + * + * Returns: --- + * + * Use: Stores a multiprecision number in an array of octets as two's + * complement. The first byte in the array is the least + * significant. If the array is too small to represent the + * number, high-order bits are truncated; if the array is too + * large, high order bytes are sign-extended. + */ + +extern void mp_storel2c(const mp */*m*/, void */*pv*/, size_t /*sz*/); + +/* --- @mp_loadb2c@ --- * * * Arguments: @mp *d@ = destination - * @mp *a@ = source + * @const void *pv@ = pointer to source data + * @size_t sz@ = size of the source data * - * Returns: Result, @a@ converted to two's complement notation. + * Returns: Resulting multiprecision number. + * + * Use: Loads a multiprecision number from an array of octets as + * two's complement. The last byte in the array is the least + * significant. + */ + +extern mp *mp_loadb2c(mp */*d*/, const void */*pv*/, size_t /*sz*/); + +/* --- @mp_storeb2c@ --- * + * + * Arguments: @const mp *m@ = source + * @void *pv@ = pointer to output array + * @size_t sz@ = size of the output array + * + * Returns: --- + * + * Use: Stores a multiprecision number in an array of octets, as + * two's complement. The last byte in the array is the least + * significant. If the array is too small to represent the + * number, high-order bits are truncated; if the array is too + * large, high order bytes are sign-extended. */ -extern mp *mp_2c(mp */*d*/, mp */*a*/); +extern void mp_storeb2c(const mp */*m*/, void */*pv*/, size_t /*sz*/); -/* --- @mp_sm@ --- * +/*----- Bit operations ----------------------------------------------------*/ + +/* --- @mp_not@ --- * * * Arguments: @mp *d@ = destination * @mp *a@ = source * - * Returns: Result, @a@ converted to the native signed-magnitude - * notation. + * Returns: The bitwise complement of the source. */ -extern mp *mp_sm(mp */*d*/, mp */*a*/); +extern mp *mp_not(mp */*d*/, mp */*a*/); -/* --- @mp_lsl@ --- * +/* --- @mp_bitop@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a@ = source + * @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: + * + * 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@ --- * + * + * Synonyms for the commonly-used functions. + */ + +#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_testbit@ --- * + * + * Arguments: @mp *x@ = a large integer + * @unsigned long n@ = which bit to test + * + * Returns: Nonzero if the bit is set, zero if not. + */ + +extern int mp_testbit(mp */*x*/, unsigned long /*n*/); + +/* --- @mp_setbit@, @mp_clearbit@ --- * + * + * 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. + */ + +extern mp *mp_setbit(mp */*d*/, mp */*x*/, unsigned long /*n*/); +extern mp *mp_clearbit(mp */*d*/, mp */*x*/, unsigned long /*n*/); + +/* --- @mp_lsl@, @mp_lslc@, @mp_lsr@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a@ = source * @size_t n@ = number of bits to move * - * Returns: Result, @a@ shifted left by @n@. + * Returns: Result, @a@ shifted left or right by @n@. + * + * 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. + */ + +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_not2c@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a@ = source + * + * Returns: The sign-extended complement of the argument. */ -extern mp *mp_lsl(mp */*d*/, const mp */*a*/, size_t /*n*/); +extern mp *mp_not2c(mp */*d*/, mp */*a*/); -/* --- @mp_lsr@ --- * +/* --- @mp_bitop2c@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a@ = source + * @mp *a, *b@ = sources + * + * Returns: The result of the given bitwise operation. Negative numbers + * are treated as two's complement, sign-extended infinitely to + * the left. The functions are named after the truth tables + * they generate: + * + * a: 0011 + * b: 0101 + * @mpx_bitXXXX@ + */ + +#define MP_BIT2CDECL(string) \ + extern mp *mp_bit##string##2c(mp */*d*/, mp */*a*/, mp */*b*/); +MPX_DOBIN(MP_BIT2CDECL) + +/* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- * + * + * Synonyms for the commonly-used functions. + */ + +#define mp_and2c mp_bit00012c +#define mp_or2c mp_bit01112c +#define mp_nand2c mp_bit11102c +#define mp_nor2c mp_bit10002c +#define mp_xor2c mp_bit01102c + +/* --- @mp_lsl2c@, @mp_lsr2c@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a@ = source * @size_t n@ = number of bits to move * - * Returns: Result, @a@ shifted left by @n@. + * 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_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 mp *mp_lsr(mp */*d*/, const mp */*a*/, size_t /*n*/); +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@ --- * * @@ -571,60 +793,123 @@ 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@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a, *b@ = sources + * @mp *a, *b@ = sources * * Returns: Result, @a@ added to @b@. */ -extern mp *mp_add(mp */*d*/, const mp */*a*/, const mp */*b*/); +extern mp *mp_add(mp */*d*/, mp */*a*/, mp */*b*/); /* --- @mp_sub@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a, *b@ = sources + * @mp *a, *b@ = sources * * Returns: Result, @b@ subtracted from @a@. */ -extern mp *mp_sub(mp */*d*/, const mp */*a*/, const mp */*b*/); +extern mp *mp_sub(mp */*d*/, mp */*a*/, mp */*b*/); /* --- @mp_mul@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a, *b@ = sources + * @mp *a, *b@ = sources * * Returns: Result, @a@ multiplied by @b@. */ -extern mp *mp_mul(mp */*d*/, const mp */*a*/, const mp */*b*/); +extern mp *mp_mul(mp */*d*/, mp */*a*/, mp */*b*/); /* --- @mp_sqr@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a@ = source + * @mp *a@ = source * * Returns: Result, @a@ squared. */ -extern mp *mp_sqr(mp */*d*/, const mp */*a*/); +extern mp *mp_sqr(mp */*d*/, mp */*a*/); /* --- @mp_div@ --- * * * Arguments: @mp **qq, **rr@ = destination, quotient and remainder - * @const mp *a, *b@ = sources + * @mp *a, *b@ = sources * * Use: Calculates the quotient and remainder when @a@ is divided by * @b@. */ -extern void mp_div(mp **/*qq*/, mp **/*rr*/, - const mp */*a*/, const mp */*b*/); +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 + * @mp *m@ = pointer to source integer + * @size_t *s@ = where to store the power of 2 + * + * Returns: An odd integer integer %$t$% such that %$m = 2^s t$%. + * + * Use: Computes a power of two and an odd integer which, when + * multiplied, give a specified result. This sort of thing is + * useful in number theory quite often. + */ + +extern mp *mp_odd(mp */*d*/, mp */*m*/, size_t */*s*/); /*----- More advanced algorithms ------------------------------------------*/ +/* --- @mp_sqrt@ --- * + * + * Arguments: @mp *d@ = pointer to destination integer + * @mp *a@ = (nonnegative) integer to take square root of + * + * Returns: The largest integer %$x$% such that %$x^2 \le a$%. + * + * Use: Computes integer square roots. + * + * The current implementation isn't very good: it uses the + * Newton-Raphson method to find an approximation to %$a$%. If + * there's any demand for a better version, I'll write one. + */ + +extern mp *mp_sqrt(mp */*d*/, mp */*a*/); + /* --- @mp_gcd@ --- * * * Arguments: @mp **gcd, **xx, **yy@ = where to write the results @@ -634,34 +919,99 @@ extern void mp_div(mp **/*qq*/, mp **/*rr*/, * * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that * @ax + by = gcd(a, b)@. This is useful for computing modular - * inverses. Neither @a@ nor @b@ may be zero. Note that, - * unlike @mp_div@ for example, it is not possible to specify - * explicit destinations -- new MPs are always allocated. + * inverses. Neither @a@ nor @b@ may be zero. */ 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*/); + +/* --- @mp_modsqrt@ --- * + * + * Arguments: @mp *d@ = destination integer + * @mp *a@ = source integer + * @mp *p@ = modulus (must be prime) + * + * Returns: If %$a$% is a quadratic residue, a square root of %$a$%; else + * a null pointer. + * + * Use: Returns an integer %$x$% such that %$x^2 \equiv a \pmod{p}$%, + * if one exists; else a null pointer. This function will not + * 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$%. */ -int mp_jacobi(mp */*a*/, mp */*n*/); +extern mp *mp_modexp(mp */*d*/, mp */*x*/, mp */*e*/, mp */*n*/); /*----- Test harness support ----------------------------------------------*/ #include -#ifndef MPTEXT_H +#ifndef CATACOMB_MPTEXT_H # include "mptext.h" #endif