|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Deterministic Polynomial Factoring and Association Schemes | | Manuel Arora
; Gábor Ivanyos
; Marek Karpinski
; Nitin Saxena
; | | Date: |
25 May 2012 | | Abstract: | The problem of finding a nontrivial factor of a polynomial f(x) over a finite
field 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 poly(n^r,log q) time; assuming GRH and that s >
sqrt{n/(2^r)}. Thus, for r = O(1) our algorithm is polynomial time. Further,
for r > loglog 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. | | Source: | arXiv, 1205.5653 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER