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

article

Deterministic root finding over finite fields using Graeffe transforms

Authors:

Grégoire LecerfAuthors Info & Claims

Applicable Algebra in Engineering, Communication and Computing, Volume 27, Issue 3

Pages 237 - 257

https://doi.org/10.1007/s00200-015-0280-5

Published: 01 June 2016 Publication History

Abstract

We design new deterministic algorithms, based on Graeffe transforms, to compute all the roots of a polynomial which splits over a finite field $$\mathbb {F}_q$$Fq. Our algorithms were designed to be particularly efficient in the case when the cardinality $$q - 1$$q-1 of the multiplicative group of $$\mathbb {F}_q$$Fq is smooth. Such fields are often used in practice because they support fast discrete Fourier transforms. We also present a new nearly optimal algorithm for computing characteristic polynomials of multiplication endomorphisms in finite field extensions. This algorithm allows for the efficient computation of Graeffe transforms of arbitrary orders.

References

[1]

Allem, L.E., Gao, S., Trevisan, V.: Extracting sparse factors from multivariate integral polynomials. J. Symb. Comput. 52, 3---16 (2013)

Digital Library

[2]

Arora, M., Ivanyos, G., Karpinski, M., Saxena, N.: Deterministic polynomial factoring and association schemes. LMS J. Comput. Math. 17(1), 123---140 (2014)

[3]

Bach, E.: Comments on search procedures for primitive roots. Math. Comput. 66, 1719---1727 (1997)

Digital Library

[4]

Berlekamp, E.R.: Factoring polynomials over finite fields. Bell Syst. Tech. J. 46, 1853---1859 (1967)

[5]

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

[6]

Bostan, A., Gonzales-Vega, L., Perdry, H., Schost, É.: Complexity issues on Newton sums of polynomials (2005). Distributed in the digital proceedings of MEGA'05

[7]

Bostan, A., Flajolet, P., Salvy, B., Schost, É.: Fast computation of special resultants. J. Symb. Comput. 41(1), 1---29 (2006)

Digital Library

[8]

Bostan, A., Gaudry, P., Schost, É.: Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator. SIAM J. Comput. 36(6), 1777---1806 (2007)

Digital Library

[9]

Bostan, A., Schost, É.: Polynomial evaluation and interpolation on special sets of points. J. Complex. 21(4), 420---446 (2005)

Digital Library

[10]

Camion, P.: A deterministic algorithm for factorizing polynomials of $${ F}_q{X}$$Fq{X}. In: Combinatorial mathematics (Marseille-Luminy, 1981), North-Holland Math. Stud., vol. 75, pp. 149---157. North-Holland, Amsterdam (1983)

[11]

Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inform. 28(7), 693---701 (1991)

Digital Library

[12]

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

[13]

Caruso, X., Roe, D., Vaccon, T.: Tracking $$p$$p-adic precision. LMS J. Comput. Math. 17, 274---294 (2014). Special Issue A, Algorithmic Number Theory Symposium XI

[14]

Costa, E., Harvey, D.: Faster deterministic integer factorization. Math. Comput. 83(285), 339---345 (2014)

[15]

Evdokimov, S.: Factorization of polynomials over finite fields in subexponential time under GRH. In: Algorithmic Number Theory (Ithaca, NY, 1994), Lecture Notes in Comput. Sci., vol. 877, pp. 209---219. Springer, Berlin (1994)

Digital Library

[16]

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

Digital Library

[17]

Giusti, M., Lecerf, G., Salvy, B.: A Gröbner free alternative for polynomial system solving. J. Complex. 17(1), 154---211 (2001)

Digital Library

[18]

Grenet, B., van der Hoeven, J., Lecerf, G.: Randomized root finding over finite FFT-fields using tangent Graeffe transforms. In: Robertz, D. (ed.) ISSAC '15: Proceedings of the 2015 International Symposium on Symbolic and Algebraic Computation, pp. 197---204. ACM Press (2015)

Digital Library

[19]

Harvey, D., van der Hoeven, J., Lecerf, G.: Even faster integer multiplication (2014). arXiv:1407.3360

