Polynomial factorization over finite fields by computing Euler–Poincaré characteristics of Drinfeld modules
- Creators
- Narayanan, Anand Kumar
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.
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.Attached Files
Submitted - 1504.07697.pdf
Files
Name | Size | Download all |
---|---|---|
md5:ea03f5b7cc3a86dec58211a6e494d806
|
339.6 kB | Preview Download |
Additional details
- Eprint ID
- 89471
- Resolver ID
- CaltechAUTHORS:20180907-150915770
- CCF-1423544
- NSF
- Created
-
2018-09-08Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field