1 /* $NetBSD: bn_mp_exptmod.c,v 1.1.1.2 2014/04/24 12:45:31 pettai Exp $ */
2
3 #include <tommath.h>
4 #ifdef BN_MP_EXPTMOD_C
5 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6 *
7 * LibTomMath is a library that provides multiple-precision
8 * integer arithmetic as well as number theoretic functionality.
9 *
10 * The library was designed directly after the MPI library by
11 * Michael Fromberger but has been written from scratch with
12 * additional optimizations in place.
13 *
14 * The library is free for all purposes without any express
15 * guarantee it works.
16 *
17 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
18 */
19
20
21 /* this is a shell function that calls either the normal or Montgomery
22 * exptmod functions. Originally the call to the montgomery code was
23 * embedded in the normal function but that wasted alot of stack space
24 * for nothing (since 99% of the time the Montgomery code would be called)
25 */
mp_exptmod(mp_int * G,mp_int * X,mp_int * P,mp_int * Y)26 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
27 {
28 int dr;
29
30 /* modulus P must be positive */
31 if (P->sign == MP_NEG) {
32 return MP_VAL;
33 }
34
35 /* if exponent X is negative we have to recurse */
36 if (X->sign == MP_NEG) {
37 #ifdef BN_MP_INVMOD_C
38 mp_int tmpG, tmpX;
39 int err;
40
41 /* first compute 1/G mod P */
42 if ((err = mp_init(&tmpG)) != MP_OKAY) {
43 return err;
44 }
45 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
46 mp_clear(&tmpG);
47 return err;
48 }
49
50 /* now get |X| */
51 if ((err = mp_init(&tmpX)) != MP_OKAY) {
52 mp_clear(&tmpG);
53 return err;
54 }
55 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
56 mp_clear_multi(&tmpG, &tmpX, NULL);
57 return err;
58 }
59
60 /* and now compute (1/G)**|X| instead of G**X [X < 0] */
61 err = mp_exptmod(&tmpG, &tmpX, P, Y);
62 mp_clear_multi(&tmpG, &tmpX, NULL);
63 return err;
64 #else
65 /* no invmod */
66 return MP_VAL;
67 #endif
68 }
69
70 /* modified diminished radix reduction */
71 #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C)
72 if (mp_reduce_is_2k_l(P) == MP_YES) {
73 return s_mp_exptmod(G, X, P, Y, 1);
74 }
75 #endif
76
77 #ifdef BN_MP_DR_IS_MODULUS_C
78 /* is it a DR modulus? */
79 dr = mp_dr_is_modulus(P);
80 #else
81 /* default to no */
82 dr = 0;
83 #endif
84
85 #ifdef BN_MP_REDUCE_IS_2K_C
86 /* if not, is it a unrestricted DR modulus? */
87 if (dr == 0) {
88 dr = mp_reduce_is_2k(P) << 1;
89 }
90 #endif
91
92 /* if the modulus is odd or dr != 0 use the montgomery method */
93 #ifdef BN_MP_EXPTMOD_FAST_C
94 if (mp_isodd (P) == 1 || dr != 0) {
95 return mp_exptmod_fast (G, X, P, Y, dr);
96 } else {
97 #endif
98 #ifdef BN_S_MP_EXPTMOD_C
99 /* otherwise use the generic Barrett reduction technique */
100 return s_mp_exptmod (G, X, P, Y, 0);
101 #else
102 /* no exptmod for evens */
103 return MP_VAL;
104 #endif
105 #ifdef BN_MP_EXPTMOD_FAST_C
106 }
107 #endif
108 }
109
110 #endif
111
112 /* Source: /cvs/libtom/libtommath/bn_mp_exptmod.c,v */
113 /* Revision: 1.5 */
114 /* Date: 2006/12/28 01:25:13 */
115