+
+/******************************************************************************/
+
+/* calculate dest = a**exp % r */
+/* using square&multiply */
+void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r){
+ if(a->length_W==0 || r->length_W==0){
+ return;
+ }
+
+ bigint_t res, base;
+ bigint_word_t t, base_b[MAX(a->length_W,r->length_W)], res_b[r->length_W*2];
+ uint16_t i;
+ uint8_t j;
+// uint16_t *xaddr = &i;
+// cli_putstr("\r\npre-alloc (");
+// cli_hexdump_rev(&xaddr, 4);
+// cli_putstr(") ...");
+ res.wordv = res_b;
+ base.wordv = base_b;
+ bigint_copy(&base, a);
+// cli_putstr("\r\npost-copy");
+ bigint_reduce(&base, r);
+ res.wordv[0]=1;
+ res.length_W=1;
+ res.info = 0;
+ bigint_adjust(&res);
+ if(exp->length_W == 0){
+ bigint_copy(dest, &res);
+ return;
+ }
+ 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 & (1<<(BIGINT_WORD_SIZE-1))){
+ flag = 1;
+ }
+ }
+ if(flag){
+ bigint_square(&res, &res);
+ bigint_reduce(&res, r);
+ if(t & (1 << (BIGINT_WORD_SIZE - 1))){
+ bigint_mul_u(&res, &res, &base);
+ bigint_reduce(&res, r);
+ }
+ }
+ t <<= 1;
+ }
+ }
+
+// cli_putc('+');
+ SET_POS(&res);
+ bigint_copy(dest, &res);
+}
+
+/******************************************************************************/
+#if 1
+#define cli_putstr(a)
+#define cli_putstr_P(a)
+#define bigint_print_hex(a)
+#define cli_hexdump_rev(a,b)
+#define uart_flush(a)
+#define printf_P(...)
+#endif
+/* gcd <-- gcd(x,y) a*x+b*y=gcd */
+void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, const bigint_t* y){
+ uint16_t i = 0;
+ printf_P(PSTR("\nDBG: gcdext( "));
+ bigint_print_hex(x);
+ printf_P(PSTR(", "));
+ bigint_print_hex(y);
+ printf_P(PSTR(")\n"));
+ if(x->length_W == 0 || y->length_W == 0){
+ printf_P(PSTR("\nDBG: got zero in gcd <%s %s %d>\n"), __FILE__, __func__, __LINE__);
+ if(gcd){
+ bigint_set_zero(gcd);
+ }
+ if(a){
+ bigint_set_zero(a);
+ }
+ if(b){
+ bigint_set_zero(b);
+ }
+ return;
+ }
+ if(x->length_W == 1 && x->wordv[0] == 1){
+ if(gcd){
+ gcd->length_W = 1;
+ gcd->wordv[0] = 1;
+ gcd->info = 0;
+ }
+ if(a){
+ a->length_W = 1;
+ a->wordv[0] = 1;
+ SET_POS(a);
+ bigint_adjust(a);
+ }
+ if(b){
+ bigint_set_zero(b);
+ }
+ return;
+ }
+ if(y->length_W == 1 && y->wordv[0] == 1){
+ if(gcd){
+ gcd->length_W = 1;
+ gcd->wordv[0] = 1;
+ gcd->info = 0;
+ }
+ if(b){
+ b->length_W = 1;
+ b->wordv[0] = 1;
+ SET_POS(b);
+ bigint_adjust(b);
+ }
+ if(a){
+ bigint_set_zero(a);
+ }
+ return;
+ }
+
+ while(x->wordv[i] == 0 && y->wordv[i] == 0){
+ ++i;
+ }
+ bigint_word_t g_b[i + 2], x_b[x->length_W - i], y_b[y->length_W - i];
+ bigint_word_t u_b[x->length_W - i], v_b[y->length_W - i];
+ bigint_word_t a_b[y->length_W + 2], c_b[y->length_W + 2];
+ bigint_word_t b_b[x->length_W + 2], d_b[x->length_W + 2];
+ bigint_t g, x_, y_, u, v, a_, b_, c_, d_;
+
+ g.wordv = g_b;
+ x_.wordv = x_b;
+ y_.wordv = y_b;
+ memset(g_b, 0, i * sizeof(bigint_word_t));
+ g_b[i] = 1;
+ g.length_W = i + 1;
+ g.info = 0;
+ x_.info = y_.info = 0;
+ x_.length_W = x->length_W - i;
+ y_.length_W = y->length_W - i;
+ memcpy(x_.wordv, x->wordv + i, x_.length_W * sizeof(bigint_word_t));
+ memcpy(y_.wordv, y->wordv + i, y_.length_W * sizeof(bigint_word_t));
+ for(i = 0; (x_.wordv[0] & (1 << i)) == 0 && (y_.wordv[0] & (1 << i)) == 0; ++i){
+ }
+
+ bigint_adjust(&x_);
+ bigint_adjust(&y_);
+
+ if(i){
+ bigint_shiftleft(&g, i);
+ bigint_shiftright(&x_, i);
+ bigint_shiftright(&y_, i);
+ }
+
+ u.wordv = u_b;
+ v.wordv = v_b;
+ a_.wordv = a_b;
+ b_.wordv = b_b;
+ c_.wordv = c_b;
+ d_.wordv = d_b;
+
+ bigint_copy(&u, &x_);
+ bigint_copy(&v, &y_);
+ a_.wordv[0] = 1;
+ a_.length_W = 1;
+ a_.info = 0;
+ d_.wordv[0] = 1;
+ d_.length_W = 1;
+ d_.info = 0;
+ bigint_set_zero(&b_);
+ bigint_set_zero(&c_);
+ printf_P(PSTR("\nloop: x_ = "));
+ bigint_print_hex(&x_);
+ printf_P(PSTR("; y_ = "));
+ bigint_print_hex(&y_);
+ do{
+ printf_P(PSTR("\nDBG (gcdext) 0"));
+ while((u.wordv[0] & 1) == 0){
+ printf_P(PSTR("\nDBG (gcdext) 0.1"));
+ bigint_shiftright(&u, 1);
+ if((a_.wordv[0] & 1) || (b_.wordv[0] & 1)){
+ bigint_add_s(&a_, &a_, &y_);
+ bigint_sub_s(&b_, &b_, &x_);
+ }
+ bigint_shiftright(&a_, 1);
+ bigint_shiftright(&b_, 1);
+ printf_P(PSTR(" a_ = "));
+ bigint_print_hex(&a_);
+ printf_P(PSTR("; b_ = "));
+ bigint_print_hex(&b_);
+ }
+ while((v.wordv[0] & 1) == 0){
+ printf_P(PSTR("\nDBG (gcdext) 0.2"));
+ bigint_shiftright(&v, 1);
+ if((c_.wordv[0] & 1) || (d_.wordv[0] & 1)){
+ bigint_add_s(&c_, &c_, &y_);
+ bigint_sub_s(&d_, &d_, &x_);
+ }
+ printf_P(PSTR(" c* = "));
+ bigint_print_hex(&c_);
+ bigint_shiftright(&c_, 1);
+ bigint_shiftright(&d_, 1);
+ printf_P(PSTR(" c_ = "));
+ bigint_print_hex(&c_);
+ printf_P(PSTR("; d_ = "));
+ bigint_print_hex(&d_);
+ }
+ if(bigint_cmp_u(&u, &v) >= 0){
+ printf_P(PSTR("\nDBG (gcdext) 0.3"));
+ bigint_sub_u(&u, &u, &v);
+ bigint_sub_s(&a_, &a_, &c_);
+ bigint_sub_s(&b_, &b_, &d_);
+ printf_P(PSTR(" a_ = "));
+ bigint_print_hex(&a_);
+ printf_P(PSTR("; b_ = "));
+ bigint_print_hex(&b_);
+ }else{
+ printf_P(PSTR("\nDBG (gcdext) 0.4"));
+ bigint_sub_u(&v, &v, &u);
+ bigint_sub_s(&c_, &c_, &a_);
+ bigint_sub_s(&d_, &d_, &b_);
+ printf_P(PSTR(" c_ = "));
+ bigint_print_hex(&c_);
+ printf_P(PSTR("; d_ = "));
+ bigint_print_hex(&d_);
+ }
+ }while(u.length_W);
+ if(gcd){
+ bigint_mul_s(gcd, &v, &g);
+ }
+ if(a){
+ bigint_copy(a, &c_);
+ }
+ if(b){
+ bigint_copy(b, &d_);
+ }
+}
+
+/******************************************************************************/
+
+void bigint_inverse(bigint_t* dest, const bigint_t* a, const bigint_t* m){
+ bigint_gcdext(NULL, dest, NULL, a, m);
+ while(dest->info&BIGINT_NEG_MASK){
+ bigint_add_s(dest, dest, m);
+ }
+}
+
+/******************************************************************************/
+
+void bigint_changeendianess(bigint_t* a){
+ uint8_t t, *p, *q;
+ p = (uint8_t*)(a->wordv);
+ q = p + a->length_W * sizeof(bigint_word_t) - 1;
+ while(p<q){
+ t = *p;
+ *p = *q;
+ *q = t;
+ ++p; --q;
+ }
+}
+
+/******************************************************************************/
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+