mcl.pow for Fr elements

[atomictag]

Currently mcl.pow is defined as pow: (x: GT, y: Fr) => GT.

It would be useful to support also the signature

pow: (x: Fr, y: Fr) => Fr

or even better

pow: (x: Fr, y: Fr | bigint | number) => Fr

since very often the exponents are not super big.

This would help with several polynomial-related algorithms that would benefit from that (e.g. Vandermonde matrix, root of unity, KZG...). I currently use a js-based algorithm that relies on a loop with mul and sqr operations (which I guess could already be improved by using mcl internals and operate on pointers inside the loop instead of copying things over). but a native .pow() would definitely be more efficient.

Many, many thanks!

[herumi]

Okay, now I'm implementing those methods. https://github.com/herumi/mcl-wasm/commit/3c8563a07dbe0e0becb386c68f4553d49ce6f900 I'll add pow(x, y) for bigint y.

[herumi]

v1.6.0 has supported them. Would you like trying it?

[atomictag]

Thank you so much for this! It works perfectly and it's about 85% (~ 6 times) faster than an equivalent algorithm in javascript using mul and sqr.

The only minor issue (due to the way I extend and use the library and not an issue of the library itself) is the following:

class MyFr extends mcl.Fr { ... } // mcl.Fr extension - e.g. a custom bls.SecretKey

const b: MyFr = ...
const eFr: mcl.Fr = ... // Fr exponent
const eNb: number = ... // scalar exponent

mcl.pow(b, eFr) // returns a MyFr
mcl.pow(b, eNb) // returns a mcl.Fr

This is because powArray is called with explicit constructors Fr instead of x.constructor. Not an issue per se (since the API signature clearly states the return type is a mcl.Fr) but it deviates slightly from the behavior of other (most) mcl.* operators which always preserve the base type in the return value (which is great to build wrappers and extensions around the base mcl types).

Also, it seems that for integer exponents <= 2^31 it is faster to convert them to Fr using setInt() so that _mclBnFr_pow is used instead of _mclBnFr_powArray (my benchmark is not super consistent and most likely the difference is minimal in most practical cases)

Many thanks again 🙏

[herumi]

This is because powArray is called with explicit constructors Fr instead of x.constructor.

Can we fix this with a few modifications?

it is faster to convert them to Fr using setInt() so that _mclBnFr_pow is used instead of _mclBnFr_powArray

In C++, powArray is faster than Fr_pow with setInt because The latter has two more Fr::mul. But in Wasm, the cost of conversion may be higher.

[atomictag]

Can we fix this with a few modifications?

Yes. This should do the trick

function pow(x, y) {
    if (x instanceof Fr) {
        if (y instanceof Fr) {
            return x._op2(mcl_1.mod._mclBnFr_pow, y);
        }
        else if (typeof (y) === 'number' || typeof (y) === 'bigint') {
            return powArray(x.constructor, mcl_1.mod._mclBnFr_powArray, x, y); // <== x.constructor instead of Fr
        }
    }
    if (x instanceof Fp) {
        if (y instanceof Fp) {
            return x._op2(mcl_1.mod._mclBnFp_pow, y);
        }
        else if (typeof (y) === 'number' || typeof (y) === 'bigint') {
            return powArray(x.constructor, mcl_1.mod._mclBnFp_powArray, x, y);  // <== x.constructor instead of Fp
        }
    }
    if (x instanceof GT && y instanceof Fr) {
        return x._op2(mcl_1.mod._mclBnGT_pow, y);
    }
    throw new Error('pow:bad type');
}

[herumi]

Thank you for the quick response. I'll check it later.