Deterministic polynomial factoring and association schemes. Issue Volume 17:Issue A(2014) (April 2014)
- Record Type:
- Journal Article
- Title:
- Deterministic polynomial factoring and association schemes. Issue Volume 17:Issue A(2014) (April 2014)
- Main Title:
- Deterministic polynomial factoring and association schemes
- Authors:
- Arora, Manuel
Ivanyos, Gábor
Karpinski, Marek
Saxena, Nitin - Abstract:
- Abstract: The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field ${\mathbb{F}}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the art by focusing on prime degree polynomials; let $n$ be the degree. If $(n-1)$ has a 'large' $r$ -smooth divisor $s$, then we find a nontrivial factor of $f(x)$ in deterministic $\mbox{poly}(n^r, \log q)$ time, assuming GRH and that $s=\Omega (\sqrt{n/2^r})$ . Thus, for $r=O(1)$ our algorithm is polynomial time. Further, for $r=\Omega (\log \log n)$ there are infinitely many prime degrees $n$ for which our algorithm is applicable and better than the best known, assuming GRH. Our methods build on the algebraic-combinatorial framework of $m$ -schemes initiated by Ivanyos, Karpinski and Saxena (ISSAC 2009). We show that the $m$ -scheme on $n$ points, implicitly appearing in our factoring algorithm, has an exceptional structure, leading us to the improved time complexity. Our structure theorem proves the existence of small intersection numbers in any association scheme that has many relations, and roughly equal valencies and indistinguishing numbers.
- Is Part Of:
- LMS journal of computation and mathematics. Volume 17:Issue A(2014)
- Journal:
- LMS journal of computation and mathematics
- Issue:
- Volume 17:Issue A(2014)
- Issue Display:
- Volume 17, Issue 1 (2014)
- Year:
- 2014
- Volume:
- 17
- Issue:
- 1
- Issue Sort Value:
- 2014-0017-0001-0000
- Page Start:
- 123
- Page End:
- 140
- Publication Date:
- 2014-04
- Subjects:
- 12Y05, -- 05E30 (primary), -- 05E10, -- 03D15, -- 68W30 (secondary)
- Journal URLs:
- https://www.cambridge.org/core/journals/lms-journal-of-computation-and-mathematics ↗
- DOI:
- 10.1112/S1461157013000296 ↗
- Languages:
- English
- ISSNs:
- 1461-1570
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library HMNTS - ELD Digital store
- Ingest File:
- 5232.xml