BN curves refactor.

[mratsim]

I suggest separating the extension fields logic from the pairing logic.

This would allow more flexibility in adding curves with embedding degrees != 12 like BW6-761 (that embeds BLS12-377) or BLS24 curves (which are more efficient than BLS12 curves for KZG as they can have a smaller base field).

For instance this works very well in Constantine:

• extension fields:

  • non-residues: https://github.com/mratsim/constantine/blob/5894a8da/constantine/math/extension_fields/towers.nim#L605-L694
  • quadratic: https://github.com/mratsim/constantine/blob/5894a8da/constantine/math/extension_fields/towers.nim#L744
  • cubic: https://github.com/mratsim/constantine/blob/5894a8da/constantine/math/extension_fields/towers.nim#L1503

  with only core field operations

• pairings:

  • line functions: Frobenius map, mul_by_014, mul_by_034
  • cyclotomic subgroup: inversion via conjugate, cyclotomic square and cyclotomic exponentiation, final exponentiation easy part
  • pairings: Miller loop, final exponentiation hard part and the full pairing functions

  see: https://github.com/mratsim/constantine/tree/5894a8da/constantine/math/pairings

[davidnevadoc]

Thanks for the recommendation @mratsim. I think following that separation is a good idea, I'll do that!

While working on this I started thinking about the order of the extensions in the towers. The most common ordering I've seen is Fp12:Fp6:Fp2:Fp. Do you think it is fine to have only this construction in mind or should we aim to also support others?

[davidnevadoc]

These changes have been mostly implemented in https://github.com/privacy-scaling-explorations/halo2curves/pull/161.

[mratsim]

While working on this I started thinking about the order of the extensions in the towers. The most common ordering I've seen is Fp12:Fp6:Fp2:Fp. Do you think it is fine to have only this construction in mind or should we aim to also support others?

I forgot to reply, the Fp12->Fp4 for me is noticeably faster for BLS12-381

The tradeoff is that inversion suffers.