{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:15:42Z","timestamp":1786979742829,"version":"3.56.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,12,12]],"date-time":"2015-12-12T00:00:00Z","timestamp":1449878400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2016,6]]},"DOI":"10.1007\/s00200-015-0280-5","type":"journal-article","created":{"date-parts":[[2015,12,12]],"date-time":"2015-12-12T01:32:15Z","timestamp":1449883935000},"page":"237-257","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Deterministic root finding over finite fields using Graeffe transforms"],"prefix":"10.1007","volume":"27","author":[{"given":"Bruno","family":"Grenet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joris","family":"van der Hoeven","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gr\u00e9goire","family":"Lecerf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,12,12]]},"reference":[{"key":"280_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.jsc.2012.05.009","volume":"52","author":"LE Allem","year":"2013","unstructured":"Allem, L.E., Gao, S., Trevisan, V.: Extracting sparse factors from multivariate integral polynomials. J. Symb. Comput. 52, 3\u201316 (2013)","journal-title":"J. Symb. Comput."},{"issue":"1","key":"280_CR2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1112\/S1461157013000296","volume":"17","author":"M Arora","year":"2014","unstructured":"Arora, M., Ivanyos, G., Karpinski, M., Saxena, N.: Deterministic polynomial factoring and association schemes. LMS J. Comput. Math. 17(1), 123\u2013140 (2014)","journal-title":"LMS J. Comput. Math."},{"key":"280_CR3","doi-asserted-by":"crossref","first-page":"1719","DOI":"10.1090\/S0025-5718-97-00890-9","volume":"66","author":"E Bach","year":"1997","unstructured":"Bach, E.: Comments on search procedures for primitive roots. Math. Comput. 66, 1719\u20131727 (1997)","journal-title":"Math. Comput."},{"key":"280_CR4","doi-asserted-by":"crossref","first-page":"1853","DOI":"10.1002\/j.1538-7305.1967.tb03174.x","volume":"46","author":"ER Berlekamp","year":"1967","unstructured":"Berlekamp, E.R.: Factoring polynomials over finite fields. Bell Syst. Tech. J. 46, 1853\u20131859 (1967)","journal-title":"Bell Syst. Tech. J."},{"key":"280_CR5","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","volume":"24","author":"ER Berlekamp","year":"1970","unstructured":"Berlekamp, E.R.: Factoring polynomials over large finite fields. Math. Comput. 24, 713\u2013735 (1970)","journal-title":"Math. Comput."},{"key":"280_CR6","unstructured":"Bostan, A., Gonzales-Vega, L., Perdry, H., Schost, \u00c9.: Complexity issues on Newton sums of polynomials (2005). Distributed in the digital proceedings of MEGA\u201905"},{"issue":"1","key":"280_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jsc.2005.07.001","volume":"41","author":"A Bostan","year":"2006","unstructured":"Bostan, A., Flajolet, P., Salvy, B., Schost, \u00c9.: Fast computation of special resultants. J. Symb. Comput. 41(1), 1\u201329 (2006)","journal-title":"J. Symb. Comput."},{"issue":"6","key":"280_CR8","doi-asserted-by":"crossref","first-page":"1777","DOI":"10.1137\/S0097539704443793","volume":"36","author":"A Bostan","year":"2007","unstructured":"Bostan, A., Gaudry, P., Schost, \u00c9.: Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator. SIAM J. Comput. 36(6), 1777\u20131806 (2007)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"280_CR9","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1016\/j.jco.2004.09.009","volume":"21","author":"A Bostan","year":"2005","unstructured":"Bostan, A., Schost, \u00c9.: Polynomial evaluation and interpolation on special sets of points. J. Complex. 21(4), 420\u2013446 (2005)","journal-title":"J. Complex."},{"key":"280_CR10","doi-asserted-by":"crossref","unstructured":"Camion, P.: A deterministic algorithm for factorizing polynomials of $${ F}_q[X]$$ F q [ X ] . In: Combinatorial mathematics (Marseille-Luminy, 1981), North-Holland Math. Stud., vol. 75, pp. 149\u2013157. North-Holland, Amsterdam (1983)","DOI":"10.1016\/S0304-0208(08)73382-6"},{"issue":"7","key":"280_CR11","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/BF01178683","volume":"28","author":"DG Cantor","year":"1991","unstructured":"Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inform. 28(7), 693\u2013701 (1991)","journal-title":"Acta Inform."},{"issue":"154","key":"280_CR12","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1090\/S0025-5718-1981-0606517-5","volume":"36","author":"DG Cantor","year":"1981","unstructured":"Cantor, D.G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comput. 36(154), 587\u2013592 (1981)","journal-title":"Math. Comput."},{"key":"280_CR13","doi-asserted-by":"crossref","unstructured":"Caruso, X., Roe, D., Vaccon, T.: Tracking $$p$$ p -adic precision. LMS J.\u00a0Comput. Math. 17, 274\u2013294 (2014). Special Issue A, Algorithmic Number Theory Symposium XI","DOI":"10.1112\/S1461157014000357"},{"issue":"285","key":"280_CR14","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1090\/S0025-5718-2013-02707-X","volume":"83","author":"E Costa","year":"2014","unstructured":"Costa, E., Harvey, D.: Faster deterministic integer factorization. Math. Comput. 83(285), 339\u2013345 (2014)","journal-title":"Math. Comput."},{"key":"280_CR15","doi-asserted-by":"crossref","unstructured":"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\u2013219. Springer, Berlin (1994)","DOI":"10.1007\/3-540-58691-1_58"},{"issue":"1\u20132","key":"280_CR16","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1006\/jsco.1999.1001","volume":"31","author":"S Gao","year":"2001","unstructured":"Gao, S.: On the deterministic complexity of factoring polynomials. J. Symb. Comput. 31(1\u20132), 19\u201336 (2001)","journal-title":"J. Symb. Comput."},{"issue":"1","key":"280_CR17","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/jcom.2000.0571","volume":"17","author":"M Giusti","year":"2001","unstructured":"Giusti, M., Lecerf, G., Salvy, B.: A Gr\u00f6bner free alternative for polynomial system solving. J. Complex. 17(1), 154\u2013211 (2001)","journal-title":"J. Complex."},{"key":"280_CR18","doi-asserted-by":"crossref","unstructured":"Grenet, B., van\u00a0der Hoeven, J., Lecerf, G.: Randomized root finding over finite FFT-fields using tangent Graeffe transforms. In: Robertz, D. (ed.) ISSAC \u201915: Proceedings of the 2015 International Symposium on Symbolic and Algebraic Computation, pp. 197\u2013204. ACM Press (2015)","DOI":"10.1145\/2755996.2756647"},{"key":"280_CR19","unstructured":"Harvey, D., van der Hoeven, J., Lecerf, G.: Even faster integer multiplication (2014). arXiv:1407.3360"},{"key":"280_CR20","unstructured":"Harvey, D., van der Hoeven, J., Lecerf, G.: Faster polynomial multiplication over finite fields (2014). arXiv:1407.3361"},{"issue":"3","key":"280_CR21","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1016\/0196-6774(91)90014-P","volume":"12","author":"MDA Huang","year":"1991","unstructured":"Huang, M.D.A.: Generalized Riemann hypothesis and factoring polynomials over finite fields. J. Algorithms 12(3), 464\u2013481 (1991)","journal-title":"J. Algorithms"},{"key":"280_CR22","doi-asserted-by":"crossref","unstructured":"Kaltofen, E.: Polynomial factorization: a success story. In: Hong, H. (ed.) ISSAC \u201903: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, pp. 3\u20134. ACM Press (2003)","DOI":"10.1145\/860854.860857"},{"key":"280_CR23","doi-asserted-by":"crossref","unstructured":"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 \u201908), pp. 146\u2013155. IEEE (2008)","DOI":"10.1109\/FOCS.2008.13"},{"issue":"6","key":"280_CR24","doi-asserted-by":"crossref","first-page":"1767","DOI":"10.1137\/08073408X","volume":"40","author":"KS Kedlaya","year":"2011","unstructured":"Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767\u20131802 (2011)","journal-title":"SIAM J. Comput."},{"key":"280_CR25","first-page":"1","volume":"92","author":"L Kronecker","year":"1882","unstructured":"Kronecker, L.: Grundz\u00fcge einer arithmetischen theorie der algebraischen Gr\u00f6ssen. J. Reine Angew. Math. 92, 1\u2013122 (1882)","journal-title":"J. Reine Angew. Math."},{"issue":"2","key":"280_CR26","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/s00200-008-0062-4","volume":"19","author":"G Lecerf","year":"2008","unstructured":"Lecerf, G.: Fast separable factorization and applications. Appl. Algebra Eng. Commun. Comput. 19(2), 135\u2013160 (2008)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"issue":"4","key":"280_CR27","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1007\/s002110100278","volume":"89","author":"G Malajovich","year":"2001","unstructured":"Malajovich, G., Zubelli, J.P.: Tangent graeffe iteration. Numer. Math. 89(4), 749\u2013782 (2001)","journal-title":"Numer. Math."},{"issue":"2","key":"280_CR28","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1137\/0221018","volume":"21","author":"AJ Menezes","year":"1992","unstructured":"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\u2013239 (1992)","journal-title":"SIAM J. Comput."},{"issue":"12","key":"280_CR29","first-page":"467","volume":"306","author":"M Mignotte","year":"1988","unstructured":"Mignotte, M., Schnorr, C.: Calcul d\u00e9terministe des racines d\u2019un polyn\u00f4me dans un corps fini. C. R. Acad. Sci. Paris S\u00e9r. I Math 306(12), 467\u2013472 (1988)","journal-title":"C. R. Acad. Sci. Paris S\u00e9r. I Math"},{"key":"280_CR30","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1090\/S0025-5718-1977-0422193-8","volume":"31","author":"RT Moenck","year":"1977","unstructured":"Moenck, R.T.: On the efficiency of algorithms for polynomial factoring. Math. Comput. 31, 235\u2013250 (1977)","journal-title":"Math. Comput."},{"key":"280_CR31","doi-asserted-by":"crossref","unstructured":"Mullen, G.L., Panario, D.: Handbook of Finite Fields. Discrete Mathematics and Its Applications. Chapman and Hall\/CRC (2013)","DOI":"10.1201\/b15006"},{"issue":"2","key":"280_CR32","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1137\/S0036144595288554","volume":"39","author":"V Pan","year":"1997","unstructured":"Pan, V.: Solving a polynomial equation: some history and recent progress. SIAM Rev. 39(2), 187\u2013220 (1997)","journal-title":"SIAM Rev."},{"key":"280_CR33","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1006\/ffta.1999.0267","volume":"6","author":"V Pan","year":"2000","unstructured":"Pan, V.: New techniques for the computation of linear recurrence coefficients. Finite Fields Appl. 6, 93\u2013118 (2000)","journal-title":"Finite Fields Appl."},{"issue":"1","key":"280_CR34","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1109\/TIT.1978.1055817","volume":"24","author":"SC Pohlig","year":"1978","unstructured":"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\u2013110 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"280_CR35","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1137\/0209024","volume":"9","author":"MO Rabin","year":"1980","unstructured":"Rabin, M.O.: Probabilistic algorithms in finite fields. SIAM J. Comput. 9(2), 273\u2013280 (1980)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"280_CR36","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF02124680","volume":"9","author":"L R\u00f3nyai","year":"1989","unstructured":"R\u00f3nyai, L.: Factoring polynomials modulo special primes. Combinatorica 9(2), 199\u2013206 (1989)","journal-title":"Combinatorica"},{"issue":"3","key":"280_CR37","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/0405026","volume":"5","author":"L R\u00f3nyai","year":"1992","unstructured":"R\u00f3nyai, L.: Galois groups and factoring polynomials over finite fields. SIAM J. Discrete Math. 5(3), 345\u2013365 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"280_CR38","unstructured":"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\u2013620. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2008). http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2008\/1323"},{"issue":"170","key":"280_CR39","first-page":"483","volume":"44","author":"R Schoof","year":"1985","unstructured":"Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod $$p$$ p . Math. Comput. 44(170), 483\u2013494 (1985)","journal-title":"Math. Comput."},{"key":"280_CR40","doi-asserted-by":"crossref","unstructured":"Shoup, V.: A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In: Watt, S.M. (ed.) ISSAC \u201991: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, pp. 14\u201321. ACM Press (1991)","DOI":"10.1145\/120694.120697"},{"key":"280_CR41","unstructured":"Shoup, V.: NTL: A Library for doing Number Theory (2014) Software, version 8.0.0. http:\/\/www.shoup.net\/ntl"},{"issue":"5","key":"280_CR42","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0020-0190(90)90195-4","volume":"33","author":"V Shoup","year":"1990","unstructured":"Shoup, V.: On the deterministic complexity of factoring polynomials over finite fields. Inf. Process. Lett. 33(5), 261\u2013267 (1990)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"280_CR43","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0020-0190(91)90212-Z","volume":"38","author":"V Shoup","year":"1991","unstructured":"Shoup, V.: Smoothness and factoring polynomials over finite fields. Inf. Process. Lett. 38(1), 39\u201342 (1991)","journal-title":"Inf. Process. Lett."},{"key":"280_CR44","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1090\/S0025-5718-1992-1106981-9","volume":"58","author":"V Shoup","year":"1992","unstructured":"Shoup, V.: Searching for primitive roots in finite fields. Math. Comput. 58, 369\u2013380 (1992)","journal-title":"Math. Comput."},{"key":"280_CR45","unstructured":"Vaccon, T.: $$p$$ p -adic precision. Ph.D. thesis, Universit\u00e9 Rennes 1 (2015) https:\/\/tel.archives-ouvertes.fr\/tel-01205269"},{"key":"280_CR46","doi-asserted-by":"crossref","unstructured":"van der Hoeven, J., Lecerf, G.: Sparse polynomial interpolation in practice. ACM Commun. Comput. Algebra 48(4) (2014). In section \u201cISSAC 2014 Software Presentations\u201d","DOI":"10.1145\/2733693.2733721"},{"key":"280_CR47","unstructured":"von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003)"},{"key":"280_CR48","doi-asserted-by":"crossref","unstructured":"von zur Gathen, J., Panario, D.: Factoring polynomials over finite fields: a survey. J. Symb. Comput. 31(1\u20132), 3\u201317 (2001)","DOI":"10.1006\/jsco.1999.1002"},{"key":"280_CR49","doi-asserted-by":"crossref","unstructured":"von zur Gathen, J.: Factoring polynomials and primitive elements for special primes. Theor. Comput. Sci. 52(1\u20132), 77\u201389 (1987)","DOI":"10.1016\/0304-3975(87)90081-8"},{"key":"280_CR50","doi-asserted-by":"crossref","first-page":"2353","DOI":"10.1090\/S0025-5718-2010-02377-4","volume":"79","author":"B \u0179ra\u0142ek","year":"2010","unstructured":"\u0179ra\u0142ek, B.: Using partial smoothness of $$p-1$$ p - 1 for factoring polynomials modulo $$p$$ p . Math. Comput. 79, 2353\u20132359 (2010)","journal-title":"Math. Comput."}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-015-0280-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00200-015-0280-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-015-0280-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,2]],"date-time":"2019-09-02T07:25:38Z","timestamp":1567409138000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00200-015-0280-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,12]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["280"],"URL":"https:\/\/doi.org\/10.1007\/s00200-015-0280-5","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,12]]}}}