Optimized multiplication by constant routines

[ValarDragon]

Something very nice that exists in Constantine is that multiplications by a constant can be inline-addition chained. https://github.com/mratsim/constantine/blob/2c5e12d5f893c6af9b97fec17d572268de3bd899/constantine/arithmetic/finite_fields.nim#L385

It would be very nice if we could do this as well.

This particularly of interest for multiplying by a non-residue, as often these are quite simple numbers, e.g. for bls12-377 its -5 for fp2, 1 for fp6, and x^2 for fp12. For -5 in particular, it can be computed with an addition chain of 4 operations

let mut a = x.double();
a.double_in_place();
x += a;
x.neg();

which per benchmarks in #198 should be under half the time it takes to compute a multiplication.

Similarly, we should be able to make improved routines for the particular fp6 and fp12 numbers.

Is there an easy way to introduce an API for "multiply by compile time constant, and switch based on constant?" We could achieve this with macros, but is there a simpler choice available?

[Pratyush]

We already have mul_by_non_residue methods which should be specialized when instantiating the fields, but I agree that it would be nice to have this for other use cases

[ValarDragon]

Oh cool, I missed the mul_by_non_residue method!

[jon-chuang]

I agree, it seems possible that one can have an unrolled double and add loop for small values. But the range of values where this is worth the while seems limited (which is why constantine stops at 12).

Hence I think the current method works just as well.

[mratsim]

Note that I've reworked the addition chain to use less copies over the weekend: https://github.com/mratsim/constantine/blob/5806cc46/constantine/arithmetic/finite_fields.nim#L362-L440