+}
+
+/******************************************************************************/
+
+/*
+ * dest = a * R mod m
+ */
+void bigint_mont_trans(bigint_t *dest, const bigint_t *a, const bigint_t *m){
+ bigint_t t;
+
+ ALLOC_BIGINT_WORDS(t_w, a->length_W + m->length_W);
+ t.wordv = t_w;
+ memset(t_w, 0, m->length_W * sizeof(bigint_word_t));
+ memcpy(&t_w[m->length_W], a->wordv, a->length_W * sizeof(bigint_word_t));
+ t.info = a->info;
+ t.length_W = a->length_W + m->length_W;
+ bigint_reduce(&t, m);
+ bigint_copy(dest, &t);
+ FREE(t_w);
+}
+
+/******************************************************************************/
+
+/* calculate dest = a**exp % r */
+/* using square&multiply */
+void bigint_expmod_u_mont_accel(bigint_t *dest, const bigint_t *a, const bigint_t *exp, const bigint_t *r, const bigint_t *m_){
+ if(r->length_W == 0) {
+ return;
+ }
+
+ bigint_t res, ax;
+ bigint_word_t t;
+ bigint_length_t i;
+ uint8_t j;
+
+ if (exp->length_W == 0) {
+ dest->length_W = 1;
+ dest->info = 0;
+ dest->wordv[0] = 1;
+ return;
+ }
+
+ ALLOC_BIGINT_WORDS(res_w, r->length_W * 2);
+ ALLOC_BIGINT_WORDS(ax_w, MAX(r->length_W, a->length_W));
+
+ res.wordv = res_w;
+ ax.wordv = ax_w;
+
+ res.wordv[0] = 1;
+ res.length_W = 1;
+ res.info = 0;
+
+ bigint_copy(&ax, a);
+ bigint_reduce(&ax, r);
+
+ bigint_mont_trans(&ax, &ax, r);
+ bigint_mont_trans(&res, &res, r);
+
+ uint8_t flag = 0;
+ t = exp->wordv[exp->length_W - 1];
+ for (i = exp->length_W; i > 0; --i) {
+ t = exp->wordv[i - 1];
+ for(j = BIGINT_WORD_SIZE; j > 0; --j){
+ if (!flag) {
+ if(t & (((bigint_word_t)1) << (BIGINT_WORD_SIZE - 1))){
+ flag = 1;
+ }
+ }
+ if (flag) {
+ bigint_square(&res, &res);
+ bigint_mont_red(&res, &res, r, m_);
+ if (t & (((bigint_word_t)1) << (BIGINT_WORD_SIZE - 1))) {
+ bigint_mont_mul(&res, &res, &ax, r, m_);
+ }
+ }
+ t <<= 1;
+ }
+ }
+ SET_POS(&res);
+ bigint_mont_red(dest, &res, r, m_);
+ FREE(ax_w);
+ FREE(res_w);
+}
+
+/******************************************************************************/
+
+void bigint_expmod_u_mont_sam(bigint_t *dest, const bigint_t *a, const bigint_t *exp, const bigint_t *r){
+ if(r->length_W == 0) {
+ return;
+ }
+ if(a->length_W == 0) {
+ bigint_set_zero(dest);
+ return;
+ }
+ bigint_t m_;
+ bigint_word_t m_w_[r->length_W + 1];
+ m_.wordv = m_w_;
+ bigint_mont_gen_m_(&m_, r);
+ bigint_expmod_u_mont_accel(dest, a, exp, r,&m_);
+}
+
+/******************************************************************************/
+
+#endif
+
+void bigint_expmod_u(bigint_t *dest, const bigint_t *a, const bigint_t *exp, const bigint_t *r){
+#if 0
+ printf("\nDBG: expmod_u (a ** e %% m) <%s %s %d>\n\ta: ", __FILE__, __func__, __LINE__);
+ bigint_print_hex(a);
+ printf("\n\te: ");
+ bigint_print_hex(exp);
+ printf("\n\tm: ");
+ bigint_print_hex(r);
+#endif
+ if (0 && r->wordv[0] & 1) {
+ bigint_expmod_u_mont_sam(dest, a, exp, r);
+ } else {
+ bigint_expmod_u_sam(dest, a, exp, r);
+ }
+}