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