+/*
+ * dest = a * R mod m
+ */
+void bigint_mont_trans(bigint_t *dest, const bigint_t *a, const bigint_t *m){
+ bigint_t t;
+ bigint_word_t 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);
+}
+
+/******************************************************************************/
+
+/* 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_length_t s = r->length_W;
+ bigint_t res, ax;
+ bigint_word_t t, res_w[r->length_W * 2], ax_w[MAX(s, a->length_W)];
+ bigint_length_t i;
+ uint8_t j;
+
+ res.wordv = res_w;
+ ax.wordv = ax_w;
+
+ res.wordv[0] = 1;
+ res.length_W = 1;
+ res.info = 0;
+ bigint_adjust(&res);
+ if (exp->length_W == 0) {
+ bigint_copy(dest, &res);
+ return;
+ }
+ 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_wordplus_t)1) << (BIGINT_WORD_SIZE - 1))){
+ flag = 1;
+ }
+ }
+ if (flag) {
+ bigint_square(&res, &res);
+ bigint_mont_red(&res, &res, r, m_);
+ if (t & (((bigint_wordplus_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_);
+}
+
+/******************************************************************************/
+
+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 (r->wordv[0] & 1) {
+ bigint_expmod_u_mont_sam(dest, a, exp, r);
+ } else {
+ bigint_expmod_u_sam(dest, a, exp, r);
+ }