<https://github.com/defeo/towers?tab=readme-ov-fil...
# repolling
a
Unique Title: "Quasi-Linear Algorithms for Lifting and Pushing in ℓ-Adic Field Towers via Rational Function Composition" Unique Abstract: We present quasi-linear-time algorithms for constructing and computing in ℓ-adic towers of finite fields, addressing the inefficiency of traditional linear-algebraic embedding methods in computer algebra systems. Our approach leverages specially tailored families of irreducible polynomials derived from cyclotomic structures and algebraic-group fibers, enabling fast change-of-basis operations between univariate and bivariate representations—termed lift and _push_—through efficient composition and decomposition of rational functions. For towers constructed via Pell conics, tori, or elliptic curve isogenies, we achieve O(M(ℓi)log⁡(ℓi))_O_(M(ℓ_i_)log(ℓ_i_))field operations per level i_i_, where M(n)M(n) is polynomial multiplication time. We provide a Sage implementation demonstrating significant performance gains over Magma in tower creation, while maintaining practical lift/push throughput. Our results establish a foundation for scalable, embedding-aware finite field arithmetic with applications in cryptography, point counting, and symbolic computation.