More Web Proxy on the site http://driver.im/

research-article

Schemes for deterministic polynomial factoring

Authors:

Gábor Ivanyos,

Marek Karpinski,

Nitin SaxenaAuthors Info & Claims

ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation

Pages 191 - 198

https://doi.org/10.1145/1576702.1576730

Published: 28 July 2009 Publication History

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.

References

[1]

L. Adleman, K. Manders, and G. Miller. On taking roots in finite fields. In Proc. 18th FOCS, pages 175--178, 1977.

Digital Library

[2]

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.

Digital Library

[3]

E. R. Berlekamp. Factoring polynomials over finite fields. Bell System Technical Journal, 46:1853--1859, 1967.

[4]

E. R. Berlekamp. Factoring polynomials over large finite fields. Math. Comp., 24:713--735, 1970.

[5]

J. Cai, M. F&#252;rer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389--410, 1992.

[6]

P. J. Cameron. Permutation Groups. LMS Student Text 45. Cambridge University Press, Cambridge, 1999.

[7]

P. Camion. A deterministic algorithm for factorizing polynomials of F_q{x}. Ann. Discr. Math., 17:149--157, 1983.

[8]

D. G. Cantor and H. Zassenhaus. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation, 36(154):587--592, 1981.

[9]

Q. Cheng and M. A. Huang. Factoring polynominals over finite fields and stable colorings of tournaments. In ANTS, pages 233--246, 2000.

Digital Library

[10]

S. A. Evdokimov. Factorization of a solvable polynomial over finite fields and the Generalized Riemann Hypothesis. Zapiski Nauchnyck Seminarov LOMI, 176:104--117, 1989.

[11]

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.

Digital Library

[12]

S. Gao. On the deterministic complexity of factoring polynomials. J. of Symbolic Computation, 31(1-2):19--36, 2001.

Digital Library

[13]

A. Hanaki and K. Uno. Algebraic structure of association schemes of prime order. J. Algebraic. Combin., 23:189--195, 2006.

Digital Library

[14]

M. A. Huang. Generalized Riemann Hypothesis and factoring polynomials over finite fields. J. Algorithms, 12:464--481, 1991.

Digital Library

[15]

E. Kaltofen and V. Shoup. Subquadratic-time factoring of polynomials over finite fields. Math. Comp., 67:1179--1197, 1998.

Digital Library

[16]

M. Mignotte and C.-P. Schnorr. Calcul d&#180;eterministe des racines d'un polyn&#244;me dans un corps fini. Comptes Rendus Acad&#233;mie des Sciences (Paris), 306:467--472, 1988.

[17]

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.

Digital Library

[18]

R. T. Moenck. On the efficiency of algorithms for polynomial factoring. Math. Comp., 31:235--250, 1977.

[19]

M. O. Rabin. Probabilistic algorithms in finite fields. SIAM J. Comput, 9:273--280, 1980.

Digital Library

[20]

L. R&#243;nyai. Factoring polynomials over finite fields. Journal of Algorithms, 9:391--400, 1988.

Digital Library

[21]

L. R&#243;nyai. Factoring polynomials modulo special primes. Combinatorica, 9:199--206, 1989.

[22]

L. R&#243;nyai. Galois groups and factoring polynomials over finite fields. SIAM J. on Discrete Mathematics, 5:345--365, 1992.

Digital Library

[23]

C. Saha. Factoring polynomials over finite fields using balance test. In STACS, pages 609--620, 2008.

[24]

A. Seress. The minimal base size of primitive solvable permutation groups. J. London Math. Soc., 53:243--255, 1996.

[25]

J. D. H. Smith. Association schemes, superschemes, and relations invariant under permutation groups. European J. Combin., 15(3):285--291, 1994.

Digital Library

[26]

J. von zur Gathen. Factoring polynomials and primitive elements for special primes. Theoretical Computer Science, 52:77--89, 1987.

Digital Library

[27]

J. von zur Gathen and V. Shoup. Computing Frobenius maps and factoring polynomials. Comput. Complexity, 2:187--224, 1992.

[28]

J. Wojdy lo. An inextensible association scheme associated with a 4-regular graph. Graphs and Combinatorics, 17(1):185--192, 2001.

[29]

H. Zassenhaus. On Hensel factorization, I. J. Number Theory, 1:291--311, 1969.

[30]

P.-H. Zieschang. Theory of Association Schemes. Springer, Berlin, 2005.

Cited By

Bhargava VIvanyos GMittal RSaxena NYap CEl Din M(2017)Irreducibility and Deterministic r-th Root Finding over Finite FieldsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087620(37-44)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087620
Reichard S(2015)Strongly regular graphs with the $$7$$7-vertex conditionJournal of Algebraic Combinatorics: An International Journal10.1007/s10801-014-0554-141:3(817-842)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s10801-014-0554-1
Arora MIvanyos GKarpinski MSaxena N(2014)Deterministic polynomial factoring and association schemesLMS Journal of Computation and Mathematics10.1112/S146115701300029617:1(123-140)Online publication date: 1-Apr-2014
https://doi.org/10.1112/S1461157013000296
Show More Cited By

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 ...
Deterministic polynomial factoring over finite fields: A uniform approach via P-schemes
Abstract
We introduce a family of combinatorial objects called P -schemes, where P is a collection of subgroups of a finite group G. A P-scheme is a collection of partitions of right coset spaces H \ G, indexed by H ∈ P, that ...
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation

July 2009

402 pages

ISBN:9781605586090

DOI:10.1145/1576702

General Chairs:
Jeremy Johnson
Drexel University, USA
,
Hyungju Park
Korea Institute for Advanced Study, Korea
,
Program Chair:
Erich Kaltofen
North Carolina State University, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '09

Sponsor:

ISSAC '09: International Symposium on Symbolic and Algebraic Computation

July 28 - 31, 2009

Seoul, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bhargava VIvanyos GMittal RSaxena NYap CEl Din M(2017)Irreducibility and Deterministic r-th Root Finding over Finite FieldsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087620(37-44)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087620
Reichard S(2015)Strongly regular graphs with the $$7$$7-vertex conditionJournal of Algebraic Combinatorics: An International Journal10.1007/s10801-014-0554-141:3(817-842)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s10801-014-0554-1
Arora MIvanyos GKarpinski MSaxena N(2014)Deterministic polynomial factoring and association schemesLMS Journal of Computation and Mathematics10.1112/S146115701300029617:1(123-140)Online publication date: 1-Apr-2014
https://doi.org/10.1112/S1461157013000296
Mullen GPanario D(2013)CryptographyHandbook of Finite Fields10.1201/b15006-22(777-860)Online publication date: 17-Jun-2013
https://doi.org/10.1201/b15006-22

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten