/* -*-c-*-
*
- * $Id: mp.h,v 1.4 1999/11/21 22:13:02 mdw Exp $
+ * $Id$
*
* Simple multiprecision arithmetic
*
* (c) 1999 Straylight/Edgeware
*/
-/*----- Licensing notice --------------------------------------------------*
+/*----- Licensing notice --------------------------------------------------*
*
* This file is part of Catacomb.
*
* 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.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" {
#include <mLib/sub.h>
-#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*/);
+extern mp *mp_new(size_t /*sz*/, unsigned /*f*/);
-/*----- Trivial macros ----------------------------------------------------*/
-
-/* --- @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
*
* 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@ --- *
*
#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
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@ --- *
*
* 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*/);
#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@ --- *
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.
*
- * Returns: Pointer to the integer (possibly different).
+ * 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:
*
- * Use: Prepares an integer to be overwritten. It's split off from
- * other references to the same integer, and sufficient space is
- * allocated.
+ * * @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@.
+ *
+ * * If @f@ has the @MP_BURN@ flag set, then @d@ will be
+ * allocated from @MPARENA_SECURE@.
+ *
+ * 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)
#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)
/*----- Bit scanning ------------------------------------------------------*/
-#ifndef MPSCAN_H
+#ifndef CATACOMB_MPSCAN_H
# include "mpscan.h"
#endif
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 -----------------------------------------------*/
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
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_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.
+ */
-/* --- @mp_2c@ --- *
+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_2c(mp */*d*/, mp */*a*/);
+extern mp *mp_loadb2c(mp */*d*/, const void */*pv*/, size_t /*sz*/);
-/* --- @mp_sm@ --- *
+/* --- @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 void mp_storeb2c(const mp */*m*/, void */*pv*/, size_t /*sz*/);
+
+/*----- 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_not(mp */*d*/, mp */*a*/);
+
+/* --- @mp_bitop@ --- *
+ *
+ * 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:
+ *
+ * a: 0011
+ * b: 0101
+ * @mpx_bitXXXX@
*/
-extern mp *mp_sm(mp */*d*/, mp */*a*/);
+#define MP_BITDECL(string) \
+ extern mp *mp_bit##string(mp */*d*/, mp */*a*/, mp */*b*/);
+MPX_DOBIN(MP_BITDECL)
-/* --- @mp_lsl@ --- *
+/* --- @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
- * @const mp *a@ = source
+ * @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*/, const mp */*a*/, size_t /*n*/);
+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_lsr@ --- *
+/* --- @mp_not2c@ --- *
*
* Arguments: @mp *d@ = destination
- * @const mp *a@ = source
+ * @mp *a@ = source
+ *
+ * Returns: The sign-extended complement of the argument.
+ */
+
+extern mp *mp_not2c(mp */*d*/, mp */*a*/);
+
+/* --- @mp_bitop2c@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @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@ --- *
*
#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
*
* 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
+ * @mp *n@ = another integer
+ *
+ * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
+ *
+ * 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$%.
+ */
+
+extern mp *mp_modexp(mp */*d*/, mp */*x*/, mp */*e*/, mp */*n*/);
+
/*----- Test harness support ----------------------------------------------*/
#include <mLib/testrig.h>
-#ifndef MPTEXT_H
+#ifndef CATACOMB_MPTEXT_H
# include "mptext.h"
#endif
projects / u / mdw / catacomb / blobdiff