libtommath.h (6423B)
1 #include <tommath.h> 2 3 #include <setjmp.h> 4 #include <stddef.h> 5 #include <stdint.h> 6 #include <stdio.h> 7 8 #define BIGINT_LIBRARY "libtommath" 9 10 #define FAST_RANDOM 0 11 #define SECURE_RANDOM 0 12 #define DEFAULT_RANDOM 0 13 #define FASTEST_RANDOM 0 14 #define LIBC_RAND_RANDOM 0 15 #define LIBC_RANDOM_RANDOM 0 16 #define LIBC_RAND48_RANDOM 0 17 #define QUASIUNIFORM 0 18 #define UNIFORM 1 19 #define MODUNIFORM 2 20 21 typedef mp_int z_t[1]; 22 23 static z_t _0, _1, _a, _b; 24 static int _tmp, error; 25 static jmp_buf jbuf; 26 27 #ifdef ZAHL_UNSAFE 28 # define try(expr) (expr) 29 #else 30 # define try(expr) do if ((error = (expr))) longjmp(jbuf, 1); while (0) 31 #endif 32 33 static inline void 34 zsetup(jmp_buf env) 35 { 36 *jbuf = *env; 37 try(mp_init_set_int(_0, 0)); 38 try(mp_init_set_int(_1, 1)); 39 try(mp_init(_a)); 40 try(mp_init(_b)); 41 } 42 43 static inline void 44 zunsetup(void) 45 { 46 mp_clear(_0); 47 mp_clear(_1); 48 mp_clear(_a); 49 mp_clear(_b); 50 } 51 52 static inline void 53 zperror(const char *str) 54 { 55 if (str && *str) 56 fprintf(stderr, "%s: %s\n", str, mp_error_to_string(error)); 57 else 58 fprintf(stderr, "%s\n", mp_error_to_string(error)); 59 } 60 61 static inline void 62 zinit(z_t a) 63 { 64 try(mp_init(a)); 65 } 66 67 static inline void 68 zfree(z_t a) 69 { 70 mp_clear(a); 71 } 72 73 static inline void 74 zset(z_t r, z_t a) 75 { 76 try(mp_copy(a, r)); 77 } 78 79 static inline void 80 zneg(z_t r, z_t a) 81 { 82 try(mp_neg(a, r)); 83 } 84 85 static inline void 86 zabs(z_t r, z_t a) 87 { 88 try(mp_abs(a, r)); 89 } 90 91 static inline void 92 zadd(z_t r, z_t a, z_t b) 93 { 94 try(mp_add(a, b, r)); 95 } 96 97 static inline void 98 zsub(z_t r, z_t a, z_t b) 99 { 100 try(mp_sub(a, b, r)); 101 } 102 103 static inline void 104 zadd_unsigned(z_t r, z_t a, z_t b) 105 { 106 zabs(_a, a); 107 zabs(_b, b); 108 zadd(r, _a, _b); 109 } 110 111 static inline void 112 zsub_unsigned(z_t r, z_t a, z_t b) 113 { 114 zabs(_a, a); 115 zabs(_b, b); 116 zsub(r, _a, _b); 117 } 118 119 static inline size_t 120 zbits(z_t a) 121 { 122 return mp_count_bits(a); 123 } 124 125 static inline size_t 126 zlsb(z_t a) 127 { 128 return mp_cnt_lsb(a); 129 } 130 131 static inline int 132 zeven(z_t a) 133 { 134 return mp_iseven(a); 135 } 136 137 static inline int 138 zodd(z_t a) 139 { 140 return mp_isodd(a); 141 } 142 143 static inline int 144 zeven_nonzero(z_t a) 145 { 146 return zeven(a); 147 } 148 149 static inline int 150 zodd_nonzero(z_t a) 151 { 152 return zodd(a); 153 } 154 155 static inline int 156 zzero(z_t a) 157 { 158 return mp_iszero(a); 159 } 160 161 static inline void 162 zand(z_t r, z_t a, z_t b) 163 { 164 try(mp_and(a, b, r)); 165 } 166 167 static inline void 168 zor(z_t r, z_t a, z_t b) 169 { 170 try(mp_or(a, b, r)); 171 } 172 173 static inline void 174 zxor(z_t r, z_t a, z_t b) 175 { 176 try(mp_xor(a, b, r)); 177 } 178 179 static inline void 180 znot(z_t r, z_t a) 181 { 182 try(mp_2expt(_a, (int)zbits(a))); 183 try(mp_sub_d(_a, 1, _a)); 184 zand(r, a, _a); 185 zneg(r, r); 186 } 187 188 static inline int 189 zbtest(z_t a, size_t bit) 190 { 191 try(mp_2expt(_b, (int)bit)); 192 zand(_b, a, _b); 193 return !zzero(_b); 194 } 195 196 static inline void 197 zbset(z_t r, z_t a, size_t bit, int mode) 198 { 199 if (mode > 0) { 200 try(mp_2expt(_b, (int)bit)); 201 zor(r, a, _b); 202 } else if (mode < 0 || zbtest(a, bit)) { 203 try(mp_2expt(_b, (int)bit)); 204 zxor(r, a, _b); 205 } 206 } 207 208 static inline void 209 zswap(z_t a, z_t b) 210 { 211 mp_exch(a, b); 212 } 213 214 static inline void 215 zlsh(z_t r, z_t a, size_t b) 216 { 217 try(mp_mul_2d(a, (int)b, r)); 218 } 219 220 static inline void 221 zrsh(z_t r, z_t a, size_t b) 222 { 223 try(mp_div_2d(a, (int)b, r, 0)); 224 } 225 226 static inline void 227 ztrunc(z_t r, z_t a, size_t b) 228 { 229 try(mp_mod_2d(a, (int)b, r)); 230 } 231 232 static inline void 233 zsplit(z_t high, z_t low, z_t a, size_t brk) 234 { 235 if (low == a) { 236 zrsh(high, a, brk); 237 ztrunc(low, a, brk); 238 } else { 239 ztrunc(low, a, brk); 240 zrsh(high, a, brk); 241 } 242 } 243 244 static inline void 245 zsetu(z_t r, unsigned long long int val) 246 { 247 try(mp_set_long_long(r, val)); 248 } 249 250 static inline void 251 zseti(z_t r, long long int val) 252 { 253 if (val >= 0) { 254 zsetu(r, (unsigned long long int)val); 255 } else { 256 zsetu(r, (unsigned long long int)-val); 257 zneg(r, r); 258 } 259 } 260 261 static inline int 262 zcmpmag(z_t a, z_t b) 263 { 264 return mp_cmp_mag(a, b); 265 } 266 267 static inline int 268 zcmp(z_t a, z_t b) 269 { 270 return mp_cmp(a, b); 271 } 272 273 static inline int 274 zcmpi(z_t a, long long int b) 275 { 276 zseti(_b, b); 277 return zcmp(a, _b); 278 } 279 280 static inline int 281 zcmpu(z_t a, unsigned long long int b) 282 { 283 zsetu(_b, b); 284 return zcmp(a, _b); 285 } 286 287 static inline int 288 zsignum(z_t a) 289 { 290 return zcmp(a, _0); 291 } 292 293 static inline void 294 zgcd(z_t r, z_t a, z_t b) 295 { 296 try(mp_gcd(a, b, r)); 297 } 298 299 static inline void 300 zmul(z_t r, z_t a, z_t b) 301 { 302 try(mp_mul(a, b, r)); 303 } 304 305 static inline void 306 zsqr(z_t r, z_t a) 307 { 308 try(mp_sqr(a, r)); 309 } 310 311 static inline void 312 zmodmul(z_t r, z_t a, z_t b, z_t m) 313 { 314 try(mp_mulmod(a, b, m, r)); 315 } 316 317 static inline void 318 zmodsqr(z_t r, z_t a, z_t m) 319 { 320 try(mp_sqrmod(a, m, r)); 321 } 322 323 static inline void 324 zpow(z_t r, z_t a, z_t b) 325 { 326 try(mp_expt_d(a, (mp_digit)mp_get_int(b), r)); 327 } 328 329 static inline void 330 zpowu(z_t r, z_t a, unsigned long long int b) 331 { 332 try(mp_expt_d(a, (mp_digit)b, r)); 333 } 334 335 static inline void 336 zmodpow(z_t r, z_t a, z_t b, z_t m) 337 { 338 try(mp_exptmod(a, b, m, r)); 339 } 340 341 static inline void 342 zmodpowu(z_t r, z_t a, unsigned long long int b, z_t m) 343 { 344 try(mp_set_int(_b, b)); 345 try(mp_exptmod(a, _b, m, r)); 346 } 347 348 static inline void 349 zsets(z_t a, const char *s) 350 { 351 try(mp_read_radix(a, s, 10)); 352 } 353 354 static inline size_t 355 zstr_length(z_t a, size_t b) 356 { 357 try(mp_radix_size(a, b, &_tmp)); 358 return _tmp; 359 } 360 361 static inline char * 362 zstr(z_t a, char *s, size_t n) 363 { 364 try(mp_toradix(a, s, 10)); 365 return s; 366 (void) n; 367 } 368 369 static inline int 370 zptest(z_t w, z_t a, int t) 371 { 372 try(mp_prime_is_prime(a, t, &_tmp)); 373 return _tmp; 374 (void) w; /* Note, the witness is not returned. */ 375 } 376 377 static inline size_t 378 zsave(z_t a, char *b) 379 { 380 _tmp = !b ? mp_signed_bin_size(a) : mp_to_signed_bin(a, (unsigned char *)b); 381 return _tmp; 382 } 383 384 static inline size_t 385 zload(z_t a, const char *b) /* Note, requires that zsave was called directly prior. */ 386 { 387 return mp_read_signed_bin(a, (const unsigned char *)b, _tmp); 388 } 389 390 static inline void 391 zdiv(z_t r, z_t a, z_t b) 392 { 393 try(mp_div(a, b, r, 0)); 394 } 395 396 static inline void 397 zmod(z_t r, z_t a, z_t b) 398 { 399 try(mp_mod(a, b, r)); 400 } 401 402 static inline void 403 zdivmod(z_t q, z_t r, z_t a, z_t b) 404 { 405 try(mp_div(a, b, q, r)); 406 } 407 408 static inline void 409 zrand(z_t r, int dev, int dist, z_t n) 410 { 411 static int gave_up = 0; 412 int bits; 413 (void) dev; 414 415 if (zzero(n)) { 416 mp_zero(r); 417 return; 418 } 419 if (zsignum(n) < 0) { 420 return; 421 } 422 423 bits = zbits(n); 424 425 switch (dist) { 426 case QUASIUNIFORM: 427 try(mp_rand(r, bits)); 428 zadd(r, r, _1); 429 zmul(r, r, n); 430 zrsh(r, r, bits); 431 break; 432 433 case UNIFORM: 434 if (!gave_up) { 435 gave_up = 1; 436 printf("I'm sorry, this is too difficult, I give up.\n"); 437 } 438 break; 439 440 case MODUNIFORM: 441 try(mp_rand(r, bits)); 442 if (zcmp(r, n) > 0) 443 zsub(r, r, n); 444 break; 445 446 default: 447 abort(); 448 } 449 }