[20]

Harvey, D., van der Hoeven, J., Lecerf, G.: Faster polynomial multiplication over finite fields (2014). arXiv:1407.3361

[21]

Huang, M.D.A.: Generalized Riemann hypothesis and factoring polynomials over finite fields. J. Algorithms 12(3), 464---481 (1991)

Digital Library

[22]

Kaltofen, E.: Polynomial factorization: a success story. In: Hong, H. (ed.) ISSAC '03: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, pp. 3---4. ACM Press (2003)

Digital Library

[23]

Kedlaya, K.S., Umans, C.: Fast modular composition in any characteristic. In: Broder, A.Z., et al. (eds.) 49th Annual IEEE Symposium on Foundations of Computer Science 2008 (FOCS '08), pp. 146---155. IEEE (2008)

Digital Library

[24]

Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767---1802 (2011)

Digital Library

[25]

Kronecker, L.: Grundzüge einer arithmetischen theorie der algebraischen Grössen. J. Reine Angew. Math. 92, 1---122 (1882)

[26]

Lecerf, G.: Fast separable factorization and applications. Appl. Algebra Eng. Commun. Comput. 19(2), 135---160 (2008)

[27]

Malajovich, G., Zubelli, J.P.: Tangent graeffe iteration. Numer. Math. 89(4), 749---782 (2001)

[28]

Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Subgroup refinement algorithms for root finding in $$\text{ GF }(q)$$GF(q). SIAM J. Comput. 21(2), 228---239 (1992)

Digital Library

[29]

Mignotte, M., Schnorr, C.: Calcul déterministe des racines d'un polynôme dans un corps fini. C. R. Acad. Sci. Paris Sér. I Math 306(12), 467---472 (1988)

[30]

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

[31]

Mullen, G.L., Panario, D.: Handbook of Finite Fields. Discrete Mathematics and Its Applications. Chapman and Hall/CRC (2013)

Digital Library

[32]

Pan, V.: Solving a polynomial equation: some history and recent progress. SIAM Rev. 39(2), 187---220 (1997)

Digital Library

[33]

Pan, V.: New techniques for the computation of linear recurrence coefficients. Finite Fields Appl. 6, 93---118 (2000)

Digital Library

[34]

Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over GF$$(p)$$(p) and its cryptographic significance (corresp.). IEEE Trans. Inf. Theory 24(1), 106---110 (1978)

Digital Library

[35]

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

[36]

Rónyai, L.: Factoring polynomials modulo special primes. Combinatorica 9(2), 199---206 (1989)

[37]

Rónyai, L.: Galois groups and factoring polynomials over finite fields. SIAM J. Discrete Math. 5(3), 345---365 (1992)

Digital Library

[38]

Saha, C.: Factoring polynomials over finite fields using balance test. In: Albers, S., Weil, P. (eds.) 25th International Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics (LIPIcs), vol. 1, pp. 609---620. Schloss Dagstuhl---Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2008). http://drops.dagstuhl.de/opus/volltexte/2008/1323

[39]

Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod $$p$$p. Math. Comput. 44(170), 483---494 (1985)

[40]

Shoup, V.: A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In: Watt, S.M. (ed.) ISSAC '91: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, pp. 14---21. ACM Press (1991)

Digital Library

[41]

Shoup, V.: NTL: A Library for doing Number Theory (2014) Software, version 8.0.0. http://www.shoup.net/ntl

[42]

Shoup, V.: On the deterministic complexity of factoring polynomials over finite fields. Inf. Process. Lett. 33(5), 261---267 (1990)

Digital Library

[43]

Shoup, V.: Smoothness and factoring polynomials over finite fields. Inf. Process. Lett. 38(1), 39---42 (1991)

Digital Library

[44]

Shoup, V.: Searching for primitive roots in finite fields. Math. Comput. 58, 369---380 (1992)

[45]

Vaccon, T.: $$p$$p-adic precision. Ph.D. thesis, Université Rennes 1 (2015) https://tel.archives-ouvertes.fr/tel-01205269

