1/*	$NetBSD: bn_mp_exptmod.c,v 1.2 2017/01/28 21:31:47 christos 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 */
26int 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