The implementation of towered fields is difficult to relate to documented constructions

[daira]

(This issue spans algebra and curves, but seems more pertinent here.)

Consider the implementation of towers of field extensions, for example here for BLS12-381. The usual way to describe such towers is by the irreducible polynomial used for each extension. For instance, the bls12_381 crate implements F_p² as F_p[u]/(u² + 1), and then F_p⁶ as F_p²[v]/(v³ - (u + 1)), and then F_p¹² as F_p⁶[w]/(w² - v).

(Strictly speaking there's an abuse of notation here because, e.g. when we write F_p⁶[w]/(w² - v) we're conflating the field F_p⁶ with its representation, but apparently everyone abuses notation that way.)

The choice of irreducible polynomials is fairly arbitrary, but for interoperability it's best for the originator of a curve to pick them and for everyone to use the same ones for that curve. A specific representation for each extension field used by a pairing is needed, at least in order to unambiguously specify the curve and generator for G₂, and for test vectors. (You can technically convert between representations, but it's a pain and no-one should need to do that extra work.)

The problem is that the implementation of a tower in arkworks doesn't directly specify these irreducible polynomials (and also doesn't document what they are for existing implementations). Each extension specifies a NONRESIDUE, and F_p² extensions also specify a QUADRATIC_NONRESIDUE, but I can't tell how these relate to the irreducible polynomial, even after poring over the implementations in algebra/ff/src/fields/models.

[weikengchen]

I agree that the irreducible polynomial is basically hidden throughout both repos. And it seems that the current implementations in https://github.com/arkworks-rs/algebra/tree/master/ff/src/fields/models focus on only specific irreducible polynomials.

Should we add more explanations in models? Do you think there will be use cases that use more special irreducible polynomials?

[weikengchen]

(Note: generally there exist some prime numbers that could cause some of these polynomials to be not irreducible, but it seems to be rare)

[daira]

If I had to guess by extrapolation from BLS12-381, I'd guess that a k-extension uses the irreducible polynomial u^k - NONRESIDUE. Is that right?

More explanation would definitely be good!

It's not so rare; e.g. Pluto's field cannot use u² + 1 for F_p², and so it is currently specified to use u² + 5 (I'll change that if needed). In fact u² + 1 will never be irreducible for a pairing or half-pairing cycle with high 2-adicity, because we must have p = 1 (mod 8).

[daira]

This is blocking my implementation of Pluto and Triton in arkworks-rs/curves#54. The documentation needed is of how the constants such as NONRESIDUE and QUADRATIC_NONRESIDUE correspond to the usual description of a tower.

[Pratyush]

QUADRATIC_NONRESIDUE is used only as an implementation detail in the square-root algorithm, while NONRESIDUE is used to construct the extension. Eg, see here for quadratic extensions and here for cubic extensions.

The documentation on QuadExtField should be helpful also.

[weikengchen]

So it seems that it is possible to implement u^2+5, just one needs to choose the NONRESIDUE in Fq2Parameters to be -5.

On a related note, I recently also implemented the BN446 inside the arkworks environment here: https://github.com/oblivious-file-sharing/netherite-algebra/tree/main/src/curve_bn446
It has associated Sage scripts, which may be helpful.