Quadruple-and-add for BLS24 Miller loop

[yelhousni]

Similarly to BLS12 curves, BLS24 Miller loop counter is the curve seed u. Although this seed is 32 bits (half the size of BLS12 seeds), the BLS24 Miller loop is slower. This is mainly because the most costly operations encountered in the Miller loop computation are those that take place in the full extension field Fp24. Implementing this paper's [CBNW10] quadruple-and-add algorithm would reduce operations in Fp24 (see section 6 for comparisons).

[Raneet10]

Hi! Has this been or being worked on ? In case it hasn't been (or isn't being), I would like to take a stab at it, given that it's a good first issue. Thanks!

[yelhousni]

Hi! Has this been or being worked on ? In case it hasn't been (or isn't being), I would like to take a stab at it, given that it's a good first issue. Thanks!

Hi @Raneet10 ! No this is still an open issue — go for it! It might come in handy in the near future.

[Raneet10]

The Miller 2^n-tuple-and-add Algorithm (Algorithm 2 in the paper) defines the loop counter as m = (ml−1...m1, m0)2^n but its representation doesn't have to be changed does it for n=2 , which is our case for quadrupling ?

[yelhousni]

The Miller 2^n-tuple-and-add Algorithm (Algorithm 2 in the paper) defines the loop counter as m = (ml−1...m1, m0)2^n but its representation doesn't have to be changed does it for n=2 , which is our case for quadrupling ?

For n=2, I guess with a binary decomposition you would just need to scan bits 2-by-2 and use Lookup2 I guess.