Gábor Ivanyos
ABSTRACT
In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects, we call m-schemes, that are generalizations of permutation groups. We design a new generalization of the known conditional deterministic subexponential time polynomial factoring algorithm to get an underlying m-scheme. We then demonstrate how progress in understanding m-schemes relate to improvements in the deterministic complexity of factoring polynomials, 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 constant-smooth number. We use a structural theorem about association schemes on a prime number of points, which Hanaki and Uno (2006) proved by representation theory methods.
- L. Adleman, K. Manders, and G. Miller. On taking roots in finite fields. In Proc. 18th FOCS, pages 175--178, 1977. Google Scholar
Digital Library
- E. Bach, J. von zur Gathen, and H. W. Lenstra, Jr. Factoring polynomials over special finite fields. Finite Fields and Their Applications, 7:5--28, 2001. Google ScholarDigital Library
- E. R. Berlekamp. Factoring polynomials over finite fields. Bell System Technical Journal, 46:1853--1859, 1967.Google ScholarCross Ref
- E. R. Berlekamp. Factoring polynomials over large finite fields. Math. Comp., 24:713--735, 1970.Google ScholarCross Ref
- J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389--410, 1992.Google ScholarCross Ref
- P. J. Cameron. Permutation Groups. LMS Student Text 45. Cambridge University Press, Cambridge, 1999.Google Scholar
- P. Camion. A deterministic algorithm for factorizing polynomials of Fq{x}. Ann. Discr. Math., 17:149--157, 1983.Google Scholar
- D. G. Cantor and H. Zassenhaus. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation, 36(154):587--592, 1981.Google ScholarCross Ref
- Q. Cheng and M. A. Huang. Factoring polynominals over finite fields and stable colorings of tournaments. In ANTS, pages 233--246, 2000. Google ScholarDigital Library
- S. A. Evdokimov. Factorization of a solvable polynomial over finite fields and the Generalized Riemann Hypothesis. Zapiski Nauchnyck Seminarov LOMI, 176:104--117, 1989.Google Scholar
- S. A. Evdokimov. Factorization of polynomials over finite fields in subexponential time under GRH. In Proc. 1st ANTS, pages 209--219. Lecture Notes In Computer Science 877, Springer-Verlag, 1994. Google ScholarDigital Library
- S. Gao. On the deterministic complexity of factoring polynomials. J. of Symbolic Computation, 31(1-2):19--36, 2001. Google ScholarDigital Library
- A. Hanaki and K. Uno. Algebraic structure of association schemes of prime order. J. Algebraic. Combin., 23:189--195, 2006. Google ScholarDigital Library
- M. A. Huang. Generalized Riemann Hypothesis and factoring polynomials over finite fields. J. Algorithms, 12:464--481, 1991. Google ScholarDigital Library
- E. Kaltofen and V. Shoup. Subquadratic-time factoring of polynomials over finite fields. Math. Comp., 67:1179--1197, 1998. Google ScholarDigital Library
- M. Mignotte and C.-P. Schnorr. Calcul d´eterministe des racines d'un polynôme dans un corps fini. Comptes Rendus Académie des Sciences (Paris), 306:467--472, 1988.Google Scholar
- I. Miyamoto. A computation of some multiply homogeneous superschemes from transitive permutation groups. In ISSAC '07: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pages 293--298, 2007. Google ScholarDigital Library
- R. T. Moenck. On the efficiency of algorithms for polynomial factoring. Math. Comp., 31:235--250, 1977.Google ScholarCross Ref
- M. O. Rabin. Probabilistic algorithms in finite fields. SIAM J. Comput, 9:273--280, 1980.Google ScholarDigital Library
- L. Rónyai. Factoring polynomials over finite fields. Journal of Algorithms, 9:391--400, 1988. Google ScholarDigital Library
- L. Rónyai. Factoring polynomials modulo special primes. Combinatorica, 9:199--206, 1989.Google ScholarCross Ref
- L. Rónyai. Galois groups and factoring polynomials over finite fields. SIAM J. on Discrete Mathematics, 5:345--365, 1992. Google ScholarDigital Library
- C. Saha. Factoring polynomials over finite fields using balance test. In STACS, pages 609--620, 2008.Google Scholar
- A. Seress. The minimal base size of primitive solvable permutation groups. J. London Math. Soc., 53:243--255, 1996.Google ScholarCross Ref
- J. D. H. Smith. Association schemes, superschemes, and relations invariant under permutation groups. European J. Combin., 15(3):285--291, 1994. Google ScholarDigital Library
- J. von zur Gathen. Factoring polynomials and primitive elements for special primes. Theoretical Computer Science, 52:77--89, 1987. Google ScholarDigital Library
- J. von zur Gathen and V. Shoup. Computing Frobenius maps and factoring polynomials. Comput. Complexity, 2:187--224, 1992.Google ScholarCross Ref
- J. Wojdy lo. An inextensible association scheme associated with a 4-regular graph. Graphs and Combinatorics, 17(1):185--192, 2001.Google ScholarCross Ref
- H. Zassenhaus. On Hensel factorization, I. J. Number Theory, 1:291--311, 1969.Google ScholarCross Ref
- P.-H. Zieschang. Theory of Association Schemes. Springer, Berlin, 2005.Google Scholar
Index Terms
- Schemes for deterministic polynomial factoring
Recommendations
New Algorithms for Polynomial Square-Free Decomposition over the Integers
Previously-known algorithms for polynomial square-free decomposition rely on greatest common divisor (gcd) computations over the same coefficient domain where the decomposition is to be performed. In particular, gcd of the given polynomial and its first ...
Factoring polynomials over Z4 and over certain Galois rings
It is known that univariate polynomials over finite local rings factor uniquely into primary pairwise coprime factors. Primary polynomials are not necessarily irreducible. Here we describe a factorisation into irreducible factors for primary polynomials ...
Comments