Using zeta functions to factor polynomials over finite fields

DOI10.1090/CONM/722/14528MaRDI QIDQ5236842zbMATH OpenOpenAlexFDO

Authors Bjorn Poonen

Publication date 16 October 2019

Published in Arithmetic Geometry: Computation and Applications (Search for Journal in Brave)

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

zbMATH Keywords

abelian varietyfactoring polynomialsfinite fieldszeta function

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Zeta functions and related questions in algebraic geometry (e.g., Birch-Swinnerton-Dyer conjecture) (14G10) Finite ground fields in algebraic geometry (14G15) Arithmetic ground fields for abelian varieties (14K15)

Abstract: In 2005, Kayal suggested that Schoof's algorithm for counting points on elliptic curves over finite fields might yield an approach to factor polynomials over finite fields in deterministic polynomial time. We present an exposition of his idea and then explain details of a generalization involving Pila's algorithm for abelian varieties.

Recommendations

• Factoring polynomials over finite fields with Drinfeld modules
• scientific article; zbMATH DE number 1222356
• Factoring polynomials over arbitrary finite fields
• Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules
• Deterministic distinct-degree factorization of polynomials over finite fields

Cites work

• Calculability of étale cohomology modulo
• Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
• Factoring polynomials over finite fields: A survey
• Factoring Polynomials Over Large Finite Fields
• Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
• scientific article; zbMATH DE number 4152523 (Why is no real title available?)
• scientific article; zbMATH DE number 3803550 (Why is no real title available?)
• Maps between curves and arithmetic obstructions
• Real polynomials with all roots on the unit circle and abelian varieties over finite fields

Cited in

(7)

• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• Impact of group theory in cryptosystem
• Maps between curves and arithmetic obstructions
• Counting points on curves and Abelian varieties over finite fields
• Doubly isogenous genus-2 curves with 𝐷₄-action
• A complexity chasm for solving univariate sparse polynomial equations over p-adic fields
• Doubly isogenous curves of genus two with a rational action of D₆

This page was built for publication: Using zeta functions to factor polynomials over finite fields

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