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