Optimize the final exponentiation

[yelhousni]

The cost of the final exponentiation is dominated by Expt(), which is a square-and-multiply exponentiation by the curve seed u. Currently, the squarings are implemented as in the Granger-Scott cyclotomic squaring (GS).

For the curves implemented in gnark-crypto (except for BN254), there is a series of consecutive 0's in the seed and it might be interesting to switch to the Karabina cyclotomic squaring only of this series.

Karabina's method works on compressed GT elements and saves 2 multiplications in F_p^{k/d} compared to GS, where k is the embedding degree and d the twist degree. The cost of decompression, however, is dominated by an inverse in F_p^{k/d}.

Concretely, given a series of s 0's in the seed, the trick is worth it if:

• For BLS12, 1 inverse over F_p costs less than 6*s-4 muls over F_p
• For BLS24, 1 inverse over F_p costs less than 18*s-16 muls over F_p

[yelhousni]

If there are more than one series of 0's for which Karabina's cyclotomic square is better, one can use a Montgomery batch inverse to decompress the results of both series at once. Concretely, this happens for BLS24-315 and yields significant speedup and for BLS12-381 but with minor speedup.