Function fxBigInt_mont_exp_SW

modules/crypt/arith/xsBigIntEx.c:539–598

}

txBigInt *fxBigInt_mont_exp_SW(txMachine *the, txBigInt *r, txBigInt *b, txBigInt *e, txBigInt *m, int param)
{
	unsigned int expLen;
	int i, k, gsize;
	txBigInt *A;
	txBigInt *g[64];
	txU4 u;
	pool_t pool;

	if (r == NULL)
		r = fxBigInt_alloc(the, m->size);
	pool_init(&pool);
	u = mont_init(m);
	A = mont_exp_init(the, pool_get(the, m->size, &pool), m, &pool);
	if (fxBigInt_ucomp(b, m) > 0)
		b = fxBigInt_mod(the, pool_get(the, m->size, &pool), b, m);
	b = mont_in(the, pool_get(the, m->size, &pool), b, m);
	expLen = fxBigInt_bitsize(e);
	if (param > 0)
		k = param;
	else
		k = (expLen <= 18 ? 1 : (expLen <= 36 ? 2 : (expLen <= 134 ? 3 : (expLen <= 536 ? 4 : (expLen <= 1224 ? 5 : (expLen <= 1342 ? 6 : 7))))));
	gsize = 1 << (k - 1);
	for (i = 0; i < gsize; i++)
		g[i] = pool_get(the, m->size, &pool);
	fxBigInt_copy(g[0], b);
	if (k > 1) {
		txBigInt *t = mont_square(the, pool_get(the, m->size, &pool), b, m, u, &pool);
		for (i = gsize; --i >= 1;)
			mont_mul(the, g[i], t, g[i - 1], m, u, &pool);
	}
	for (i = expLen - 1; i >= 0;) {
		if (!fxBigInt_isset(e, i)) {
			mont_square(the, A, A, m, u, &pool);
			--i;
		}
		else {
			int j, l;
			int power = 0;
			int shift = 0;
			for (j = l = i; j >= 0 && i - j + 1 <= k; --j) {
				if (fxBigInt_isset(e, j)) {
					l = j;
					power = (power << (shift + 1)) | 1;
					shift = 0;
				}
				else
					shift++;
			}
			mont_square(the, A, A, m, u, &pool);
			for (j = 1; j < i - l + 1; j++)
				mont_square(the, A, A, m, u, &pool);
			mont_mul(the, A, A, g[(power-1)>>1], m, u, &pool);
			i = l - 1;
		}
	}
	mont_out(the, r, A, m, u);
	pool_dispose(the, &pool);