[WIP] add cyclotomic square of fp12 element

[Raneet10]

Add cyclotomic square of fp12 element

Description

This PR attempts to add faster squaring for 6th cyclotomic subgroup elements. I imagine this would be the first step towards implementing #544

I tried implementing what I described in this comment but there are obvious gaps in my knowledge which is apparent in the code. Hence, I am hoping to get reviews here to bridge those gaps and clear away my misunderstandings.

Type of change

Please delete options that are not relevant.

• [x] New feature
• [ ] Bug fix
• [x] Optimization

Checklist

• [x] Linked to Github Issue
• [x] Unit tests added
• [ ] This change requires new documentation.
  • [ ] Documentation has been added/updated.
• [x] This change is an Optimization
  • [ ] Benchmarks added/run

[Raneet10]

As mentioned in Telegram

It's important to mention in document that the paper uses a Fp2->Fp4->Fp12 towering while usually people implement Fp2->Fp6->Fp12.

Formulas need to be adapted like this depending on towering: https://github.com/mratsim/constantine/blob/master/constantine%2Fmath%2Fpairings%2Fcyclotomic_subgroups.nim#L278

Thanks for the reference! Unless I'm missing something, the paper seems to derive the squaring for Fp6 (by cubic over quadratic, Fp -> Fp2 -> Fp6) and not Fp12. I tried to follow the same train of thought here in this rundown , which I believe is quadratic over cubic over quadratic (Fp -> Fp2 -> Fp6 -> Fp12). Could you maybe go through that and let me know if it makes sense ?

[mratsim]

Unless I'm missing something, the paper seems to derive the squaring for Fp6 (by cubic over quadratic, Fp -> Fp2 -> Fp6) and not Fp12. I tried to follow the same train of thought https://github.com/lambdaclass/lambdaworks/issues/544#issuecomment-1925423017, which I believe is quadratic over cubic over quadratic (Fp -> Fp2 -> Fp6 -> Fp12). Could you maybe go through that and let me know if it makes sense ?

The paper is about cyclotomic subgroups first and foremost, and use Fp6 as an example with Fp->Fp2->Fp6 towering. You're using Fp12, so paper formulas apply in your case for Fp2->Fp4->Fp12 towering.

Hence either you match the paper cubic over quadratic or you adapt the formulas.

[Raneet10]

The paper is about cyclotomic subgroups first and foremost, and use Fp6 as an example with Fp->Fp2->Fp6 towering. You're using Fp12, so paper formulas apply in your case for Fp2->Fp4->Fp12 towering.

Hence either you match the paper cubic over quadratic or you adapt the formulas.

I see. So should I be deriving the formula for Fp6 via Fp -> Fp3 -> Fp6 and substitute into the derivation I did here: https://github.com/lambdaclass/lambdaworks/issues/544#issuecomment-1925423017 ? Additionally would love if you can point out any mis-assumptions in the derivation itself and why the approach I took isn't going to yield correct results. Sorry if I'm being dumb 😄

[mratsim]

So should I be deriving the formula for Fp6 via Fp -> Fp3 -> Fp6

No, you forget about Fp, completely. What matters is how Fp12 is built as a 6th degree extension. And it's built as a 6th degree extension from Fp2.

[Raneet10]

No, you forgot about Fp, completely. What matters is how Fp12 is built as a 6th degree extension. And it's built as a 6th degree extension from Fp2.

Okay I see your point. I'll try to revaluate.

[diegokingston]

This functionality has been added