{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:53:48Z","timestamp":1776848028361,"version":"3.51.2"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1992,9,1]],"date-time":"1992-09-01T00:00:00Z","timestamp":715305600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1992,9]]},"DOI":"10.1007\/bf01272074","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T04:41:33Z","timestamp":1111639293000},"page":"187-224","source":"Crossref","is-referenced-by-count":113,"title":["Computing Frobenius maps and factoring polynomials"],"prefix":"10.1007","volume":"2","author":[{"given":"Joachim","family":"von zur Gathen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor","family":"Shoup","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974."},{"key":"CR2","first-page":"1","volume":"14","author":"A. Arwin","year":"1918","unstructured":"A. Arwin. \u00dcber Kongruenzen von dem f\u00fcnften und h\u00f6heren Graden nach einem Primzahlmodulus.Arkiv f\u00f6r matematik, astronomi o. fysik 14 (1918), 1?46.","journal-title":"Arkiv f\u00f6r matematik, astronomi o. fysik"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"L. Babai, E. M. Luks, and \u00c1. Seress. Fast management of permutation groups. In29th Annual Symposium on Foundations of Computer Science, 272?282, 1988.","DOI":"10.1109\/SFCS.1988.21943"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W. Baur","year":"1983","unstructured":"W. Baur and V. Strassen. The complexity of computing partial derivatives.Theoret. Comput. Sci. 22 (1983), 317?330.","journal-title":"Theoret. Comput. Sci."},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. Probabilistic algorithms in finite fields. In22nd Annual Symposium on Foundations of Computer Science, 394?398, 1981.","DOI":"10.1109\/SFCS.1981.37"},{"key":"CR6","unstructured":"E. R. Berlekamp.Algebraic Coding Theory. McGraw-Hill, 1968."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","volume":"24","author":"E. R. Berlekamp","year":"1970","unstructured":"E. R. Berlekamp. Factoring polynomials over large finite fields.Math. Comp. 24 (1970), 713?735.","journal-title":"Math. Comp."},{"key":"CR8","unstructured":"A. Borodin and I. Munro.The Computational Complexity of Algebraic and Numeric Problems. American Elsevier, 1975."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1145\/322092.322099","volume":"25","author":"R. P. Brent","year":"1978","unstructured":"R. P. Brent and H. T. Kung. Fast algorithms for manipulating formal power series.J. Assoc. Comput. Mach. 25 (1978), 581?595.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"J. Buchmann. Complexity of algorithms in algebraic number theory. InNumber Theory. Proc. First Conf. Canadian Number Theory Assoc., 37?53. Walter de Gruyter, 1990.","DOI":"10.1515\/9783110848632-006"},{"issue":"2","key":"CR11","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1093\/qmath\/5.1.102","volume":"5","author":"M. C. R. Butler","year":"1954","unstructured":"M. C. R. Butler. On the reducibility of polynomials over a finite field.Quart. J. Math., Oxford Ser. (2)5 (1954), 102?107.","journal-title":"Quart. J. Math., Oxford Ser."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1109\/TIT.1983.1056666","volume":"29","author":"P. Camion","year":"1983","unstructured":"P. Camion. Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials.IEEE Trans. Inform. Theory IT-29 (1983), 378?385.","journal-title":"IEEE Trans. Inform. Theory IT"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"J. F. Canny, E. Kaltofen, and L. Yagati. Solving systems of non-linear polynomial equations faster. InProc. Int. Symp. on Symbolic and Algebraic Comp., 121?128, 1989.","DOI":"10.1145\/74540.74556"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/BF01178683","volume":"28","author":"D. G. Cantor","year":"1991","unstructured":"D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras.Acta. Inf. 28 (1991), 693?701.","journal-title":"Acta. Inf."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1090\/S0025-5718-1981-0606517-5","volume":"36","author":"D. G. Cantor","year":"1981","unstructured":"D. G. Cantor and H. Zassenhaus. A new algorithm for factoring polynomials over finite fields.Math. Comp. 36 (1981), 587?592.","journal-title":"Math. Comp."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions.J. Symb. Comp. 9 (1990), 23?52.","journal-title":"J. Symb. Comp."},{"key":"CR17","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest.Introduction to algorithms. MIT Press, 1989."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0022-0000(85)90043-1","volume":"31","author":"J. Gathen von zur","year":"1985","unstructured":"J. von zur Gathen. Irreducibility of multivariate polynomials.J. Computer System Sciences 31 (1985), 225?264.","journal-title":"J. Computer System Sciences"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0304-3975(87)90081-8","volume":"52","author":"J. Gathen von zur","year":"1987","unstructured":"J. von zur Gathen. Factoring polynomials and primitive elements for special primes.Theoret. Comput. Sci. 52, (1987), 77?89.","journal-title":"Theoret. Comput. Sci."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1016\/S0747-7171(08)80158-7","volume":"10","author":"J. Gathen von zur","year":"1990","unstructured":"J. von zur Gathen and M. Giesbrecht. Constructing normal bases in finite fields.J. Symb. Comp. 10, (1990), 547?570.","journal-title":"J. Symb. Comp."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/0890-5401(91)90078-G","volume":"91","author":"J. Gathen von zur","year":"1991","unstructured":"J. von zur Gathen and G. Seroussi. Boolean circuits versus arithmetic circuits.Inform. and Comput. 91, (1991), 142?154.","journal-title":"Inform. and Comput."},{"key":"CR22","unstructured":"G. H. Hardy and E. M. Wright.An Introduction to the Theory of Numbers. Oxford University Press, fifth edition, 1984."},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"E. Kaltofen. Polynomial factorization 1982?1986. In Computers in Mathematics,ed. D. V. Chudnovsky, R. D. Jenks, Lecture Notes in Pure and Applied Mathematics, vol. 125, 285?309, 1990.","DOI":"10.1201\/9781003072157-9"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/0196-6774(88)90026-0","volume":"9","author":"M. Kaminski","year":"1988","unstructured":"M. Kaminski, D. G. Kirkpatrick, and N. H. Bshouty. Addition requirements for matrix and transposed matrix products.J. of Algorithms 9 (1988), 354?364.","journal-title":"J. of Algorithms"},{"key":"CR25","unstructured":"D. E. Knuth.The Art of Computer Programming, vol. 2. Addison-Wesley, second edition, 1981."},{"key":"CR26","unstructured":"R. Lidl and H. Niederreiter.Finite Fields. Addison-Wesley, 1983."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1090\/S0025-5718-1969-0257039-X","volume":"23","author":"R. J. McEliece","year":"1969","unstructured":"R. J. McEliece. Factorization of polynomials over finite fields.Math. Comp. 23 (1969), 861?867.","journal-title":"Math. Comp."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1137\/0221018","volume":"21","author":"A. J. Menezes","year":"1992","unstructured":"A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Subgroup refinement algorithms for root finding inGF(q).SIAM J. Comput. 21 (1992), 228?239.","journal-title":"SIAM J. Comput."},{"key":"CR29","first-page":"205","volume":"290","author":"M. Mignotte","year":"1988","unstructured":"M. Mignotte and C. Schnorr. Calcul des racinesd-i\u00e8mes dans un corps fini.C. R. Acad. Sci. Paris 290 (1988), 205?206.","journal-title":"C. R. Acad. Sci. Paris"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1090\/S0025-5718-1977-0422193-8","volume":"31","author":"R. T. Moenck","year":"1977","unstructured":"R. T. Moenck. On the efficiency of algorithms for polynomial factoring.Math. Comp. 31 (1977), 235?250.","journal-title":"Math. Comp."},{"key":"CR31","doi-asserted-by":"crossref","unstructured":"A. M. Odlyzko. Discrete logarithms in finite fields and their cryptographic significance. InAdvances in Cryptology, Proceedings of Eurocrypt 84, 224?314. Springer-Verlag, 1985.","DOI":"10.1007\/3-540-39757-4_20"},{"key":"CR32","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1137\/0209024","volume":"9","author":"M. O. Rabin","year":"1980","unstructured":"M. O. Rabin. Probabilistic algorithms in finite fields.SIAM J. Comput. 9 (1980), 273?280.","journal-title":"SIAM J. Comput."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/BF00289470","volume":"7","author":"A. Sch\u00f6nhage","year":"1977","unstructured":"A. Sch\u00f6nhage. Schnelle Multiplikation von Polynomen \u00fcber K\u00f6rpern der Charakteristik 2.Acta Inf. 7 (1977), 395?398.","journal-title":"Acta Inf."},{"key":"CR34","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nhage","year":"1971","unstructured":"A. Sch\u00f6nhage and V. Strassen. Schnelle Multiplikation gro\u00dfer Zahlen.Computing 7 (1971), 281?292.","journal-title":"Computing"},{"key":"CR35","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0020-0190(90)90195-4","volume":"33","author":"V. Shoup","year":"1990","unstructured":"V. Shoup. On the deterministic complexity of factoring polynomials over finite fields.Inform. Process. Lett. 33 (1990), 261?267.","journal-title":"Inform. Process. Lett."},{"key":"CR36","doi-asserted-by":"crossref","unstructured":"V. Shoup. A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. InProc. Int. Symp. on Symbolic and Algebraic Comp., 14?21, 1991.","DOI":"10.1145\/120694.120697"},{"key":"CR37","unstructured":"V. Shoup. Fast construction of irreducible polynomials over finite fields. InProc. IEEE Symp. on Discrete Algorithms, Austin, TX, 1993."},{"key":"CR38","unstructured":"V. Shoup and R. Smolensky. An algorithm for modular composition. Preprint, 1992."},{"key":"CR39","doi-asserted-by":"crossref","unstructured":"I. E. Shparlinski.Computational problems in finite fields. Kluwer, 1992. To appear.","DOI":"10.1007\/978-94-011-1806-4"},{"key":"CR40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0212001","volume":"12","author":"V. Strassen","year":"1983","unstructured":"V. Strassen. The computational complexity of continued fractions.SIAM J. Comput. 12 (1983), 1?27.","journal-title":"SIAM J. Comput."},{"key":"CR41","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1080\/02522667.1989.10698971","volume":"10","author":"A. Thiong ly","year":"1989","unstructured":"A. Thiong ly. A deterministic algorithm for factorizing polynomials over extensionsGF(p m ) ofGF(p), p a small prime.J. of Information and Optimization Sciences 10 (1989), 337?344.","journal-title":"J. of Information and Optimization Sciences"},{"key":"CR42","doi-asserted-by":"crossref","unstructured":"D. Y. Y. Yun. On square-free decomposition algorithms. InProc. ACM Symp. Symbolic and Algebraic Comp., 26?35, 1976.","DOI":"10.1145\/800205.806320"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01272074.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01272074\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01272074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,7]],"date-time":"2021-07-07T06:06:54Z","timestamp":1625638014000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01272074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,9]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,9]]}},"alternative-id":["BF01272074"],"URL":"https:\/\/doi.org\/10.1007\/bf01272074","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,9]]}}}