5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 1997 - 2001 Pekka Riikonen
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
21 /****h* silcmath/SilcMPAPI
25 * SILC MP Library Interface. This interface defines the arbitrary
26 * precision arithmetic routines for SILC. Currently the actual routines
27 * are implemented separately, usually by some other MP library. The
28 * interface is generic but is mainly intended for crypto usage. This
29 * interface is used by SILC routines that needs big numbers, such as
30 * RSA implementation, Diffie-Hellman implementation etc.
38 #include "mp_gmp.h" /* SILC_MP_GMP */
40 #include "mp_mpi.h" /* SILC_MP_NSS_MPI */
43 /****d* silcmath/SilcMPAPI/SilcMPInt
47 * typedef SILC_MP_INT SilcMPInt;
51 * The SILC MP Integer definition. This is the actual MP integer.
52 * The type is defined as SILC_MP_INT as it is implementation specific
53 * and is unknown to the application.
57 typedef SILC_MP_INT SilcMPInt;
60 /****f* silcmath/SilcMPAPI/silc_mp_init
64 * void silc_mp_init(SilcMPInt mp);
68 * Initializes the SilcMPInt *that is the actual MP Integer.
69 * This must be called before any of the silc_mp_ routines can be
70 * used. The integer is uninitialized with the silc_mp_uninit function.
73 void silc_mp_init(SilcMPInt *mp);
75 /****f* silcmath/SilcMPAPI/silc_mp_uninit
79 * void silc_mp_uninit(SilcMPInt *mp);
83 * Uninitializes the MP Integer.
86 void silc_mp_uninit(SilcMPInt *mp);
88 /****f* silcmath/SilcMPAPI/silc_mp_size
92 * size_t silc_mp_size(SilcMPInt *mp);
96 * Return the precision size of the integer `mp'.
99 size_t silc_mp_size(SilcMPInt *mp);
101 /****f* silcmath/SilcMPAPI/silc_mp_sizeinbase
105 * size_t silc_mp_sizeinbase(SilcMPInt *mp, int base);
109 * Return the size of the integer in base `base'. Note that this size
110 * is probably only an approximation. However, it is guaranteed that
111 * the returned size is always at least the size of the integer, however,
115 size_t silc_mp_sizeinbase(SilcMPInt *mp, int base);
117 /****f* silcmath/SilcMPAPI/silc_mp_set
121 * void silc_mp_set(SilcMPInt *dst, SilcMPInt *src);
125 * Set `dst' integer from `src' integer. The `dst' must already be
129 void silc_mp_set(SilcMPInt *dst, SilcMPInt *src);
131 /****f* silcmath/SilcMPAPI/silc_mp_set_ui
135 * void silc_mp_set_ui(SilcMPInt *dst, uint32 ui);
139 * Set `dst' integer from unsigned word `ui'. The `dst' must already be
143 void silc_mp_set_ui(SilcMPInt *dst, uint32 ui);
145 /****f* silcmath/SilcMPAPI/silc_mp_set_si
149 * void silc_mp_set_si(SilcMPInt *dst, int32 si);
153 * Set `dst' integer from single word `si'. The `dst' must
154 * already be initialized.
157 void silc_mp_set_si(SilcMPInt *dst, int32 si);
159 /****f* silcmath/SilcMPAPI/silc_mp_set_str
163 * void silc_mp_set_str(SilcMPInt *dst, const char *str, int base);
167 * Set `dst' integer from string `str' of base `base'. The `dst' must
168 * already be initialized.
171 void silc_mp_set_str(SilcMPInt *dst, const char *str, int base);
173 /****f* silcmath/SilcMPAPI/silc_mp_get_ui
177 * uint32 silc_mp_get_ui(SilcMPInt *mp);
181 * Returns the least significant unsigned word from `mp'.
184 uint32 silc_mp_get_ui(SilcMPInt *mp);
186 /****f* silcmath/SilcMPAPI/silc_mp_get_str
190 * void silc_mp_get_str(char *str, SilcMPInt *mp, int base);
194 * Converts integer `mp' into a string of base `base'. The `str'
195 * must already have space allocated. The function returns the same
196 * as `str' or NULL on error.
199 char *silc_mp_get_str(char *str, SilcMPInt *mp, int base);
201 /****f* silcmath/SilcMPAPI/silc_mp_add
205 * void silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
209 * Add two integers `mp1' and `mp2' and save the result to `dst'.
212 void silc_mp_add(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
214 /****f* silcmath/SilcMPAPI/silc_mp_add_ui
218 * void silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
222 * Add two integers `mp1' and unsigned word `ui' and save the result
226 void silc_mp_add_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
228 /****f* silcmath/SilcMPAPI/silc_mp_sub
232 * void silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
236 * Subtract two integers `mp1' and `mp2' and save the result to `dst'.
239 void silc_mp_sub(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
241 /****f* silcmath/SilcMPAPI/silc_mp_sub_ui
245 * void silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
249 * Subtract integers `mp1' and unsigned word `ui' and save the result
253 void silc_mp_sub_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
255 /****f* silcmath/SilcMPAPI/silc_mp_mul
259 * void silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
263 * Multiply two integers `mp1' and `mp2' and save the result to `dst'.
266 void silc_mp_mul(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
268 /****f* silcmath/SilcMPAPI/silc_mp_mul_ui
272 * void silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
276 * Multiply integer `mp1' and unsigned word `ui' and save the result
280 void silc_mp_mul_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
282 /****f* silcmath/SilcMPAPI/silc_mp_mul_2exp
286 * void silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, uint32 exp);
290 * Multiply integers `mp1' with 2 ** `exp' and save the result to
291 * `dst'. This is equivalent to dst = mp1 * (2 ^ exp).
294 void silc_mp_mul_2exp(SilcMPInt *dst, SilcMPInt *mp1, uint32 exp);
296 /****f* silcmath/SilcMPAPI/silc_mp_sqrt
300 * void silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src);
304 * Compute square root of floor(sqrt(src)) and save the result to `dst'.
307 void silc_mp_sqrt(SilcMPInt *dst, SilcMPInt *src);
309 /****f* silcmath/SilcMPAPI/silc_mp_div
313 * void silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
317 * Divide the `mp1' and `mp2' and save the result to the `dst'. This
318 * is equivalent to dst = mp1 / mp2;
321 void silc_mp_div(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
323 /****f* silcmath/SilcMPAPI/silc_mp_div_ui
327 * void silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
331 * Divide the `mp1' and unsigned word `ui' and save the result to the
332 * `dst'. This is equivalent to dst = mp1 / ui;
335 void silc_mp_div_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
337 /****f* silcmath/SilcMPAPI/silc_mp_div_qr
341 * void silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
346 * Divide the `mp1' and `mp2' and save the quotient to the `q' and
347 * the remainder to the `r'. This is equivalent to the q = mp1 / mp2,
348 * r = mp1 mod mp2 (or mp1 = mp2 * q + r). If the `q' or `r' is NULL
349 * then the operation is omitted.
352 void silc_mp_div_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
355 /****f* silcmath/SilcMPAPI/silc_mp_div_2exp
359 * void silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
363 * Divide the `mp1' with 2 ** `exp' and save the result to `dst'.
364 * This is equivalent to dst = mp1 / (2 ^ exp).
367 void silc_mp_div_2exp(SilcMPInt *dst, SilcMPInt *mp1, uint32 exp);
369 /****f* silcmath/SilcMPAPI/silc_mp_div_2exp_qr
373 * void silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
378 * Divide the `mp1' with 2 ** `exp' and save the quotient to `q' and
379 * the remainder to `r'. This is equivalent to q = mp1 / (2 ^ exp),
380 * r = mp1 mod (2 ^ exp). If the `q' or `r' is NULL then the operation
384 void silc_mp_div_2exp_qr(SilcMPInt *q, SilcMPInt *r, SilcMPInt *mp1,
387 /****f* silcmath/SilcMPAPI/silc_mp_mod
391 * void silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
395 * Mathematical MOD function. Produces the remainder of `mp1' and `mp2'
396 * and saves the result to `dst'. This is equivalent to dst = mp1 mod mp2.
397 * The same result can also be get with silc_mp_div_qr as that function
398 * returns the remainder as well.
401 void silc_mp_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
403 /****f* silcmath/SilcMPAPI/silc_mp_mod_ui
407 * void silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
411 * Mathematical MOD function. Produces the remainder of `mp1' and
412 * unsigned word `ui' and saves the result to `dst'. This is equivalent
413 * to dst = mp1 mod ui.
416 void silc_mp_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
418 /****f* silcmath/SilcMPAPI/silc_mp_mod_2exp
422 * void silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
426 * Computes the remainder of `mp1' with 2 ** `exp' and saves the
427 * result to `dst'. This is equivalent to dst = mp1 mod (2 ^ exp).
428 * The same result can also be get with silc_mp_div_2exp_qr as that
429 * function returns the remainder as well.
432 void silc_mp_mod_2exp(SilcMPInt *dst, SilcMPInt *mp1, uint32 ui);
434 /****f* silcmath/SilcMPAPI/silc_mp_pow
438 * void silc_mp_pow(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp);
442 * Compute `mp1' ** `exp' and save the result to `dst'. This is
443 * equivalent to dst = mp1 ^ exp.
446 void silc_mp_pow(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp);
448 /****f* silcmath/SilcMPAPI/silc_mp_pow_ui
452 * void silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 exp);
456 * Compute `mp1' ** `exp' and save the result to `dst'. This is
457 * equivalent to dst = mp1 ^ exp.
460 void silc_mp_pow_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 exp);
462 /****f* silcmath/SilcMPAPI/silc_mp_pow_mod
466 * void silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp,
471 * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'.
472 * This is equivalent to dst = (mp1 ^ exp) mod mod.
475 void silc_mp_pow_mod(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *exp,
478 /****f* silcmath/SilcMPAPI/silc_mp_pow_mod_ui
482 * void silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 exp,
487 * Compute (`mp1' ** `exp') mod `mod' and save the result to `dst'.
488 * This is equivalent to dst = (mp1 ^ exp) mod mod.
491 void silc_mp_pow_mod_ui(SilcMPInt *dst, SilcMPInt *mp1, uint32 exp,
494 /****f* silcmath/SilcMPAPI/silc_mp_modinv
498 * void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n);
502 * Find multiplicative inverse using Euclid's extended algorithm.
503 * Computes inverse such that a * inv mod n = 1, where 0 < a < n.
504 * Algorithm goes like this:
510 * g(i+1) = g(i-1) - y * g(i) = g(i)-1 mod g(i)
511 * v(i+1) = v(i-1) - y * v(i)
513 * do until g(i) = 0, then inverse = v(i-1). If inverse is negative then n,
514 * is added to inverse making it positive again. (Sometimes the algorithm
515 * has a variable u defined too and it behaves just like v, except that
516 * initalize values are swapped (i.e. u(0) = 1, u(1) = 0). However, u is
517 * not needed by the algorithm so it does not have to be included.)
520 void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n);
522 /****f* silcmath/SilcMPAPI/silc_mp_gcd
526 * void silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
530 * Calculate the greatest common divisor of the integers `mp1' and `mp2'
531 * and save the result to `dst'.
534 void silc_mp_gcd(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
536 /****f* silcmath/SilcMPAPI/silc_mp_gcdext
540 * void silc_mp_gcdext(SilcMPInt *g, SilcMPInt *s, SilcMPInt *t,
541 * SilcMPInt *mp1, SilcMPInt *mp2);
545 * Calculate the extended greatest common divisor `g', `s' and `t' such
546 * that g = mp1 * s + mp2 * + t.
549 void silc_mp_gcdext(SilcMPInt *g, SilcMPInt *s, SilcMPInt *t, SilcMPInt *mp1,
552 /****f* silcmath/SilcMPAPI/silc_mp_cmp
556 * int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2);
560 * Compare `mp1' and `mp2'. Returns posivite, zero, or negative
561 * if `mp1' > `mp2', `mp1' == `mp2', or `mp1' < `mp2', respectively.
564 int silc_mp_cmp(SilcMPInt *mp1, SilcMPInt *mp2);
566 /****f* silcmath/SilcMPAPI/silc_mp_cmp_si
570 * int silc_mp_cmp_si(SilcMPInt *mp1, int32 si);
574 * Compare `mp1' and single word `si'. Returns posivite, zero, or negative
575 * if `mp1' > `si', `mp1' == `si', or `mp1' < `si', respectively.
578 int silc_mp_cmp_si(SilcMPInt *mp1, int32 si);
580 /****f* silcmath/SilcMPAPI/silc_mp_cmp_ui
584 * int silc_mp_cmp_ui(SilcMPInt *mp1, uint32 ui);
588 * Compare `mp1' and unsigned word `ui'. Returns posivite, zero, or
589 * negative if `mp1' > `ui', `mp1' == `ui', or `mp1' < `ui',
593 int silc_mp_cmp_ui(SilcMPInt *mp1, uint32 ui);
595 /****f* silcmath/SilcMPAPI/silc_mp_mp2bin
599 * unsigned char *silc_mp_mp2bin(SilcMPInt *val, uint32 len,
604 * Encodes MP integer into binary data. Returns allocated data that
605 * must be free'd by the caller. If `len' is provided the destination
606 * buffer is allocated that large. If zero then the size is approximated.
609 unsigned char *silc_mp_mp2bin(SilcMPInt *val, uint32 len,
612 /****f* silcmath/SilcMPAPI/silc_mp_mp2bin_noalloc
616 * void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst,
621 * Same as silc_mp_mp2bin but does not allocate any memory. The
622 * encoded data is returned into `dst' and it's length to the `ret_len'.
625 void silc_mp_mp2bin_noalloc(SilcMPInt *val, unsigned char *dst,
628 /****f* silcmath/SilcMPAPI/silc_mp_bin2mp
632 * void silc_mp_bin2mp(unsigned char *data, uint32 len,
637 * Decodes binary data into MP integer. The integer sent as argument
638 * must be initialized.
641 void silc_mp_bin2mp(unsigned char *data, uint32 len, SilcMPInt *ret);
643 /****f* silcmath/SilcMPAPI/silc_mp_abs
647 * void silc_mp_abs(SilcMPInt *src, SilcMPInt *dst);
651 * Assign the absolute value of `src' to `dst'.
654 void silc_mp_abs(SilcMPInt *dst, SilcMPInt *src);
656 /****f* silcmath/SilcMPAPI/silc_mp_neg
660 * void silc_mp_neg(SilcMPInt *dst, SilcMPInt *src);
664 * Negate `src' and save the result to `dst'.
667 void silc_mp_neg(SilcMPInt *dst, SilcMPInt *src);
669 /****f* silcmath/SilcMPAPI/silc_mp_and
673 * void silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
677 * Logical and operator. The result is saved to `dst'.
680 void silc_mp_and(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
682 /****f* silcmath/SilcMPAPI/silc_mp_or
686 * void silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
690 * Logical inclusive OR operator. The result is saved to `dst'.
693 void silc_mp_or(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
695 /****f* silcmath/SilcMPAPI/silc_mp_xor
699 * void silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);
703 * Logical exclusive OR operator. The result is saved to `dst'.
706 void silc_mp_xor(SilcMPInt *dst, SilcMPInt *mp1, SilcMPInt *mp2);