Mercurial > dropbear

comparison bn_mp_exptmod.c @ 1:22d5cf7d4b1a libtommath

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Renaming branch
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:23:46 +0000
parents
children a96ff234ff19
comparison
equal deleted inserted replaced
-1:000000000000 1:22d5cf7d4b1a
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 #ifndef NO_FAST_EXPTMOD
72 if (mp_isodd (P) == 1 || dr != 0) {
73 return mp_exptmod_fast (G, X, P, Y, dr);
74 }
75 else
76 #endif
77 {
78 /* otherwise use the generic Barrett reduction technique */
79 return s_mp_exptmod (G, X, P, Y);
80 }
81 }
82