Schemes for Deterministic Polynomial Factoring

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditional deterministic subexponential time polynomial factoring algorithm for finite fields to get an underlying m-scheme. We demonstrate how the properties of m-schemes relate to improvements in the deterministic complexity of factoring polynomials over finite fields assuming the generalized Riemann Hypothesis (GRH). In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n-1) is a smooth number.
14 pages, preliminary version

Keywords

Computational Complexity, Symbolic Computation

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/158693

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0804.1974
 http://arxiv.org/abs/0804.1974

Collections

arXiv