Mercurial > dropbear

comparison bn_mp_exptmod.c @ 2:86e0b50a9b58 libtommath-orig ltm-0.30-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ltm 0.30 orig import
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:25:22 +0000
parents
children d29b64170cf0
comparison
equal deleted inserted replaced
-1:000000000000 2:86e0b50a9b58
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 *
3 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality.
5 *
6 * The library was designed directly after the MPI library by
7 * Michael Fromberger but has been written from scratch with
8 * additional optimizations in place.
9 *
10 * The library is free for all purposes without any express
11 * guarantee it works.
12 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org
14 */
15 #include <tommath.h>
16
17
18 /* this is a shell function that calls either the normal or Montgomery
19 * exptmod functions. Originally the call to the montgomery code was
20 * embedded in the normal function but that wasted alot of stack space
21 * for nothing (since 99% of the time the Montgomery code would be called)
22 */
23 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
24 {
25 int dr;
26
27 /* modulus P must be positive */
28 if (P->sign == MP_NEG) {
29 return MP_VAL;
30 }
31
32 /* if exponent X is negative we have to recurse */
33 if (X->sign == MP_NEG) {
34 mp_int tmpG, tmpX;
35 int err;
36
37 /* first compute 1/G mod P */
38 if ((err = mp_init(&tmpG)) != MP_OKAY) {
39 return err;
40 }
41 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
42 mp_clear(&tmpG);
43 return err;
44 }
45
46 /* now get |X| */
47 if ((err = mp_init(&tmpX)) != MP_OKAY) {
48 mp_clear(&tmpG);
49 return err;
50 }
51 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
52 mp_clear_multi(&tmpG, &tmpX, NULL);
53 return err;
54 }
55
56 /* and now compute (1/G)**|X| instead of G**X [X < 0] */
57 err = mp_exptmod(&tmpG, &tmpX, P, Y);
58 mp_clear_multi(&tmpG, &tmpX, NULL);
59 return err;
60 }
61
62 /* is it a DR modulus? */
63 dr = mp_dr_is_modulus(P);
64
65 /* if not, is it a uDR modulus? */
66 if (dr == 0) {
67 dr = mp_reduce_is_2k(P) << 1;
68 }
69
70 /* if the modulus is odd or dr != 0 use the fast method */
71 if (mp_isodd (P) == 1 || dr != 0) {
72 return mp_exptmod_fast (G, X, P, Y, dr);
73 } else {
74 /* otherwise use the generic Barrett reduction technique */
75 return s_mp_exptmod (G, X, P, Y);
76 }
77 }
78