Schemes for Deterministic Polynomial Factoring

Simple item page
dc.creatorIvanyos, Gábor
dc.creatorKarpinski, Marek
dc.creatorSaxena, Nitin
dc.date2008-04-11
dc.date.accessioned2026-07-07T09:32:06Z
dc.date.available2026-07-07T09:32:06Z
dc.descriptionIn 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.
dc.description14 pages, preliminary version
dc.identifierhttps://arxiv.org/abs/0804.1974
dc.identifierhttp://arxiv.org/abs/0804.1974
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/158693
dc.subjectComputational Complexity
dc.subjectSymbolic Computation
dc.titleSchemes for Deterministic Polynomial Factoring
dc.typetext

Files

Collections

arXiv