Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-13T17:49:57.512Z Has data issue: false hasContentIssue false
  • English
  • Français

Deterministic polynomial factoring and association schemes

Part of: Algebraic combinatorics Computability and recursion theory Algorithms - Computer Science Computational aspects of field theory and polynomials

Published online by Cambridge University Press:  01 April 2014

Manuel Arora ,
Gábor Ivanyos ,
Marek Karpinski  and
Nitin Saxena
Manuel Arora
Affiliation:
Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA 91125, USA email arora@caltech.edu
Gábor Ivanyos
Affiliation:
Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Kende u. 13-17, H-1111 Budapest, Hungary email Gabor.Ivanyos@sztaki.mta.hu
Marek Karpinski
Affiliation:
Department of Computer Science, University of Bonn, 53117 Bonn, Germany email marek@cs.uni-bonn.de
Nitin Saxena
Affiliation:
Department of Computer Science and Engineering, IIT Kanpur, Kanpur 208016, India email nitin@cse.iitk.ac.in

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

MSC classification

Secondary: 12Y05: Computational aspects of field theory and polynomials 05E30: Association schemes, strongly regular graphs 05E10: Combinatorial aspects of representation theory 03D15: Complexity of computation (including implicit computational complexity) 68W30: Symbolic computation and algebraic computation
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 17 , Issue 1 , 2014 , pp. 123 - 140
Copyright
© The Author(s) 2014 

References

