Commit | Line | Data |
---|---|---|
d03ab969 | 1 | /* -*-c-*- |
d03ab969 | 2 | * |
d3409d5e | 3 | * Simple multiprecision arithmetic |
d03ab969 | 4 | * |
5 | * (c) 1999 Straylight/Edgeware | |
6 | */ | |
7 | ||
45c0fd36 | 8 | /*----- Licensing notice --------------------------------------------------* |
d03ab969 | 9 | * |
10 | * This file is part of Catacomb. | |
11 | * | |
12 | * Catacomb is free software; you can redistribute it and/or modify | |
13 | * it under the terms of the GNU Library General Public License as | |
14 | * published by the Free Software Foundation; either version 2 of the | |
15 | * License, or (at your option) any later version. | |
45c0fd36 | 16 | * |
d03ab969 | 17 | * Catacomb is distributed in the hope that it will be useful, |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
20 | * GNU Library General Public License for more details. | |
45c0fd36 | 21 | * |
d03ab969 | 22 | * You should have received a copy of the GNU Library General Public |
23 | * License along with Catacomb; if not, write to the Free | |
24 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
25 | * MA 02111-1307, USA. | |
26 | */ | |
27 | ||
d9a8ae10 | 28 | #ifndef CATACOMB_MP_H |
29 | #define CATACOMB_MP_H | |
d03ab969 | 30 | |
31 | #ifdef __cplusplus | |
32 | extern "C" { | |
33 | #endif | |
34 | ||
35 | /*----- Header files ------------------------------------------------------*/ | |
36 | ||
d3409d5e | 37 | #include <assert.h> |
d03ab969 | 38 | #include <string.h> |
39 | ||
a6d8eb54 | 40 | #include <mLib/macros.h> |
d3409d5e | 41 | #include <mLib/sub.h> |
42 | ||
d9a8ae10 | 43 | #ifndef CATACOMB_MPW_H |
d3409d5e | 44 | # include "mpw.h" |
d03ab969 | 45 | #endif |
46 | ||
d34decd2 | 47 | #ifndef CATACOMB_ARENA_H |
48 | # include "arena.h" | |
49 | #endif | |
50 | ||
51 | #ifndef CATACOMB_MPARENA_H | |
52 | # include "mparena.h" | |
53 | #endif | |
54 | ||
d9a8ae10 | 55 | #ifndef CATACOMB_MPX_H |
d03ab969 | 56 | # include "mpx.h" |
57 | #endif | |
58 | ||
d03ab969 | 59 | /*----- Data structures ---------------------------------------------------*/ |
60 | ||
3bc0a0fe | 61 | /* --- A multiprecision integer --- */ |
62 | ||
d03ab969 | 63 | typedef struct mp { |
3bc0a0fe | 64 | mpw *v, *vl; /* Vector of digits, current limit */ |
65 | size_t sz; /* Size of digit buffer in words */ | |
66 | mparena *a; /* Arena for buffer allocation */ | |
67 | unsigned f; /* Flags (see below) */ | |
68 | unsigned ref; /* Reference counter */ | |
d03ab969 | 69 | } mp; |
70 | ||
3bc0a0fe | 71 | #define MP_NEG 1u /* Negative (signed magnitude) */ |
72 | #define MP_BURN 2u /* Secret (viral flag) */ | |
73 | #define MP_CONST 4u /* Uses strange memory allocation */ | |
74 | #define MP_UNDEF 8u /* Contains nothing interesting */ | |
75 | #define MP_DESTROYED 16u /* Has been destroyed */ | |
76 | ||
77 | /* --- A factor for simultaneous exponentation --- * | |
78 | * | |
79 | * Used by the Montgomery and Barrett exponentiators. | |
80 | */ | |
81 | ||
82 | typedef struct mp_expfactor { | |
83 | mp *base; | |
84 | mp *exp; | |
85 | } mp_expfactor; | |
d03ab969 | 86 | |
d3409d5e | 87 | /*----- Useful constants --------------------------------------------------*/ |
d03ab969 | 88 | |
d3409d5e | 89 | extern mp mp_const[]; |
d03ab969 | 90 | |
d3409d5e | 91 | #define MP_ZERO (&mp_const[0]) |
45c0fd36 MW |
92 | #define MP_ONE (&mp_const[1]) |
93 | #define MP_TWO (&mp_const[2]) | |
d3409d5e | 94 | #define MP_THREE (&mp_const[3]) |
45c0fd36 MW |
95 | #define MP_FOUR (&mp_const[4]) |
96 | #define MP_FIVE (&mp_const[5]) | |
97 | #define MP_TEN (&mp_const[6]) | |
d34decd2 | 98 | #define MP_256 (&mp_const[7]) |
45c0fd36 | 99 | #define MP_MONE (&mp_const[8]) |
d03ab969 | 100 | |
d3409d5e | 101 | #define MP_NEW ((mp *)0) |
d34decd2 | 102 | #define MP_NEWSEC (&mp_const[9]) |
d03ab969 | 103 | |
d34decd2 | 104 | /*----- Trivial macros ----------------------------------------------------*/ |
d03ab969 | 105 | |
d34decd2 | 106 | /* --- @MP_LEN@ --- * |
d03ab969 | 107 | * |
d34decd2 | 108 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 109 | * |
d34decd2 | 110 | * Returns: Length of the integer, in words. |
d03ab969 | 111 | */ |
112 | ||
d34decd2 | 113 | #define MP_LEN(m) ((m)->vl - ((m)->v)) |
d03ab969 | 114 | |
d34decd2 | 115 | /*----- Memory management and reference counting --------------------------*/ |
d3409d5e | 116 | |
d34decd2 | 117 | /* --- @mp_new@ --- * |
d03ab969 | 118 | * |
d34decd2 | 119 | * Arguments: @size_t sz@ = size of vector required |
120 | * @unsigned f@ = flags to set | |
d03ab969 | 121 | * |
d34decd2 | 122 | * Returns: Pointer to a new MP structure. |
d03ab969 | 123 | * |
d34decd2 | 124 | * Use: Allocates a new multiprecision integer. The data space is |
125 | * allocated from either the standard global or secret arena, | |
126 | * depending on the initial flags requested. | |
d03ab969 | 127 | */ |
128 | ||
d34decd2 | 129 | extern mp *mp_new(size_t /*sz*/, unsigned /*f*/); |
d03ab969 | 130 | |
d34decd2 | 131 | /* --- @mp_create@ --- * |
d03ab969 | 132 | * |
d34decd2 | 133 | * Arguments: @size_t sz@ = size of vector required |
d03ab969 | 134 | * |
d34decd2 | 135 | * Returns: Pointer to pristine new MP structure with enough memory |
136 | * bolted onto it. | |
137 | * | |
138 | * Use: Creates a new multiprecision integer with indeterminate | |
139 | * contents. The integer has a single reference. | |
d03ab969 | 140 | */ |
141 | ||
d34decd2 | 142 | extern mp *mp_create(size_t /*sz*/); |
d3409d5e | 143 | |
d34decd2 | 144 | /* --- @mp_createsecure@ --- * |
d03ab969 | 145 | * |
d3409d5e | 146 | * Arguments: @size_t sz@ = size of vector required |
d03ab969 | 147 | * |
d3409d5e | 148 | * Returns: Pointer to pristine new MP structure with enough memory |
149 | * bolted onto it. | |
d03ab969 | 150 | * |
d3409d5e | 151 | * Use: Creates a new multiprecision integer with indeterminate |
d34decd2 | 152 | * contents. The integer has a single reference. The integer's |
153 | * data space is allocated from the secure arena. Its burn flag | |
154 | * is set. | |
d03ab969 | 155 | */ |
156 | ||
d34decd2 | 157 | extern mp *mp_createsecure(size_t /*sz*/); |
d03ab969 | 158 | |
d3409d5e | 159 | /* --- @mp_build@ --- * |
d03ab969 | 160 | * |
d3409d5e | 161 | * Arguments: @mp *m@ = pointer to an MP block to fill in |
162 | * @mpw *v@ = pointer to a word array | |
163 | * @mpw *vl@ = pointer just past end of array | |
d03ab969 | 164 | * |
165 | * Returns: --- | |
166 | * | |
d3409d5e | 167 | * Use: Creates a multiprecision integer representing some smallish |
168 | * number. You must provide storage for the number and dispose | |
169 | * of it when you've finished with it. The number is marked as | |
170 | * constant while it exists. | |
d03ab969 | 171 | */ |
172 | ||
d3409d5e | 173 | extern void mp_build(mp */*m*/, mpw */*v*/, mpw */*vl*/); |
d03ab969 | 174 | |
d3409d5e | 175 | /* --- @mp_destroy@ --- * |
d03ab969 | 176 | * |
d3409d5e | 177 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 178 | * |
179 | * Returns: --- | |
180 | * | |
d3409d5e | 181 | * Use: Destroys a multiprecision integer. The reference count isn't |
182 | * checked. Don't use this function if you don't know what | |
183 | * you're doing: use @mp_drop@ instead. | |
d03ab969 | 184 | */ |
185 | ||
d3409d5e | 186 | extern void mp_destroy(mp */*m*/); |
d03ab969 | 187 | |
d3409d5e | 188 | /* --- @mp_copy@ --- * |
d03ab969 | 189 | * |
d3409d5e | 190 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 191 | * |
d3409d5e | 192 | * Returns: A copy of the given multiprecision integer. |
193 | * | |
194 | * Use: Copies the given integer. In fact you just get another | |
195 | * reference to the same old one again. | |
d03ab969 | 196 | */ |
197 | ||
d3409d5e | 198 | extern mp *mp_copy(mp */*m*/); |
d03ab969 | 199 | |
a6d8eb54 MW |
200 | #define MP_COPY(m) MUFFLE_WARNINGS_EXPR(GCC_WARNING("-Wunused-value"), \ |
201 | ((m)->ref++, (m))) | |
d3409d5e | 202 | |
203 | /* --- @mp_drop@ --- * | |
d03ab969 | 204 | * |
d3409d5e | 205 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 206 | * |
207 | * Returns: --- | |
208 | * | |
d3409d5e | 209 | * Use: Drops a reference to an integer which isn't wanted any more. |
210 | * If there are no more references, the integer is destroyed. | |
d03ab969 | 211 | */ |
212 | ||
d3409d5e | 213 | extern void mp_drop(mp */*m*/); |
d03ab969 | 214 | |
d3409d5e | 215 | #define MP_DROP(m) do { \ |
216 | mp *_mm = (m); \ | |
d34decd2 | 217 | _mm->ref--; \ |
218 | if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \ | |
d3409d5e | 219 | mp_destroy(_mm); \ |
220 | } while (0) | |
45c0fd36 | 221 | |
d3409d5e | 222 | /* --- @mp_split@ --- * |
d03ab969 | 223 | * |
d3409d5e | 224 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 225 | * |
d3409d5e | 226 | * Returns: A reference to the same integer, possibly with a different |
227 | * address. | |
d03ab969 | 228 | * |
d3409d5e | 229 | * Use: Splits off a modifiable version of the integer referred to. |
d03ab969 | 230 | */ |
231 | ||
d3409d5e | 232 | extern mp *mp_split(mp */*m*/); |
233 | ||
234 | #define MP_SPLIT(m) do { \ | |
d34decd2 | 235 | mp *_m = (m); \ |
236 | if ((_m->f & MP_CONST) || _m->ref > 1) { \ | |
237 | size_t _len = MP_LEN(_m); \ | |
238 | mp *_mm = mp_new(_len, _m->f); \ | |
239 | if (!(_m->f & MP_UNDEF)) \ | |
240 | memcpy(_mm->v, _m->v, MPWS(_len)); \ | |
241 | _m->ref--; \ | |
242 | _m = _mm; \ | |
d3409d5e | 243 | } \ |
d34decd2 | 244 | (m) = _m; \ |
d3409d5e | 245 | } while (0) |
d03ab969 | 246 | |
d3409d5e | 247 | /* --- @mp_resize@ --- * |
d03ab969 | 248 | * |
d3409d5e | 249 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
250 | * @size_t sz@ = new size | |
d03ab969 | 251 | * |
d3409d5e | 252 | * Returns: --- |
d03ab969 | 253 | * |
d3409d5e | 254 | * Use: Resizes the vector containing the integer's digits. The new |
255 | * size must be at least as large as the current integer's | |
d34decd2 | 256 | * length. This isn't really intended for client use. |
d03ab969 | 257 | */ |
258 | ||
d3409d5e | 259 | extern void mp_resize(mp */*m*/, size_t /*sz*/); |
260 | ||
261 | #define MP_RESIZE(m, ssz) do { \ | |
262 | mp *_m = (m); \ | |
263 | size_t _sz = (ssz); \ | |
d34decd2 | 264 | mparena *_a = (_m->f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL; \ |
265 | mpw *_v; \ | |
d3409d5e | 266 | size_t _len = MP_LEN(_m); \ |
d34decd2 | 267 | assert(((void)"can't make size less than length", _sz >= _len)); \ |
268 | _v = mpalloc(_a, _sz); \ | |
d9a8ae10 | 269 | if (!(_m->f & MP_UNDEF)) \ |
270 | memcpy(_v, _m->v, MPWS(_len)); \ | |
d3409d5e | 271 | if (_m->f & MP_BURN) \ |
272 | memset(_m->v, 0, MPWS(_m->sz)); \ | |
d34decd2 | 273 | mpfree(_m->a, _m->v); \ |
274 | _m->a = _a; \ | |
d3409d5e | 275 | _m->v = _v; \ |
276 | _m->vl = _v + _len; \ | |
d3409d5e | 277 | } while (0) |
d03ab969 | 278 | |
d3409d5e | 279 | /* --- @mp_ensure@ --- * |
d03ab969 | 280 | * |
d3409d5e | 281 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
282 | * @size_t sz@ = required size | |
d03ab969 | 283 | * |
284 | * Returns: --- | |
285 | * | |
d3409d5e | 286 | * Use: Ensures that the integer has enough space for @sz@ digits. |
287 | * The value is not changed. | |
d03ab969 | 288 | */ |
289 | ||
d3409d5e | 290 | extern void mp_ensure(mp */*m*/, size_t /*sz*/); |
291 | ||
292 | #define MP_ENSURE(m, ssz) do { \ | |
d34decd2 | 293 | mp *_m = (m); \ |
d3409d5e | 294 | size_t _ssz = (ssz); \ |
d34decd2 | 295 | size_t _len = MP_LEN(_m); \ |
296 | if (_ssz >= _len) { \ | |
297 | if (_ssz > _m->sz) \ | |
298 | mp_resize(_m, _ssz); \ | |
299 | if (!(_m->f & MP_UNDEF) && _ssz > _len) \ | |
300 | memset(_m->vl, 0, MPWS(_ssz - _len)); \ | |
301 | _m->vl = _m->v + _ssz; \ | |
302 | } \ | |
d3409d5e | 303 | } while (0) |
d03ab969 | 304 | |
d34decd2 | 305 | /* --- @mp_dest@ --- * |
d03ab969 | 306 | * |
d34decd2 | 307 | * Arguments: @mp *m@ = a suggested destination integer |
308 | * @size_t sz@ = size required for result, in digits | |
309 | * @unsigned f@ = various flags | |
310 | * | |
311 | * Returns: A pointer to an appropriate destination. | |
312 | * | |
313 | * Use: Converts a suggested destination into a real destination with | |
314 | * the required properties. If the real destination is @d@, | |
315 | * then the following properties will hold: | |
316 | * | |
317 | * * @d@ will have exactly one reference. | |
d03ab969 | 318 | * |
d34decd2 | 319 | * * If @m@ is not @MP_NEW@, then the contents of @m@ will not |
320 | * change, unless @f@ has the @MP_UNDEF@ flag set. | |
d03ab969 | 321 | * |
d34decd2 | 322 | * * If @m@ is not @MP_NEW@, then he reference count of @m@ on |
323 | * entry is equal to the sum of the counts of @d@ and @m@ on | |
324 | * exit. | |
325 | * | |
326 | * * The size of @d@ will be at least @sz@. | |
327 | * | |
328 | * * If @f@ has the @MP_BURN@ flag set, then @d@ will be | |
329 | * allocated from @MPARENA_SECURE@. | |
330 | * | |
331 | * Understanding this function is crucial to using Catacomb's | |
332 | * multiprecision integer library effectively. | |
d03ab969 | 333 | */ |
334 | ||
d34decd2 | 335 | extern mp *mp_dest(mp */*m*/, size_t /*sz*/, unsigned /*f*/); |
d03ab969 | 336 | |
d34decd2 | 337 | #define MP_DEST(m, ssz, f) do { \ |
d3409d5e | 338 | mp *_m = (m); \ |
d34decd2 | 339 | size_t _ssz = (ssz); \ |
340 | unsigned _f = (f); \ | |
341 | _m = mp_dest(_m, _ssz, _f); \ | |
d3409d5e | 342 | (m) = _m; \ |
343 | } while (0) | |
344 | ||
345 | /*----- Size manipulation -------------------------------------------------*/ | |
346 | ||
347 | /* --- @mp_shrink@ --- * | |
d03ab969 | 348 | * |
d3409d5e | 349 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 350 | * |
351 | * Returns: --- | |
352 | * | |
d3409d5e | 353 | * Use: Reduces the recorded length of an integer. This doesn't |
354 | * reduce the amount of memory used, although it can improve | |
355 | * performance a bit. To reduce memory, use @mp_minimize@ | |
356 | * instead. This can't change the value of an integer, and is | |
357 | * therefore safe to use even when there are multiple | |
358 | * references. | |
d03ab969 | 359 | */ |
360 | ||
d3409d5e | 361 | extern void mp_shrink(mp */*m*/); |
d03ab969 | 362 | |
d3409d5e | 363 | #define MP_SHRINK(m) do { \ |
364 | mp *_mm = (m); \ | |
365 | MPX_SHRINK(_mm->v, _mm->vl); \ | |
a69a3efd | 366 | if (MP_ZEROP(_mm)) \ |
d3409d5e | 367 | _mm->f &= ~MP_NEG; \ |
368 | } while (0) | |
369 | ||
370 | /* --- @mp_minimize@ --- * | |
d03ab969 | 371 | * |
d3409d5e | 372 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 373 | * |
374 | * Returns: --- | |
375 | * | |
d3409d5e | 376 | * Use: Reduces the amount of memory an integer uses. It's best to |
377 | * do this to numbers which aren't going to change in the | |
378 | * future. | |
d03ab969 | 379 | */ |
380 | ||
d3409d5e | 381 | extern void mp_minimize(mp */*m*/); |
d03ab969 | 382 | |
d3409d5e | 383 | /*----- Bit scanning ------------------------------------------------------*/ |
d03ab969 | 384 | |
d9a8ae10 | 385 | #ifndef CATACOMB_MPSCAN_H |
d3409d5e | 386 | # include "mpscan.h" |
387 | #endif | |
388 | ||
389 | /* --- @mp_scan@ --- * | |
d03ab969 | 390 | * |
d3409d5e | 391 | * Arguments: @mpscan *sc@ = pointer to bitscanner block |
392 | * @const mp *m@ = pointer to a multiprecision integer | |
d03ab969 | 393 | * |
394 | * Returns: --- | |
395 | * | |
d3409d5e | 396 | * Use: Initializes a bitscanner on a multiprecision integer. |
d03ab969 | 397 | */ |
398 | ||
d3409d5e | 399 | extern void mp_scan(mpscan */*sc*/, const mp */*m*/); |
400 | ||
401 | #define MP_SCAN(sc, m) do { \ | |
a790733d | 402 | const mp *_mm = (m); \ |
d3409d5e | 403 | mpscan *_sc = (sc); \ |
404 | MPSCAN_INITX(_sc, _mm->v, _mm->vl); \ | |
405 | } while (0) | |
406 | ||
5fbe3846 | 407 | /* --- @mp_rscan@ --- * |
408 | * | |
409 | * Arguments: @mpscan *sc@ = pointer to bitscanner block | |
410 | * @const mp *m@ = pointer to a multiprecision integer | |
411 | * | |
412 | * Returns: --- | |
413 | * | |
414 | * Use: Initializes a reverse bitscanner on a multiprecision | |
415 | * integer. | |
416 | */ | |
417 | ||
418 | extern void mp_rscan(mpscan */*sc*/, const mp */*m*/); | |
419 | ||
420 | #define MP_RSCAN(sc, m) do { \ | |
421 | const mp *_mm = (m); \ | |
422 | mpscan *_sc = (sc); \ | |
423 | MPSCAN_RINITX(_sc, _mm->v, _mm->vl); \ | |
424 | } while (0) | |
425 | ||
d3409d5e | 426 | /* --- Other bitscanning aliases --- */ |
427 | ||
428 | #define mp_step mpscan_step | |
429 | #define mp_bit mpscan_bit | |
5fbe3846 | 430 | #define mp_rstep mpscan_rstep |
431 | #define mp_rbit mpscan_rbit | |
d3409d5e | 432 | |
433 | #define MP_STEP MPSCAN_STEP | |
434 | #define MP_BIT MPSCAN_BIT | |
5fbe3846 | 435 | #define MP_RSTEP MPSCAN_RSTEP |
436 | #define MP_RBIT MPSCAN_RBIT | |
d3409d5e | 437 | |
438 | /*----- Loading and storing -----------------------------------------------*/ | |
d03ab969 | 439 | |
d3409d5e | 440 | /* --- @mp_octets@ --- * |
d03ab969 | 441 | * |
d3409d5e | 442 | * Arguments: @const mp *m@ = a multiprecision integer |
d03ab969 | 443 | * |
d3409d5e | 444 | * Returns: The number of octets required to represent @m@. |
d03ab969 | 445 | * |
d3409d5e | 446 | * Use: Calculates the external storage required for a multiprecision |
447 | * integer. | |
d03ab969 | 448 | */ |
449 | ||
24e1e862 | 450 | extern size_t mp_octets(const mp */*m*/); |
451 | ||
f09e814a | 452 | /* --- @mp_octets2c@ --- * |
453 | * | |
454 | * Arguments: @const mp *m@ = a multiprecision integer | |
455 | * | |
456 | * Returns: The number of octets required to represent @m@. | |
457 | * | |
458 | * Use: Calculates the external storage required for a multiprecision | |
459 | * integer represented as two's complement. | |
460 | */ | |
461 | ||
462 | extern size_t mp_octets2c(const mp */*m*/); | |
463 | ||
24e1e862 | 464 | /* --- @mp_bits@ --- * |
465 | * | |
466 | * Arguments: @const mp *m@ = a multiprecision integer | |
467 | * | |
468 | * Returns: The number of bits required to represent @m@. | |
469 | * | |
470 | * Use: Calculates the external storage required for a multiprecision | |
471 | * integer. | |
472 | */ | |
473 | ||
474 | extern unsigned long mp_bits(const mp */*m*/); | |
d03ab969 | 475 | |
d3409d5e | 476 | /* --- @mp_loadl@ --- * |
d03ab969 | 477 | * |
d3409d5e | 478 | * Arguments: @mp *d@ = destination |
479 | * @const void *pv@ = pointer to source data | |
480 | * @size_t sz@ = size of the source data | |
d03ab969 | 481 | * |
d3409d5e | 482 | * Returns: Resulting multiprecision number. |
d03ab969 | 483 | * |
d3409d5e | 484 | * Use: Loads a multiprecision number from an array of octets. The |
485 | * first byte in the array is the least significant. More | |
486 | * formally, if the bytes are %$b_0, b_1, \ldots, b_{n-1}$% | |
487 | * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%. | |
d03ab969 | 488 | */ |
489 | ||
d3409d5e | 490 | extern mp *mp_loadl(mp */*d*/, const void */*pv*/, size_t /*sz*/); |
d03ab969 | 491 | |
d3409d5e | 492 | /* --- @mp_storel@ --- * |
493 | * | |
494 | * Arguments: @const mp *m@ = source | |
495 | * @void *pv@ = pointer to output array | |
496 | * @size_t sz@ = size of the output array | |
497 | * | |
498 | * Returns: --- | |
499 | * | |
500 | * Use: Stores a multiprecision number in an array of octets. The | |
501 | * first byte in the array is the least significant. If the | |
502 | * array is too small to represent the number, high-order bits | |
503 | * are truncated; if the array is too large, high order bytes | |
504 | * are filled with zeros. More formally, if the number is | |
505 | * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%, | |
506 | * then the array is %$b_0, b_1, \ldots, b_{n-1}$%. | |
507 | */ | |
d03ab969 | 508 | |
d3409d5e | 509 | extern void mp_storel(const mp */*m*/, void */*pv*/, size_t /*sz*/); |
d03ab969 | 510 | |
d3409d5e | 511 | /* --- @mp_loadb@ --- * |
d03ab969 | 512 | * |
d3409d5e | 513 | * Arguments: @mp *d@ = destination |
514 | * @const void *pv@ = pointer to source data | |
515 | * @size_t sz@ = size of the source data | |
d03ab969 | 516 | * |
d3409d5e | 517 | * Returns: Resulting multiprecision number. |
d03ab969 | 518 | * |
d3409d5e | 519 | * Use: Loads a multiprecision number from an array of octets. The |
520 | * last byte in the array is the least significant. More | |
521 | * formally, if the bytes are %$b_{n-1}, b_{n-2}, \ldots, b_0$% | |
522 | * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%. | |
d03ab969 | 523 | */ |
524 | ||
d3409d5e | 525 | extern mp *mp_loadb(mp */*d*/, const void */*pv*/, size_t /*sz*/); |
d03ab969 | 526 | |
d3409d5e | 527 | /* --- @mp_storeb@ --- * |
d03ab969 | 528 | * |
d3409d5e | 529 | * Arguments: @const mp *m@ = source |
530 | * @void *pv@ = pointer to output array | |
531 | * @size_t sz@ = size of the output array | |
d03ab969 | 532 | * |
533 | * Returns: --- | |
534 | * | |
d3409d5e | 535 | * Use: Stores a multiprecision number in an array of octets. The |
536 | * last byte in the array is the least significant. If the | |
537 | * array is too small to represent the number, high-order bits | |
538 | * are truncated; if the array is too large, high order bytes | |
539 | * are filled with zeros. More formally, if the number is | |
540 | * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%, | |
541 | * then the array is %$b_{n-1}, b_{n-2}, \ldots, b_0$%. | |
d03ab969 | 542 | */ |
543 | ||
d3409d5e | 544 | extern void mp_storeb(const mp */*m*/, void */*pv*/, size_t /*sz*/); |
d03ab969 | 545 | |
f09e814a | 546 | /* --- @mp_loadl2c@ --- * |
d03ab969 | 547 | * |
d3409d5e | 548 | * Arguments: @mp *d@ = destination |
f09e814a | 549 | * @const void *pv@ = pointer to source data |
550 | * @size_t sz@ = size of the source data | |
551 | * | |
552 | * Returns: Resulting multiprecision number. | |
d03ab969 | 553 | * |
f09e814a | 554 | * Use: Loads a multiprecision number from an array of octets as |
555 | * two's complement. The first byte in the array is the least | |
556 | * significant. | |
d3409d5e | 557 | */ |
558 | ||
f09e814a | 559 | extern mp *mp_loadl2c(mp */*d*/, const void */*pv*/, size_t /*sz*/); |
d3409d5e | 560 | |
f09e814a | 561 | /* --- @mp_storel2c@ --- * |
562 | * | |
563 | * Arguments: @const mp *m@ = source | |
564 | * @void *pv@ = pointer to output array | |
565 | * @size_t sz@ = size of the output array | |
566 | * | |
567 | * Returns: --- | |
568 | * | |
569 | * Use: Stores a multiprecision number in an array of octets as two's | |
570 | * complement. The first byte in the array is the least | |
571 | * significant. If the array is too small to represent the | |
572 | * number, high-order bits are truncated; if the array is too | |
573 | * large, high order bytes are sign-extended. | |
574 | */ | |
575 | ||
576 | extern void mp_storel2c(const mp */*m*/, void */*pv*/, size_t /*sz*/); | |
577 | ||
578 | /* --- @mp_loadb2c@ --- * | |
d3409d5e | 579 | * |
580 | * Arguments: @mp *d@ = destination | |
f09e814a | 581 | * @const void *pv@ = pointer to source data |
582 | * @size_t sz@ = size of the source data | |
d03ab969 | 583 | * |
f09e814a | 584 | * Returns: Resulting multiprecision number. |
585 | * | |
586 | * Use: Loads a multiprecision number from an array of octets as | |
587 | * two's complement. The last byte in the array is the least | |
588 | * significant. | |
d03ab969 | 589 | */ |
590 | ||
f09e814a | 591 | extern mp *mp_loadb2c(mp */*d*/, const void */*pv*/, size_t /*sz*/); |
592 | ||
593 | /* --- @mp_storeb2c@ --- * | |
594 | * | |
595 | * Arguments: @const mp *m@ = source | |
596 | * @void *pv@ = pointer to output array | |
597 | * @size_t sz@ = size of the output array | |
598 | * | |
599 | * Returns: --- | |
600 | * | |
601 | * Use: Stores a multiprecision number in an array of octets, as | |
602 | * two's complement. The last byte in the array is the least | |
603 | * significant. If the array is too small to represent the | |
604 | * number, high-order bits are truncated; if the array is too | |
605 | * large, high order bytes are sign-extended. | |
606 | */ | |
607 | ||
608 | extern void mp_storeb2c(const mp */*m*/, void */*pv*/, size_t /*sz*/); | |
609 | ||
397041a9 | 610 | /*----- Bit operations ----------------------------------------------------*/ |
d03ab969 | 611 | |
397041a9 | 612 | /* --- @mp_not@ --- * |
d03ab969 | 613 | * |
d3409d5e | 614 | * Arguments: @mp *d@ = destination |
d9a8ae10 | 615 | * @mp *a@ = source |
d03ab969 | 616 | * |
397041a9 | 617 | * Returns: The bitwise complement of the source. |
45c0fd36 | 618 | */ |
d3409d5e | 619 | |
397041a9 | 620 | extern mp *mp_not(mp */*d*/, mp */*a*/); |
d3409d5e | 621 | |
397041a9 | 622 | /* --- @mp_bitop@ --- * |
d3409d5e | 623 | * |
624 | * Arguments: @mp *d@ = destination | |
397041a9 | 625 | * @mp *a, *b@ = sources |
d03ab969 | 626 | * |
397041a9 | 627 | * Returns: The result of the given bitwise operation. These functions |
628 | * don't handle negative numbers at all sensibly. For that, use | |
629 | * the @...2c@ variants. The functions are named after the | |
630 | * truth tables they generate: | |
631 | * | |
632 | * a: 0011 | |
633 | * b: 0101 | |
634 | * @mpx_bitXXXX@ | |
d03ab969 | 635 | */ |
636 | ||
397041a9 | 637 | #define MP_BITDECL(string) \ |
638 | extern mp *mp_bit##string(mp */*d*/, mp */*a*/, mp */*b*/); | |
639 | MPX_DOBIN(MP_BITDECL) | |
f09e814a | 640 | |
397041a9 | 641 | /* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- * |
f09e814a | 642 | * |
397041a9 | 643 | * Synonyms for the commonly-used functions. |
f09e814a | 644 | */ |
645 | ||
45c0fd36 MW |
646 | #define mp_and mp_bit0001 |
647 | #define mp_or mp_bit0111 | |
397041a9 | 648 | #define mp_nand mp_bit1110 |
45c0fd36 MW |
649 | #define mp_nor mp_bit1000 |
650 | #define mp_xor mp_bit0110 | |
f09e814a | 651 | |
397041a9 | 652 | /* --- @mp_testbit@ --- * |
f09e814a | 653 | * |
654 | * Arguments: @mp *x@ = a large integer | |
09d00c6b | 655 | * @unsigned long n@ = which bit to test |
f09e814a | 656 | * |
397041a9 | 657 | * Returns: Nonzero if the bit is set, zero if not. |
d3409d5e | 658 | */ |
659 | ||
397041a9 | 660 | extern int mp_testbit(mp */*x*/, unsigned long /*n*/); |
d3409d5e | 661 | |
09d00c6b | 662 | /* --- @mp_setbit@, @mp_clearbit@ --- * |
663 | * | |
664 | * Arguments: @mp *d@ = a destination | |
665 | * @mp *x@ = a large integer | |
666 | * @unsigned long n@ = which bit to modify | |
667 | * | |
668 | * Returns: The argument @x@, with the appropriate bit set or cleared. | |
669 | */ | |
670 | ||
671 | extern mp *mp_setbit(mp */*d*/, mp */*x*/, unsigned long /*n*/); | |
672 | extern mp *mp_clearbit(mp */*d*/, mp */*x*/, unsigned long /*n*/); | |
673 | ||
81578196 | 674 | /* --- @mp_lsl@, @mp_lslc@, @mp_lsr@ --- * |
0f32e0f8 | 675 | * |
676 | * Arguments: @mp *d@ = destination | |
397041a9 | 677 | * @mp *a@ = source |
678 | * @size_t n@ = number of bits to move | |
f09e814a | 679 | * |
397041a9 | 680 | * Returns: Result, @a@ shifted left or right by @n@. |
81578196 | 681 | * |
682 | * Use: Bitwise shift operators. @mp_lslc@ fills the bits introduced | |
683 | * on the right with ones instead of zeroes: it's used | |
684 | * internally by @mp_lsl2c@, though it may be useful on its | |
685 | * own. | |
f09e814a | 686 | */ |
687 | ||
397041a9 | 688 | extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/); |
81578196 | 689 | extern mp *mp_lslc(mp */*d*/, mp */*a*/, size_t /*n*/); |
397041a9 | 690 | extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/); |
f09e814a | 691 | |
397041a9 | 692 | /* --- @mp_not2c@ --- * |
f09e814a | 693 | * |
694 | * Arguments: @mp *d@ = destination | |
695 | * @mp *a@ = source | |
696 | * | |
397041a9 | 697 | * Returns: The sign-extended complement of the argument. |
698 | */ | |
f09e814a | 699 | |
397041a9 | 700 | extern mp *mp_not2c(mp */*d*/, mp */*a*/); |
0f32e0f8 | 701 | |
f09e814a | 702 | /* --- @mp_bitop2c@ --- * |
703 | * | |
704 | * Arguments: @mp *d@ = destination | |
705 | * @mp *a, *b@ = sources | |
706 | * | |
707 | * Returns: The result of the given bitwise operation. Negative numbers | |
708 | * are treated as two's complement, sign-extended infinitely to | |
709 | * the left. The functions are named after the truth tables | |
710 | * they generate: | |
711 | * | |
712 | * a: 0011 | |
713 | * b: 0101 | |
714 | * @mpx_bitXXXX@ | |
715 | */ | |
716 | ||
717 | #define MP_BIT2CDECL(string) \ | |
718 | extern mp *mp_bit##string##2c(mp */*d*/, mp */*a*/, mp */*b*/); | |
719 | MPX_DOBIN(MP_BIT2CDECL) | |
720 | ||
721 | /* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- * | |
722 | * | |
723 | * Synonyms for the commonly-used functions. | |
724 | */ | |
725 | ||
726 | #define mp_and2c mp_bit00012c | |
45c0fd36 | 727 | #define mp_or2c mp_bit01112c |
f09e814a | 728 | #define mp_nand2c mp_bit11102c |
729 | #define mp_nor2c mp_bit10002c | |
730 | #define mp_xor2c mp_bit01102c | |
731 | ||
397041a9 | 732 | /* --- @mp_lsl2c@, @mp_lsr2c@ --- * |
f09e814a | 733 | * |
734 | * Arguments: @mp *d@ = destination | |
735 | * @mp *a@ = source | |
397041a9 | 736 | * @size_t n@ = number of bits to move |
f09e814a | 737 | * |
397041a9 | 738 | * Returns: Result, @a@ shifted left or right by @n@. Handles the |
739 | * pretence of sign-extension for negative numbers. | |
f09e814a | 740 | */ |
741 | ||
397041a9 | 742 | extern mp *mp_lsl2c(mp */*d*/, mp */*a*/, size_t /*n*/); |
743 | extern mp *mp_lsr2c(mp */*d*/, mp */*a*/, size_t /*n*/); | |
744 | ||
745 | /* --- @mp_testbit2c@ --- * | |
746 | * | |
747 | * Arguments: @mp *x@ = a large integer | |
748 | * @unsigned long n@ = which bit to test | |
749 | * | |
750 | * Returns: Nonzero if the bit is set, zero if not. Fakes up two's | |
751 | * complement representation. | |
752 | */ | |
753 | ||
754 | extern int mp_testbit2c(mp */*x*/, unsigned long /*n*/); | |
755 | ||
756 | /* --- @mp_setbit2c@, @mp_clearbit2c@ --- * | |
757 | * | |
758 | * Arguments: @mp *d@ = a destination | |
759 | * @mp *x@ = a large integer | |
760 | * @unsigned long n@ = which bit to modify | |
761 | * | |
762 | * Returns: The argument @x@, with the appropriate bit set or cleared. | |
763 | * Fakes up two's complement representation. | |
764 | */ | |
765 | ||
766 | extern mp *mp_setbit2c(mp */*d*/, mp */*x*/, unsigned long /*n*/); | |
767 | extern mp *mp_clearbit2c(mp */*d*/, mp */*x*/, unsigned long /*n*/); | |
768 | ||
769 | /*----- Comparisons -------------------------------------------------------*/ | |
770 | ||
771 | /* --- @mp_eq@ --- * | |
772 | * | |
773 | * Arguments: @const mp *a, *b@ = two numbers | |
774 | * | |
775 | * Returns: Nonzero if the numbers are equal. | |
776 | */ | |
777 | ||
778 | extern int mp_eq(const mp */*a*/, const mp */*b*/); | |
779 | ||
780 | #define MP_EQ(a, b) \ | |
781 | ((((a)->f ^ (b)->f) & MP_NEG) == 0 && \ | |
782 | mpx_ueq((a)->v, (a)->vl, (b)->v, (b)->vl)) | |
783 | ||
784 | /* --- @mp_cmp@ --- * | |
785 | * | |
786 | * Arguments: @const mp *a, *b@ = two numbers | |
787 | * | |
788 | * Returns: Less than, equal to or greater than zero, according to | |
789 | * whether @a@ is less than, equal to or greater than @b@. | |
790 | */ | |
791 | ||
792 | extern int mp_cmp(const mp */*a*/, const mp */*b*/); | |
793 | ||
794 | #define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0) | |
795 | ||
3cd24abb | 796 | /* --- Other handy macros --- */ |
797 | ||
a69a3efd | 798 | #define MP_NEGP(x) ((x)->f & MP_NEG) |
799 | #define MP_ZEROP(x) (!MP_LEN(x)) | |
800 | #define MP_POSP(x) (!MP_NEGP(x) && !MP_ZEROP(x)) | |
801 | #define MP_ODDP(x) (!MP_ZEROP(x) && ((x)->v[0] & 1u)) | |
802 | #define MP_EVENP(x) (!MP_ODDP(x)) | |
3cd24abb | 803 | |
397041a9 | 804 | /*----- Arithmetic operations ---------------------------------------------*/ |
805 | ||
806 | /* --- @mp_neg@ --- * | |
807 | * | |
808 | * Arguments: @mp *d@ = destination | |
809 | * @mp *a@ = argument | |
810 | * | |
811 | * Returns: The negation of the argument. | |
812 | * | |
813 | * Use: Negates its argument. | |
814 | */ | |
815 | ||
816 | extern mp *mp_neg(mp */*d*/, mp */*a*/); | |
f09e814a | 817 | |
d3409d5e | 818 | /* --- @mp_add@ --- * |
d03ab969 | 819 | * |
d3409d5e | 820 | * Arguments: @mp *d@ = destination |
d9a8ae10 | 821 | * @mp *a, *b@ = sources |
d3409d5e | 822 | * |
823 | * Returns: Result, @a@ added to @b@. | |
d03ab969 | 824 | */ |
825 | ||
d9a8ae10 | 826 | extern mp *mp_add(mp */*d*/, mp */*a*/, mp */*b*/); |
d03ab969 | 827 | |
d3409d5e | 828 | /* --- @mp_sub@ --- * |
829 | * | |
830 | * Arguments: @mp *d@ = destination | |
d9a8ae10 | 831 | * @mp *a, *b@ = sources |
d3409d5e | 832 | * |
833 | * Returns: Result, @b@ subtracted from @a@. | |
834 | */ | |
d03ab969 | 835 | |
d9a8ae10 | 836 | extern mp *mp_sub(mp */*d*/, mp */*a*/, mp */*b*/); |
d3409d5e | 837 | |
838 | /* --- @mp_mul@ --- * | |
d03ab969 | 839 | * |
d3409d5e | 840 | * Arguments: @mp *d@ = destination |
d9a8ae10 | 841 | * @mp *a, *b@ = sources |
d03ab969 | 842 | * |
d3409d5e | 843 | * Returns: Result, @a@ multiplied by @b@. |
844 | */ | |
845 | ||
d9a8ae10 | 846 | extern mp *mp_mul(mp */*d*/, mp */*a*/, mp */*b*/); |
d3409d5e | 847 | |
848 | /* --- @mp_sqr@ --- * | |
849 | * | |
850 | * Arguments: @mp *d@ = destination | |
d9a8ae10 | 851 | * @mp *a@ = source |
d3409d5e | 852 | * |
853 | * Returns: Result, @a@ squared. | |
854 | */ | |
855 | ||
d9a8ae10 | 856 | extern mp *mp_sqr(mp */*d*/, mp */*a*/); |
d3409d5e | 857 | |
858 | /* --- @mp_div@ --- * | |
d03ab969 | 859 | * |
d3409d5e | 860 | * Arguments: @mp **qq, **rr@ = destination, quotient and remainder |
d9a8ae10 | 861 | * @mp *a, *b@ = sources |
d3409d5e | 862 | * |
863 | * Use: Calculates the quotient and remainder when @a@ is divided by | |
864 | * @b@. | |
d03ab969 | 865 | */ |
866 | ||
d9a8ae10 | 867 | extern void mp_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/); |
d3409d5e | 868 | |
f4535c64 | 869 | /* --- @mp_exp@ --- * |
870 | * | |
871 | * Arguments: @mp *d@ = fake destination | |
872 | * @mp *a@ = base | |
873 | * @mp *e@ = exponent | |
874 | * | |
875 | * Returns: Result, %$a^e$%. | |
876 | */ | |
877 | ||
878 | extern mp *mp_exp(mp */*d*/, mp */*a*/, mp */*e*/); | |
879 | ||
22a073c0 | 880 | /* --- @mp_odd@ --- * |
881 | * | |
882 | * Arguments: @mp *d@ = pointer to destination integer | |
883 | * @mp *m@ = pointer to source integer | |
884 | * @size_t *s@ = where to store the power of 2 | |
885 | * | |
886 | * Returns: An odd integer integer %$t$% such that %$m = 2^s t$%. | |
887 | * | |
888 | * Use: Computes a power of two and an odd integer which, when | |
889 | * multiplied, give a specified result. This sort of thing is | |
890 | * useful in number theory quite often. | |
891 | */ | |
892 | ||
893 | extern mp *mp_odd(mp */*d*/, mp */*m*/, size_t */*s*/); | |
894 | ||
0c4f06c0 MW |
895 | /* --- @mp_leastcongruent@ --- * |
896 | * | |
897 | * Arguments: @mp *d@ = pointer to destination | |
898 | * @mp *b@ = lower bound | |
899 | * @mp *r@ = representative | |
900 | * @mp *m@ = modulus | |
901 | * | |
902 | * Returns: The smallest integer %$x \equiv r \pmod{m}$% such that | |
903 | * %$x \ge b$%. | |
904 | */ | |
905 | ||
906 | extern mp *mp_leastcongruent(mp */*d*/, mp */*b*/, mp */*r*/, mp */*m*/); | |
907 | ||
d3409d5e | 908 | /*----- More advanced algorithms ------------------------------------------*/ |
d03ab969 | 909 | |
22a073c0 | 910 | /* --- @mp_sqrt@ --- * |
911 | * | |
912 | * Arguments: @mp *d@ = pointer to destination integer | |
913 | * @mp *a@ = (nonnegative) integer to take square root of | |
914 | * | |
915 | * Returns: The largest integer %$x$% such that %$x^2 \le a$%. | |
916 | * | |
917 | * Use: Computes integer square roots. | |
918 | * | |
919 | * The current implementation isn't very good: it uses the | |
920 | * Newton-Raphson method to find an approximation to %$a$%. If | |
921 | * there's any demand for a better version, I'll write one. | |
922 | */ | |
923 | ||
924 | extern mp *mp_sqrt(mp */*d*/, mp */*a*/); | |
925 | ||
d3409d5e | 926 | /* --- @mp_gcd@ --- * |
d03ab969 | 927 | * |
d3409d5e | 928 | * Arguments: @mp **gcd, **xx, **yy@ = where to write the results |
929 | * @mp *a, *b@ = sources (must be nonzero) | |
d03ab969 | 930 | * |
931 | * Returns: --- | |
932 | * | |
d3409d5e | 933 | * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that |
934 | * @ax + by = gcd(a, b)@. This is useful for computing modular | |
d9a8ae10 | 935 | * inverses. Neither @a@ nor @b@ may be zero. |
d03ab969 | 936 | */ |
937 | ||
d3409d5e | 938 | extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/, |
939 | mp */*a*/, mp */*b*/); | |
940 | ||
b817bfc6 | 941 | /* -- @mp_modinv@ --- * |
942 | * | |
943 | * Arguments: @mp *d@ = destination | |
944 | * @mp *x@ = argument | |
945 | * @mp *p@ = modulus | |
946 | * | |
947 | * Returns: The inverse %$x^{-1} \bmod p$%. | |
948 | * | |
949 | * Use: Computes a modular inverse. An assertion fails if %$p$% | |
950 | * has no inverse. | |
951 | */ | |
952 | ||
953 | extern mp *mp_modinv(mp */*d*/, mp */*x*/, mp */*p*/); | |
954 | ||
5b00a0ea | 955 | /* --- @mp_jacobi@ --- * |
956 | * | |
6791ed17 MW |
957 | * Arguments: @mp *a@ = an integer |
958 | * @mp *n@ = another integer | |
5b00a0ea | 959 | * |
960 | * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%. | |
961 | * | |
6791ed17 MW |
962 | * Use: Computes the Kronecker symbol %$\jacobi{a}{n}$%. If @n@ is |
963 | * prime, this is the Legendre symbol and is equal to 1 if and | |
964 | * only if @a@ is a quadratic residue mod @n@. The result is | |
965 | * zero if and only if @a@ and @n@ have a common factor greater | |
966 | * than one. | |
967 | * | |
968 | * If @n@ is composite, then this computes the Kronecker symbol | |
969 | * | |
970 | * %$\jacobi{a}{n}=\jacobi{a}{u}\prod_i\jacobi{a}{p_i}^{e_i}$% | |
971 | * | |
972 | * where %$n = u p_0^{e_0} \ldots p_{n-1}^{e_{n-1}}$% is the | |
973 | * prime factorization of %$n$%. The missing bits are: | |
974 | * | |
975 | * * %$\jacobi{a}{1} = 1$%; | |
976 | * * %$\jacobi{a}{-1} = 1$% if @a@ is negative, or 1 if | |
977 | * positive; | |
978 | * * %$\jacobi{a}{0} = 0$%; | |
075af359 | 979 | * * %$\jacobi{a}{2}$ is 0 if @a@ is even, 1 if @a@ is |
6791ed17 MW |
980 | * congruent to 1 or 7 (mod 8), or %$-1$% otherwise. |
981 | * | |
982 | * If %$n$% is positive and odd, then this is the Jacobi | |
27b1fbee | 983 | * symbol. (The Kronecker symbol is a consistent domain |
6791ed17 MW |
984 | * extension; the Jacobi symbol was implemented first, and the |
985 | * name stuck.) | |
5b00a0ea | 986 | */ |
987 | ||
22a073c0 | 988 | extern int mp_jacobi(mp */*a*/, mp */*n*/); |
989 | ||
990 | /* --- @mp_modsqrt@ --- * | |
991 | * | |
992 | * Arguments: @mp *d@ = destination integer | |
993 | * @mp *a@ = source integer | |
994 | * @mp *p@ = modulus (must be prime) | |
995 | * | |
996 | * Returns: If %$a$% is a quadratic residue, a square root of %$a$%; else | |
997 | * a null pointer. | |
998 | * | |
999 | * Use: Returns an integer %$x$% such that %$x^2 \equiv a \pmod{p}$%, | |
1000 | * if one exists; else a null pointer. This function will not | |
1001 | * work if %$p$% is composite: you must factor the modulus, take | |
1002 | * a square root mod each factor, and recombine the results | |
1003 | * using the Chinese Remainder Theorem. | |
222c8a43 MW |
1004 | * |
1005 | * We guarantee that the square root returned is the smallest | |
1006 | * one (i.e., the `positive' square root). | |
22a073c0 | 1007 | */ |
1008 | ||
1009 | extern mp *mp_modsqrt(mp */*d*/, mp */*a*/, mp */*p*/); | |
5b00a0ea | 1010 | |
ffec4880 MW |
1011 | /* --- @mp_modexp@ --- * |
1012 | * | |
1013 | * Arguments: @mp *d@ = fake destination | |
1014 | * @mp *x@ = base of exponentiation | |
1015 | * @mp *e@ = exponent | |
1016 | * @mp *n@ = modulus (must be positive) | |
1017 | * | |
1018 | * Returns: The value %$x^e \bmod n$%. | |
1019 | */ | |
1020 | ||
1021 | extern mp *mp_modexp(mp */*d*/, mp */*x*/, mp */*e*/, mp */*n*/); | |
1022 | ||
d3409d5e | 1023 | /*----- Test harness support ----------------------------------------------*/ |
1024 | ||
1025 | #include <mLib/testrig.h> | |
1026 | ||
d9a8ae10 | 1027 | #ifndef CATACOMB_MPTEXT_H |
d3409d5e | 1028 | # include "mptext.h" |
1029 | #endif | |
1030 | ||
1031 | extern const test_type type_mp; | |
d03ab969 | 1032 | |
1033 | /*----- That's all, folks -------------------------------------------------*/ | |
1034 | ||
1035 | #ifdef __cplusplus | |
1036 | } | |
1037 | #endif | |
1038 | ||
1039 | #endif |