1 /* 2 mpi.h 3 4 by Michael J. Fromberger <sting (at) linguist.dartmouth.edu> 5 Copyright (C) 1998 Michael J. Fromberger, All Rights Reserved 6 7 Arbitrary precision integer arithmetic library 8 9 $Id: mpi.h,v 1.2 2005/05/05 14:38:47 tom Exp $ 10 */ 11 12 #ifndef _H_MPI_ 13 #define _H_MPI_ 14 15 #include "mpi-config.h" 16 17 #define MP_LT -1 18 #define MP_EQ 0 19 #define MP_GT 1 20 21 #if MP_DEBUG 22 #undef MP_IOFUNC 23 #define MP_IOFUNC 1 24 #endif 25 26 #if MP_IOFUNC 27 #include <stdio.h> 28 #include <ctype.h> 29 #endif 30 31 #include <limits.h> 32 33 #define MP_NEG 1 34 #define MP_ZPOS 0 35 36 /* Included for compatibility... */ 37 #define NEG MP_NEG 38 #define ZPOS MP_ZPOS 39 40 #define MP_OKAY 0 /* no error, all is well */ 41 #define MP_YES 0 /* yes (boolean result) */ 42 #define MP_NO -1 /* no (boolean result) */ 43 #define MP_MEM -2 /* out of memory */ 44 #define MP_RANGE -3 /* argument out of range */ 45 #define MP_BADARG -4 /* invalid parameter */ 46 #define MP_UNDEF -5 /* answer is undefined */ 47 #define MP_LAST_CODE MP_UNDEF 48 49 #include "mpi-types.h" 50 51 /* Included for compatibility... */ 52 #define DIGIT_BIT MP_DIGIT_BIT 53 #define DIGIT_MAX MP_DIGIT_MAX 54 55 /* Macros for accessing the mp_int internals */ 56 #define SIGN(MP) ((MP)->sign) 57 #define USED(MP) ((MP)->used) 58 #define ALLOC(MP) ((MP)->alloc) 59 #define DIGITS(MP) ((MP)->dp) 60 #define DIGIT(MP,N) (MP)->dp[(N)] 61 62 #if MP_ARGCHK == 1 63 #define ARGCHK(X,Y) {if(!(X)){return (Y);}} 64 #elif MP_ARGCHK == 2 65 #include <assert.h> 66 #define ARGCHK(X,Y) assert(X) 67 #else 68 #define ARGCHK(X,Y) /* */ 69 #endif 70 71 /* This defines the maximum I/O base (minimum is 2) */ 72 #define MAX_RADIX 64 73 74 typedef struct { 75 mp_sign sign; /* sign of this quantity */ 76 mp_size alloc; /* how many digits allocated */ 77 mp_size used; /* how many digits used */ 78 mp_digit *dp; /* the digits themselves */ 79 } mp_int; 80 81 /*------------------------------------------------------------------------*/ 82 /* Default precision */ 83 84 unsigned int mp_get_prec(void); 85 void mp_set_prec(unsigned int prec); 86 87 /*------------------------------------------------------------------------*/ 88 /* Memory management */ 89 90 mp_err mp_init(mp_int *mp); 91 mp_err mp_init_array(mp_int mp[], int count); 92 mp_err mp_init_size(mp_int *mp, mp_size prec); 93 mp_err mp_init_copy(mp_int *mp, mp_int *from); 94 mp_err mp_copy(mp_int *from, mp_int *to); 95 void mp_exch(mp_int *mp1, mp_int *mp2); 96 void mp_clear(mp_int *mp); 97 void mp_clear_array(mp_int mp[], int count); 98 void mp_zero(mp_int *mp); 99 void mp_set(mp_int *mp, mp_digit d); 100 mp_err mp_set_int(mp_int *mp, long z); 101 mp_err mp_shrink(mp_int *a); 102 103 104 /*------------------------------------------------------------------------*/ 105 /* Single digit arithmetic */ 106 107 mp_err mp_add_d(mp_int *a, mp_digit d, mp_int *b); 108 mp_err mp_sub_d(mp_int *a, mp_digit d, mp_int *b); 109 mp_err mp_mul_d(mp_int *a, mp_digit d, mp_int *b); 110 mp_err mp_mul_2(mp_int *a, mp_int *c); 111 mp_err mp_div_d(mp_int *a, mp_digit d, mp_int *q, mp_digit *r); 112 mp_err mp_div_2(mp_int *a, mp_int *c); 113 mp_err mp_expt_d(mp_int *a, mp_digit d, mp_int *c); 114 115 /*------------------------------------------------------------------------*/ 116 /* Sign manipulations */ 117 118 mp_err mp_abs(mp_int *a, mp_int *b); 119 mp_err mp_neg(mp_int *a, mp_int *b); 120 121 /*------------------------------------------------------------------------*/ 122 /* Full arithmetic */ 123 124 mp_err mp_add(mp_int *a, mp_int *b, mp_int *c); 125 mp_err mp_sub(mp_int *a, mp_int *b, mp_int *c); 126 mp_err mp_mul(mp_int *a, mp_int *b, mp_int *c); 127 mp_err mp_mul_2d(mp_int *a, mp_digit d, mp_int *c); 128 #if MP_SQUARE 129 mp_err mp_sqr(mp_int *a, mp_int *b); 130 #else 131 #define mp_sqr(a, b) mp_mul(a, a, b) 132 #endif 133 mp_err mp_div(mp_int *a, mp_int *b, mp_int *q, mp_int *r); 134 mp_err mp_div_2d(mp_int *a, mp_digit d, mp_int *q, mp_int *r); 135 mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c); 136 mp_err mp_2expt(mp_int *a, mp_digit k); 137 mp_err mp_sqrt(mp_int *a, mp_int *b); 138 139 /*------------------------------------------------------------------------*/ 140 /* Modular arithmetic */ 141 142 #if MP_MODARITH 143 mp_err mp_mod(mp_int *a, mp_int *m, mp_int *c); 144 mp_err mp_mod_d(mp_int *a, mp_digit d, mp_digit *c); 145 mp_err mp_addmod(mp_int *a, mp_int *b, mp_int *m, mp_int *c); 146 mp_err mp_submod(mp_int *a, mp_int *b, mp_int *m, mp_int *c); 147 mp_err mp_mulmod(mp_int *a, mp_int *b, mp_int *m, mp_int *c); 148 #if MP_SQUARE 149 mp_err mp_sqrmod(mp_int *a, mp_int *m, mp_int *c); 150 #else 151 #define mp_sqrmod(a, m, c) mp_mulmod(a, a, m, c) 152 #endif 153 mp_err mp_exptmod(mp_int *a, mp_int *b, mp_int *m, mp_int *c); 154 mp_err mp_exptmod_d(mp_int *a, mp_digit d, mp_int *m, mp_int *c); 155 #endif /* MP_MODARITH */ 156 157 /*------------------------------------------------------------------------*/ 158 /* Comparisons */ 159 160 int mp_cmp_z(mp_int *a); 161 int mp_cmp_d(mp_int *a, mp_digit d); 162 int mp_cmp(mp_int *a, mp_int *b); 163 int mp_cmp_mag(mp_int *a, mp_int *b); 164 int mp_cmp_int(mp_int *a, long z); 165 int mp_isodd(mp_int *a); 166 int mp_iseven(mp_int *a); 167 168 /*------------------------------------------------------------------------*/ 169 /* Number theoretic */ 170 171 #if MP_NUMTH 172 mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c); 173 mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c); 174 mp_err mp_xgcd(mp_int *a, mp_int *b, mp_int *g, mp_int *x, mp_int *y); 175 mp_err mp_invmod(mp_int *a, mp_int *m, mp_int *c); 176 #endif /* end MP_NUMTH */ 177 178 /*------------------------------------------------------------------------*/ 179 /* Input and output */ 180 181 #if MP_IOFUNC 182 void mp_print(mp_int *mp, FILE *ofp); 183 #endif /* end MP_IOFUNC */ 184 185 /*------------------------------------------------------------------------*/ 186 /* Base conversion */ 187 188 #define BITS 1 189 #define BYTES CHAR_BIT 190 191 mp_err mp_read_signed_bin(mp_int *mp, unsigned char *str, int len); 192 int mp_signed_bin_size(mp_int *mp); 193 mp_err mp_to_signed_bin(mp_int *mp, unsigned char *str); 194 195 mp_err mp_read_unsigned_bin(mp_int *mp, unsigned char *str, int len); 196 int mp_unsigned_bin_size(mp_int *mp); 197 mp_err mp_to_unsigned_bin(mp_int *mp, unsigned char *str); 198 199 int mp_count_bits(mp_int *mp); 200 201 #if MP_COMPAT_MACROS 202 #define mp_read_raw(mp, str, len) mp_read_signed_bin((mp), (str), (len)) 203 #define mp_raw_size(mp) mp_signed_bin_size(mp) 204 #define mp_toraw(mp, str) mp_to_signed_bin((mp), (str)) 205 #define mp_read_mag(mp, str, len) mp_read_unsigned_bin((mp), (str), (len)) 206 #define mp_mag_size(mp) mp_unsigned_bin_size(mp) 207 #define mp_tomag(mp, str) mp_to_unsigned_bin((mp), (str)) 208 #endif 209 210 mp_err mp_read_radix(mp_int *mp, unsigned char *str, int radix); 211 int mp_radix_size(mp_int *mp, int radix); 212 int mp_value_radix_size(int num, int qty, int radix); 213 mp_err mp_toradix(mp_int *mp, unsigned char *str, int radix); 214 215 int mp_char2value(char ch, int r); 216 217 #define mp_tobinary(M, S) mp_toradix((M), (S), 2) 218 #define mp_tooctal(M, S) mp_toradix((M), (S), 8) 219 #define mp_todecimal(M, S) mp_toradix((M), (S), 10) 220 #define mp_tohex(M, S) mp_toradix((M), (S), 16) 221 222 /*------------------------------------------------------------------------*/ 223 /* Error strings */ 224 225 const char *mp_strerror(mp_err ec); 226 227 #endif /* end _H_MPI_ */ 228 229 /* $Source: /cvs/libtom/libtommath/mtest/mpi.h,v $ */ 230 /* $Revision: 1.2 $ */ 231 /* $Date: 2005/05/05 14:38:47 $ */ 232
