CaltechAUTHORS
  A Caltech Library Service

Polynomial factorization over finite fields by computing Euler–Poincaré characteristics of Drinfeld modules

Narayanan, Anand Kumar (2018) Polynomial factorization over finite fields by computing Euler–Poincaré characteristics of Drinfeld modules. Finite Fields and Their Applications, 54 . pp. 335-365. ISSN 1071-5797. http://resolver.caltech.edu/CaltechAUTHORS:20180907-150915770

[img] PDF - Submitted Version
See Usage Policy.

331Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20180907-150915770

Abstract

We propose and rigorously analyze two randomized algorithms to factor univariate polynomials over finite fields using rank 2 Drinfeld modules. The first algorithm estimates the degree of an irreducible factor of a polynomial from Euler–Poincaré characteristics of random Drinfeld modules. Knowledge of a factor degree allows one to rapidly extract all factors of that degree. As a consequence, the problem of factoring polynomials over finite fields in time nearly linear in the degree is reduced to finding Euler–Poincaré characteristics of random Drinfeld modules with high probability. The second algorithm is a random Drinfeld module analogue of Berlekamp's algorithm. During the course of its analysis, we prove a new bound on degree distributions in factorization patterns of polynomials over finite fields in certain short intervals.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1016/j.ffa.2018.08.003DOIArticle
https://arxiv.org/abs/1504.07697arXivDiscussion Paper
Additional Information:© 2018 Elsevier Inc. Received 31 May 2017, Accepted 13 August 2018, Available online 6 September 2018. The author was partially supported by NSF grant CCF 1423544.
Funders:
Funding AgencyGrant Number
NSFCCF-1423544
Subject Keywords:Finite fields; Polyomial factorization; Drinfeld modules
Classification Code:MSC: primary 11T55, 11Y16; secondary 11G20
Record Number:CaltechAUTHORS:20180907-150915770
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20180907-150915770
Official Citation:Anand Kumar Narayanan, Polynomial factorization over finite fields by computing Euler–Poincaré characteristics of Drinfeld modules, Finite Fields and Their Applications, Volume 54, 2018, Pages 335-365, ISSN 1071-5797, https://doi.org/10.1016/j.ffa.2018.08.003. (http://www.sciencedirect.com/science/article/pii/S1071579718300959)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89471
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:08 Sep 2018 03:21
Last Modified:10 Sep 2018 14:59

Repository Staff Only: item control page