Tower field extension for cryptography

finite-fields

asked 2026-04-01 10:42:35 +0200

j08ny
21 ●3

I am trying to instantiate the BLS48_581 tower of extension fields from draft-irtf-cfrg-pairing-friendly-curves-12:

   p = 0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac3edc154e6565912b
   GF(p^2) = GF(p)[u] / (u^2 + 1)
   GF(p^4) = GF(p^2)[v] / (v^2 + u + 1)
   GF(p^8) = GF(p^4)[w] / (w^2 + v)

The best I could do was this:

p = 0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac3edc154e6565912b
Fp = GF(p)

# Fp2 = Fp[u]/(u^2 + 1)
R.<u> = PolynomialRing(Fp)
Fp2.<u> = Fp.extension(u^2 + 1)

# Fp4 = Fp2[v]/(v^2 + u + 1)
S.<v> = PolynomialRing(Fp2)
Fp4.<v> = Fp2.extension(v^2 + u + 1)

# Fp8 = Fp4[w]/(w^2 + v)
T.<w> = PolynomialRing(Fp4)
Fp8.<w> = Fp4.extension(w^2 + v)

However, the third field extension (Fp8) just refuses to be created in a reasonable time. When I check the types of the objects I get:

sage: Fp
Finite Field of size 4576545538729420598762745822889397370509838601207708465545582186285824315458656151272834027217178198654229063318759931344008864619718319130560845441720114764111976549023322411
sage: Fp2
Finite Field in u of size 4576545538729420598762745822889397370509838601207708465545582186285824315458656151272834027217178198654229063318759931344008864619718319130560845441720114764111976549023322411^2
sage: Fp4
Univariate Quotient Polynomial Ring in v over Finite Field in u of size 4576545538729420598762745822889397370509838601207708465545582186285824315458656151272834027217178198654229063318759931344008864619718319130560845441720114764111976549023322411^2 with modulus v^2 + u + 1

Then, the extension of that goes through a slow path of:

CommutativeRing.extension() -> QuotientRing -> PolynomialRing_commutative.quotient_by_principal_ideal -> PolynomialQuotientRingFactory.create_object -> Polynomial.is_irreducible() -> Polynomial.factor()

I can not pass check_irreducible=False, because the method then complains:

Fp4.<v> = Fp2.extension(v^2 + u + 1, check_irreducible=False)
File /usr/lib/python3.14/site-packages/sage/rings/finite_rings/finite_field_base.pyx:1515, in sage.rings.finite_rings.finite_field_base.FiniteField.extension()
   1513             pass
   1514 else:
-> 1515     E = Field.extension(self, modulus, name=name, embedding=embedding, latex_name=latex_name, **kwds)
   1516 if map:
   1517     return (E, E.coerce_map_from(self))
TypeError: extension() got an unexpected keyword argument 'check_irreducible'

edit retag flag offensive close merge delete

add a comment

answered 2026-06-05 17:21:57 +0200

dan_fulea
5705 ●5 ●45 ●97

It is possible to solve the issue on the mathematical side.

$u=\sqrt{-1}$ has minimal polynomial over $\Bbb F_p$ equal to $(U^2 + 1)$.

We know $v^2 + u+1$ is zero in $\Bbb F_p[u]$ so let us multiply with the (Galois) conjugate $$0=(v^2+u+1)(v^2-u+1)=(v^2+1)^2-u^2=(v^4+2v^2+1)-(-1)\ .$$ The element $v$ has minimal polynomial $V^4+2V^2+2$ over the base field $\Bbb F_p$.

It remains to let sage make its choice for $w=\pm\sqrt v$, which has minimal polynomial $W^8+2W^4+2$. All you need is (using the default x or explicitly defining it as polynomial ring indeterminate):

sage: p = 0x1280f73ff3476f313824e31d47012a0056e84f8d122131bb3be6c0f1f3975444a48ae43af6e082acd9cd30394f4736daf68367a5513170ee0a578fdf721a4a48ac3edc154e6565912b
sage: K.<w> = GF(p^8, modulus=x^8 + 2*x^4 + 2)
sage: w.minpoly()
x^8 + 2*x^4 + 2
sage: v = -w^2
sage: u = -(v^2 + 1)
sage: u^2
4576545538729420598762745822889397370509838601207708465545582186285824315458656151272834027217178198654229063318759931344008864619718319130560845441720114764111976549023322410
sage: u^2 == -1
True

Then work with $u,v,w\in K$ as usual.

edit flag offensive delete link

add a comment

Tower field extension for cryptography

1 Answer

Your Answer

Question Tools

Stats

Related questions

Tower field extension for cryptography edit

1 Answer

Your Answer

Question Tools

Stats

Related questions

Tower field extension for cryptography