Commit e9b1837c8c7caf707f6a038456597568b39c3eeb
2014-02-13T20:21:18
mp_expt_d: bring back pre 921be35779f7d71080ad85c27ed58671602d59b3 state The implementation of the expt_d functionality is now implemented in the mp_expt_d_ex() function. The user can now choose between the old (more timing resistant) version and the new version by modification of the parameter 'fast'. mp_expt_d() defaults to the old version
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184
diff --git a/bn_mp_expt_d.c b/bn_mp_expt_d.c
index 2b0b095..ed5f28f 100644
--- a/bn_mp_expt_d.c
+++ b/bn_mp_expt_d.c
@@ -15,41 +15,12 @@
* Tom St Denis, tomstdenis@gmail.com, http://libtom.org
*/
-/* calculate c = a**b using a square-multiply algorithm */
+/* wrapper function for mp_expt_d_ex() */
int mp_expt_d (mp_int * a, mp_digit b, mp_int * c)
{
- int res;
- mp_int g;
-
- if ((res = mp_init_copy (&g, a)) != MP_OKAY) {
- return res;
- }
-
- /* set initial result */
- mp_set (c, 1);
-
- while (b > 0) {
- /* if the bit is set multiply */
- if (b & 1) {
- if ((res = mp_mul (c, &g, c)) != MP_OKAY) {
- mp_clear (&g);
- return res;
- }
- }
-
- /* square */
- if (b > 1 && (res = mp_sqr (&g, &g)) != MP_OKAY) {
- mp_clear (&g);
- return res;
- }
-
- /* shift to next bit */
- b >>= 1;
- }
-
- mp_clear (&g);
- return MP_OKAY;
+ return mp_expt_d_ex(a, b, c, 0);
}
+
#endif
/* $Source$ */
diff --git a/bn_mp_expt_d_ex.c b/bn_mp_expt_d_ex.c
new file mode 100644
index 0000000..f8ff172
--- /dev/null
+++ b/bn_mp_expt_d_ex.c
@@ -0,0 +1,81 @@
+#include <tommath.h>
+#ifdef BN_MP_EXPT_D_EX_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis
+ *
+ * LibTomMath is a library that provides multiple-precision
+ * integer arithmetic as well as number theoretic functionality.
+ *
+ * The library was designed directly after the MPI library by
+ * Michael Fromberger but has been written from scratch with
+ * additional optimizations in place.
+ *
+ * The library is free for all purposes without any express
+ * guarantee it works.
+ *
+ * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
+ */
+
+/* calculate c = a**b using a square-multiply algorithm */
+int mp_expt_d_ex (mp_int * a, mp_digit b, mp_int * c, int fast)
+{
+ int res;
+ unsigned int x;
+
+ mp_int g;
+
+ if ((res = mp_init_copy (&g, a)) != MP_OKAY) {
+ return res;
+ }
+
+ /* set initial result */
+ mp_set (c, 1);
+
+ if (fast) {
+ while (b > 0) {
+ /* if the bit is set multiply */
+ if (b & 1) {
+ if ((res = mp_mul (c, &g, c)) != MP_OKAY) {
+ mp_clear (&g);
+ return res;
+ }
+ }
+
+ /* square */
+ if (b > 1 && (res = mp_sqr (&g, &g)) != MP_OKAY) {
+ mp_clear (&g);
+ return res;
+ }
+
+ /* shift to next bit */
+ b >>= 1;
+ }
+ }
+ else {
+ for (x = 0; x < DIGIT_BIT; x++) {
+ /* square */
+ if ((res = mp_sqr (c, c)) != MP_OKAY) {
+ mp_clear (&g);
+ return res;
+ }
+
+ /* if the bit is set multiply */
+ if ((b & (mp_digit) (((mp_digit)1) << (DIGIT_BIT - 1))) != 0) {
+ if ((res = mp_mul (c, &g, c)) != MP_OKAY) {
+ mp_clear (&g);
+ return res;
+ }
+ }
+
+ /* shift to next bit */
+ b <<= 1;
+ }
+ } /* if ... else */
+
+ mp_clear (&g);
+ return MP_OKAY;
+}
+#endif
+
+/* $Source$ */
+/* $Revision$ */
+/* $Date$ */
diff --git a/makefile b/makefile
index ed7bd91..e9b2eab 100644
--- a/makefile
+++ b/makefile
@@ -96,7 +96,7 @@ bn_mp_init_multi.o bn_mp_clear_multi.o bn_mp_exteuclid.o bn_mp_toradix_n.o \
bn_mp_prime_random_ex.o bn_mp_get_int.o bn_mp_sqrt.o bn_mp_is_square.o bn_mp_init_set.o \
bn_mp_init_set_int.o bn_mp_invmod_slow.o bn_mp_prime_rabin_miller_trials.o \
bn_mp_to_signed_bin_n.o bn_mp_to_unsigned_bin_n.o bn_mp_import.o bn_mp_export.o \
-bn_mp_balance_mul.o
+bn_mp_balance_mul.o bn_mp_expt_d_ex.o
$(LIBNAME): $(OBJECTS)
$(AR) $(ARFLAGS) $@ $(OBJECTS)
diff --git a/tommath.h b/tommath.h
index 8a71d3c..7b5a703 100644
--- a/tommath.h
+++ b/tommath.h
@@ -364,6 +364,7 @@ int mp_div_3(mp_int *a, mp_int *c, mp_digit *d);
/* c = a**b */
int mp_expt_d(mp_int *a, mp_digit b, mp_int *c);
+int mp_expt_d_ex (mp_int * a, mp_digit b, mp_int * c, int fast);
/* c = a mod b, 0 <= c < b */
int mp_mod_d(mp_int *a, mp_digit b, mp_digit *c);
diff --git a/tommath_class.h b/tommath_class.h
index 238e72d..6569f18 100644
--- a/tommath_class.h
+++ b/tommath_class.h
@@ -41,6 +41,7 @@
#define BN_MP_EXCH_C
#define BN_MP_EXPORT_C
#define BN_MP_EXPT_D_C
+#define BN_MP_EXPT_D_EX_C
#define BN_MP_EXPTMOD_C
#define BN_MP_EXPTMOD_FAST_C
#define BN_MP_EXTEUCLID_C
@@ -333,6 +334,10 @@
#endif
#if defined(BN_MP_EXPT_D_C)
+ #define BN_MP_EXPT_D_EX_C
+#endif
+
+#if defined(BN_MP_EXPT_D_EX_C)
#define BN_MP_INIT_COPY_C
#define BN_MP_SET_C
#define BN_MP_MUL_C