|
1
|
1 /* |
|
|
2 mpi.h |
|
|
3 |
|
|
4 by Michael J. Fromberger <[email protected]> |
|
|
5 Copyright (C) 1998 Michael J. Fromberger, All Rights Reserved |
|
|
6 |
|
|
7 Arbitrary precision integer arithmetic library |
|
|
8 |
|
2
|
9 $Id: mpi.h,v 1.15 2001/09/17 14:16:22 sting Exp $ |
|
1
|
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_ */ |