[46]

van der Hoeven, J., Lecerf, G.: Sparse polynomial interpolation in practice. ACM Commun. Comput. Algebra 48(4) (2014). In section "ISSAC 2014 Software Presentations"

Digital Library

[47]

von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003)

Digital Library

[48]

von zur Gathen, J., Panario, D.: Factoring polynomials over finite fields: a survey. J. Symb. Comput. 31(1---2), 3---17 (2001)

Digital Library

[49]

von zur Gathen, J.: Factoring polynomials and primitive elements for special primes. Theor. Comput. Sci. 52(1---2), 77---89 (1987)

Digital Library

[50]

¿rałek, B.: Using partial smoothness of $$p-1$$p-1 for factoring polynomials modulo $$p$$p. Math. Comput. 79, 2353---2359 (2010)

Cited By

Go SPan VSoto P(2023)Root-Squaring for Root-FindingComputer Algebra in Scientific Computing10.1007/978-3-031-41724-5_6(107-127)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-41724-5_6
Abelard SCouvreur ALecerf G(2022)Efficient computation of Riemann–Roch spaces for plane curves with ordinary singularitiesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-022-00588-x35:6(739-804)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00200-022-00588-x
van der Hoeven JMonagan M(2021)Computing one billion roots using the tangent Graeffe methodACM Communications in Computer Algebra10.1145/3457341.345734254:3(65-85)Online publication date: 15-Mar-2021
https://dl.acm.org/doi/10.1145/3457341.3457342
Show More Cited By

Deterministic root finding over finite fields using Graeffe transforms
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
2. Theory of computation

Recommendations

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 ...
Randomized Root Finding over Finite FFT-fields using Tangent Graeffe Transforms
ISSAC '15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation

Consider a finite field F_q whose multiplicative group has smooth cardinality. We study the problem of computing all roots of a polynomial that splits over F_q, which was one of the bottlenecks for fast sparse interpolation in practice. We revisit and ...
Tame decompositions and collisions

A univariate polynomial f over a field is decomposable if f = g h = g ( h ) with nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials over a finite field F q . The tame case,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applicable Algebra in Engineering, Communication and Computing

Applicable Algebra in Engineering, Communication and Computing Volume 27, Issue 3

June 2016

86 pages

ISSN:0938-1279

EISSN:1432-0622

Issue’s Table of Contents

Copyright © Copyright © 2016 Springer-Verlag Berlin Heidelberg.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Go SPan VSoto P(2023)Root-Squaring for Root-FindingComputer Algebra in Scientific Computing10.1007/978-3-031-41724-5_6(107-127)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-41724-5_6
Abelard SCouvreur ALecerf G(2022)Efficient computation of Riemann–Roch spaces for plane curves with ordinary singularitiesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-022-00588-x35:6(739-804)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00200-022-00588-x
van der Hoeven JMonagan M(2021)Computing one billion roots using the tangent Graeffe methodACM Communications in Computer Algebra10.1145/3457341.345734254:3(65-85)Online publication date: 15-Mar-2021
https://dl.acm.org/doi/10.1145/3457341.3457342
van der Hoeven JLecerf G(2021)On the Complexity Exponent of Polynomial System SolvingFoundations of Computational Mathematics10.1007/s10208-020-09453-021:1(1-57)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s10208-020-09453-0
Abelard SCouvreur ALecerf GEmiris IZhi LMantzaflaris A(2020)Sub-quadratic time for riemann-roch spacesProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3404053(14-21)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3404053
van der Hoeven JMonagan M(2020)Implementing the Tangent Graeffe Root Finding MethodMathematical Software – ICMS 202010.1007/978-3-030-52200-1_48(482-492)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.1007/978-3-030-52200-1_48
van der Hoeven JLecerf GYap CEl Din M(2017)Composition Modulo Powers of PolynomialsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087634(445-452)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087634
Lairez PVaccon TAbramov SZima EGao X(2016)On p-Adic Differential Equations with Separation of VariablesProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930912(319-323)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930912

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents