Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields

DOI10.1016/J.JSC.2020.06.007MaRDI QIDQ1994892zbMATH OpenOpenAlexWikidataFDO

Authors Javad Doliskani, Anand Kumar Narayanan, Éric Schost

Publication date 18 February 2021

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.00669

zbMATH Keywords

complex multiplicationDrinfeld moduleselliptic modulesHasse invariantpolynomial factorization

Mathematics Subject Classification ID

Drinfel'd modules; higher-dimensional motives, etc. (11G09) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Abstract: We present a novel randomized algorithm to factor polynomials over a finite field $F_q$ of odd characteristic using rank $2$ Drinfeld modules with complex multiplication. The main idea is to compute a lift of the Hasse invariant (modulo the polynomial $fin{F}_q[x]$ to be factored) with respect to a random Drinfeld module $phi$ with complex multiplication. Factors of $f$ supported on prime ideals with supersingular reduction at $phi$ have vanishing Hasse invariant and can be separated from the rest. Incorporating a Drinfeld module analogue of Deligne's congruence, we devise an algorithm to compute the Hasse invariant lift, which turns out to be the crux of our algorithm. The resulting expected runtime of $n^{3/2+varepsilon}(logq{)}^{1+o(1)}+n^{1+varepsilon}(logq{)}^{2+o(1)}$ to factor polynomials of degree $n$ over $F_q$ matches the fastest previously known algorithm, the Kedlaya-Umans implementation of the Kaltofen-Shoup algorithm.

Recommendations

• Factoring polynomials over finite fields with Drinfeld modules
• Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules
• Polynomial factorisation using Drinfeld modules
• scientific article; zbMATH DE number 1273636
• On a New Factorization Algorithm for Polynomials Over Finite Fields

Cites work

• A New Algorithm for Factoring Polynomials Over Finite Fields
• Computing Frobenius maps and factoring polynomials
• Deligne's congruence and supersingular reduction of Drinfeld modules
• Factoring integers with elliptic curves
• Factoring polynomials over finite fields with Drinfeld modules
• Fast Algorithms for Manipulating Formal Power Series
• Fast arithmetic for the algebraic closure of finite fields
• Fast construction of irreducible polynomials over finite fields
• Fast Library for Number Theory: An Introduction
• Fast polynomial factorization and modular composition
• Fast rectangular matrix multiplication and applications
• Field Arithmetic
• Frobenius distributions of Drinfeld modules over finite fields
• scientific article; zbMATH DE number 1716471 (Why is no real title available?)
• scientific article; zbMATH DE number 4055695 (Why is no real title available?)
• scientific article; zbMATH DE number 3785035 (Why is no real title available?)
• scientific article; zbMATH DE number 25927 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 3265895 (Why is no real title available?)
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Matrix multiplication via arithmetic progressions
• Modern computer algebra
• On fast multiplication of polynomials over arbitrary algebras
• On finite Drinfeld modules
• On singular and supersingular invariants of Drinfeld modules
• On the coefficients of Drinfeld modular forms
• Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules
• Powers of tensors and fast matrix multiplication
• Public key cryptosystems based on Drinfeld modules are insecure
• Some results on computational complexity
• Subquadratic-time factoring of polynomials over finite fields
• The Magma algebra system. I: The user language

Cited in

(6)

• Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules
• Polynomial factorisation using Drinfeld modules
• Factoring polynomials over finite fields with Drinfeld modules
• Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology
• Computing a group action from the class field theory of imaginary hyperelliptic function fields
• Algorithms for computing norms and characteristic polynomials on general Drinfeld modules

Describes a project that uses

Uses Software

• FLINT
• Magma
• NTL

This page was built for publication: Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1994892)