Deterministic root finding in finite fields
Pages 87 - 89
Abstract
Finding roots of polynomials with coefficients in a finite field is a special instance of the polynomial factorization problem. The most well known algorithm for factoring and root-finding is the Cantor-Zassenhaus algorithm. It is a Las Vegas algorithm with running time polynomial in both the polynomial degree and the field size. Its running time is quasi-optimal for the special case of root-finding.
No deterministic polynomial time algorithm for these problems is known in general, however several deterministic algorithms are known for special instances, most notably when the characteristic of the finite field is small.
The goal of this poster is to review the best deterministic algorithms for root-finding, in a systematic way. We present, in a unified way, four algorithms:
• Berlekamp's Trace Algorithm [2] (BTA),
• Moenk's Subgroup Refinement Method [7] (SRM),
• Menezes, van Oorschot and Vanstone's Affine Refinement Method [5, 10] (ARM), and
• Petit's Successive Resultants Algorithm [8] (SRA).
It is the first time that these algorithms are presented together in a comprehensive way, and that they are rigorously analysed, implemented and compared to each other.
In doing so, we obtain several new results:
• We significantly improve the complexity ARM, matching that of BTA and SRA.
• We highlight a profound duality relationship between ARM and SRA.
• We show how to combine ARM with SRM to obtain a new algorithm, which always performs better, and of which ARM and SRM are special instances. The new algorithm considerably extends the range of finite fields for which deterministic polynomial time root-finding is possible.
• We present several practical and asymptotic improvements to special instances of the algorithms.
Part of these results were submitted in response to the call for papers of ISSAC '15, but were rejected. This poster corrects some minor imperfections, improves the asymptotic complexities of some algorithms, and presents a new algorithm not previously known.
References
[1]
E. Berlekamp. Algebraic Coding Theory. Aegan Park Press, 1984.
[2]
E. R. Berlekamp. Factoring Polynomials over Large Finite Fields. Math. Comp., 24:713--735, 1970.
[3]
D. G. Cantor and H. Zassenhaus. A New Algorithm for Factoring Polynomials over Finite Fields. Mathematics of Computation, pages 587--592, 1981.
[4]
R. McEliece. A Public-key Cryptosystem Based on the Aalgebraic Cdoing Theory. Technical Report DSN 42-44, JPL, Pasadena, 1978.
[5]
A. Menezes, P. C. van Oorschot, and S. A. Vanstone. Some Computational Aspects of Root Finding in GF(qm). In P. M. Gianni, editor, ISSAC, volume 358 of Lecture Notes in Computer Science, pages 259--270. Springer, 1988.
[6]
A. J. Menezes, P. C. Van Oorschot, and S. Vanstone. Subgroup Refinement Algorithms for Roots Finding in GF(q)*. SIAM J. Comput., 21(2):228--239, apr 1992.
[7]
R. T. Moenck. On the Efficiency of Algorithms for Polynomial factoring. 31(137):235--250, Jan. 1977.
[8]
C. Petit. Finding Roots in GF(pn) with the Successive Resultant Algorithm. LMS Journal of Computation and Mathematics, 8 2014. (to appear).
[9]
V. Shoup. A Fast Deterministic Algorithm for Factoring Polynomials over Finite Fields of Small Characteristic. In S. M. Watt, editor, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC '91, Bonn, Germany, July 15-17, 1991, pages 14--21. ACM, 1991.
[10]
P. C. van Oorschot and S. A. Vanstone. A Geometric Approach to Root Finding in GF(qm). IEEE Transactions on Information Theory, 35(2):444--453, 1989.
Recommendations
Irreducibility and Deterministic r-th Root Finding over Finite Fields
ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic ComputationConstructing r-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree re (where r is a prime) over a given finite field Fq of characteristic p (equivalently, ...
Real root-finding
SNC '07: Proceedings of the 2007 international workshop on Symbolic-numeric computationIn this paper we seek all real roots of a polynomial with real coefficients and real and nonreal roots. Somewhat paradoxically, one of the most effective solutions is by approximating these real roots semi-numerically together with all nonreal roots. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2015 Authors.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 November 2015
Published in SIGSAM-CCA Volume 49, Issue 3
Check for updates
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 134Total Downloads
- Downloads (Last 12 months)8
- Downloads (Last 6 weeks)3
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in