Adleman, L., Manders, K. and Miller, G., ‘On taking roots in finite fields’, Proceedings of the 18th FOCS (1977) 175–178.Google Scholar
Ankeny, N. C., ‘The least quadratic non residue’, Ann. of Math. (2) 55 (1952) 65–72.Google Scholar
Bach, E. and Sorenson, J., ‘Explicit bounds for primes in residue classes’, Math. Comput. 65 (1996) 1717–1735.Google Scholar
Bach, E., von zur Gathen, J. and Lenstra, H. W. Jr, ‘Factoring polynomials over special finite fields’, Finite Fields Appl. 7 (2001) 5–28.Google Scholar
Bannai, E. and Ito, T., Algebraic combinatorics I: association schemes (Benjamin-Cummings, 1984).Google Scholar
Berlekamp, E. R., ‘Factoring polynomials over finite fields’, Bell Syst. Tech. J. 46 (1967) 1853–1859.Google Scholar
Berlekamp, E. R., ‘Factoring polynomials over large finite fields’, Math. Comp. 24 (1970) 713–735.Google Scholar
Borwein, P., Choi, S., Rooney, B. and Weirathmueller, A. (eds), The Riemann hypothesis: a resource for the afficionado and virtuoso alike , CMS Books in Mathematics (Springer, 2008).Google Scholar
Bose, R. C. and Mesner, D. M., ‘On linear associative algebras corresponding to association schemes of partially balanced designs’, Ann. Math. Statist. 30 (1959) 21–38.Google Scholar
Bose, R. C. and Nair, K. R., ‘Partially balanced incomplete block designs’, Sankhyā 4 (1939) 337–372.Google Scholar
Camion, P., ‘A deterministic algorithm for factorizing polynomials of $\mathbb{F}_q[x]$ ’, Ann. Discrete Math. 17 (1983) 149–157.Google Scholar
Cantor, D. G. and Zassenhaus, H., ‘A new algorithm for factoring polynomials over finite fields’, Math. Comput. 36 (1981) 587–592.Google Scholar
Cheng, Q. and Huang, M. A., ‘Factoring polynomials over finite fields and stable colorings of tournaments’, Proceedings of the 4th ANTS (2000) 233–246.Google Scholar
Chowla, S., The Riemann hypothesis and Hilbert’s tenth problem (Gordon and Breach, 1965).Google Scholar
Cohn, H. and Umans, C., ‘Fast matrix multiplication using coherent configurations’, Preprint, 2012,arXiv:1207.6528.Google Scholar
Delsarte, P., ‘An algebraic approach to the association schemes of coding theory’, Technical Report, Philips Research Reports, Supplement No. 10, 1973.Google Scholar
Evdokimov, S. A., ‘Factorization of a solvable polynomial over finite fields and the generalized Riemann hypothesis’, Zap. Nauchn. Sem. LOMI 176 (1989) 104–117.Google Scholar
Evdokimov, S. A., ‘Factorization of polynomials over finite fields in subexponential time under GRH’, Proc. 1st ANTS , Lecture Notes in Computer Science 877 (Springer, 1994) 209–219.Google Scholar
Evdokimov, S. A. and Ponomarenko, I. N., ‘Separability number and Schurity number of coherent configurations’, Electron. J. Combin. 7 (2000).Google Scholar
Evdokimov, S. A. and Ponomarenko, I. N., ‘Characterization of cyclotomic schemes and normal Schur rings over a cyclic group’, St. Petersburg Math. J. 14 (2003) 189–221.Google Scholar
Evdokimov, S. A. and Ponomarenko, I. N., ‘Permutation group approach to association schemes’, European J. Combin. 30 (2009) 1456–1476.Google Scholar
Ford, K., ‘The distribution of integers with a divisor in a given interval’, Ann. of Math. (2) 168 (2008) 367–433.CrossRefGoogle Scholar
Gao, S., ‘On the deterministic complexity of factoring polynomials’, J. Symbolic Comput. 31 (2001) 19–36.Google Scholar
Goldbach, R. W. and Claasen, H. L., ‘Cyclotomic schemes over finite rings’, Indag. Math. 3 (1992) 301–312.Google Scholar
Hanaki, A. and Uno, K., ‘Algebraic structure of association schemes of prime order’, J. Algebraic Combin. 23 (2006) 189–195.Google Scholar
Heath-Brown, D. R., ‘Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression’, Proc. Lond. Math. Soc. 64 (1992) 265–338.Google Scholar
Higman, D. G., ‘Coherent configurations I’, Rend. Semin. Mat. Univ. Padova 44 (1970) 1–25.Google Scholar
Huang, M. A., ‘Factorization of polynomials over finite fields and factorization of primes in algebraic number fields’, Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC) (1984) 175–182.Google Scholar
Huang, M. A., ‘Generalized Riemann hypothesis and factoring polynomials over finite fields’, J. Algorithms 12 (1991) 464–481.Google Scholar
Ivanyos, G., Karpinski, M., Rónyai, L. and Saxena, N., ‘Trading GRH for algebra: algorithms for factoring polynomials and related structures’, Math. Comput. 81 (2012) 493–531.Google Scholar
Ivanyos, G., Karpinski, M. and Saxena, N., ‘Schemes for deterministic polynomial factoring’, 34th International Symposium on Symbolic and Algebraic Computation, 2009, 191–198.Google Scholar
Kaltofen, E. and Shoup, V., ‘Subquadratic-time factoring of polynomials over finite fields’, Math. Comput. 67 (1998) 1179–1197.Google Scholar
Kanold, H. J., ‘Elementare Betrachtungen zur Primzahltheorie’, Arch. Math. 14 (1963) 147–151.Google Scholar
Kanold, H. J., ‘Über Primzahlen in Arithmetischen Folgen’, Math. Ann. 156 (1964) 393–395.CrossRefGoogle Scholar
Kedlaya, K. S. and Umans, C., ‘Fast polynomial factorization and modular composition’, SIAM J. Comput. 40 (2011) 1767–1802.Google Scholar
Krasner, M., ‘Une généralisation de la notion de corps’, J. Math. Pures Appl. 17 (1938) 367–385.Google Scholar
Linnik, Y. V., ‘On the least prime in an arithmetic progression I. The basic theorem’, Rec. Math. (Mat. Sbornik ) N.S. 15 (1944) 139–178.Google Scholar
Mignotte, M. and Schnorr, C. P., ‘Calcul déterministe des racines d’un polynôme dans un corps fini’, C. R. Math. Acad. Sci. 306 (1988) 467–472.Google Scholar
Moenck, R. T., ‘On the efficiency of algorithms for polynomial factoring’, Math. Comp. 31 (1977) 235–250.Google Scholar
Muzychuk, M. and Ponomarenko, I., ‘On pseudocyclic association schemes’, ARS Math. Contemp. 5 (2012) 1–25.Google Scholar
Rabin, M. O., ‘Probabilistic algorithms in finite fields’, SIAM J. Comput. 9 (1980) 273–280.Google Scholar
Riemann, B., ‘Über die Anzahl der Primzahlen unter einer gegebenen Grösse’, Monatsberichte Berliner Akad., 1859.Google Scholar
Rónyai, L., ‘Factoring polynomials over finite fields’, J. Algorithms 9 (1988) 391–400.CrossRefGoogle Scholar
Rónyai, L., ‘Factoring polynomials modulo special primes’, Combinatorica 9 (1989) 199–206.CrossRefGoogle Scholar
Rónyai, L., ‘Galois groups and factoring polynomials over finite fields’, SIAM J. Discrete Math. 5 (1992) 345–365.Google Scholar
Saha, C., ‘Factoring polynomials over finite fields using balance test’, 25th STACS (2008) 609–620.Google Scholar
Schinzel, A. and Sierpinski, W., ‘Sur certaines hypothèses concernant les nombres premiers’, Acta Arith. 4 (1958) 345–365.Google Scholar
Smith, J. D. H., ‘Association schemes, superschemes, and relations invariant under permutation groups’, European J. Combin. 15 (1994) 285–291.Google Scholar
Voight, J., ‘Curves over finite fields with many points: an introduction’, Computational aspects of algebraic curves, Lecture Notes Series on Computing 13 (ed. Shaska Tanush; World Scientific, Hackensack, NJ, 2005) 124–144.Google Scholar
von zur Gathen, J., ‘Factoring polynomials and primitive elements for special primes’, Theoret. Comput. Sci. 52 (1987) 77–89.Google Scholar
von zur Gathen, J. and Shoup, V., ‘Computing Frobenius maps and factoring polynomials’, Comput. Complexity 2 (1992) 187–224.CrossRefGoogle Scholar
Weil, A., Courbes Algébriques et Variétés Abelienne (Hermann, 1971).Google Scholar
Weisfeiler, Y. B. and Lehman, A. A., ‘Reduction of a graph to a canonical form and an algebra which appears in this process (Russian)’, Sci.-Technol. Investig. 9 (1968) 12–16.Google Scholar
Wojdyło, J., ‘Relation algebras and $t$ -vertex condition graphs’, European J. Combin. 19 (1998) 981–986.Google Scholar
Wojdyło, J., ‘An inextensible association scheme associated with a 4-regular graph’, Graphs Combin. 1 (2001) 185–192.Google Scholar
Wojdyło, J., ‘Presuperschemes and colored directed graphs’, JCMCC 38 (2001) 45–54.Google Scholar
Xylouris, T., ‘Über die Nullstellen der Dirichletschen L-Funktionen und die Kleinste Primzahl in einer Arithmetischen Progression’, PhD Thesis, Mathematisch-Naturwissenschaftliche Fakultät der Universität Bonn, 2011.Google Scholar
Zieschang, P.-H., Theory of association schemes (Springer, 2005).Google Scholar