{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:08:38Z","timestamp":1787508518719,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540586913","type":"print"},{"value":"9783540490449","type":"electronic"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"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":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58691-1_47","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:39:53Z","timestamp":1330256393000},"page":"93-107","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A new modular interpolation algorithm for factoring multivariate polynomials"],"prefix":"10.1007","author":[{"given":"Ronitt","family":"Rubinfeld","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Zippel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, and Madhu Sudan. Reconstructing algebraic functions from mixed data. In 33th Symposium on Foundations of Computer Science, pages 503\u2013512. ACM, 1992.","DOI":"10.1109\/SFCS.1992.267801"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Michael Ben Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In 20th Symposium on Theory of Computing, pages 301\u2013309. ACM, 1988.","DOI":"10.1145\/62212.62241"},{"key":"12_CR3","doi-asserted-by":"crossref","first-page":"1853","DOI":"10.1002\/j.1538-7305.1967.tb03174.x","volume":"46","author":"E. R. Berlekamp","year":"1967","unstructured":"Elwyn Ralph Berlekamp. Factoring polynomials over finite fields. Bell System technical Journal, 46:1853, 1967.","journal-title":"Bell System technical Journal"},{"issue":"III","key":"12_CR4","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","volume":"24","author":"E. R. Berlekamp","year":"1970","unstructured":"Elwyn Ralph Berlekamp. Factoring polynomials over large finite fields. Mathematics of Computation, 24(III):713\u2013735, July 1970.","journal-title":"Mathematics of Computation"},{"issue":"154","key":"12_CR5","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1090\/S0025-5718-1981-0606517-5","volume":"36","author":"D. G. Cantor","year":"1981","unstructured":"David G. Cantor and Hans Zassenhaus. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation, 36(154):587\u2013592, April 1981.","journal-title":"Mathematics of Computation"},{"key":"12_CR6","unstructured":"Michael Clausen, A. Dress, Johannes Grabmeier, and Marek Karpinski. On zerotesting and interpolation of fc-sparse multivariate polynomials over finite fields. Research Report 8522-CS, Universit\u00e4t Bonn, May 1988."},{"key":"12_CR7","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1112\/plms\/s3-43.2.227","volume":"43","author":"S. D. Cohen","year":"1981","unstructured":"S. D. Cohen. The distribution of Galois groups and Hilbert's irreducibility theorem. Proceedings of the London Mathematical Society (3), 43:227\u2013250, 1981.","journal-title":"Proceedings of the London Mathematical Society (3)"},{"issue":"4","key":"12_CR8","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"R. A. Demillo","year":"1978","unstructured":"Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193\u2013195, June 1978.","journal-title":"Information Processing Letters"},{"key":"12_CR9","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF01206609","volume":"95","author":"K. D\u00f6rge","year":"1926","unstructured":"K. D\u00f6rge. \u00dcber die Seltenheit der reduziblen Polynome und der Normalgleichungen. Mathematische Annalen, 95:247\u2013256, 1926.","journal-title":"Mathematische Annalen"},{"key":"12_CR10","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/BF01206597","volume":"95","author":"K. D\u00f6rge","year":"1926","unstructured":"K. D\u00f6rge. Zum Hilbertschen Irreduzibilit\u00e4tssatz. Mathematische Annalen, 95:84\u201397, 1926.","journal-title":"Mathematische Annalen"},{"key":"12_CR11","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/BF01209160","volume":"96","author":"K. D\u00f6rge","year":"1927","unstructured":"K. D\u00f6rge. Einfacher Beweis des Hilbertschen Irreduzibilit\u00e4tssatzes. Mathematische Annalen, 96:176\u2013182, 1927.","journal-title":"Mathematische Annalen"},{"key":"12_CR12","unstructured":"Torsten Ekedahl. An effective version of the Hilbert irreducibility theorem. In Catherine Goldstein, editor, S\u00e9minaire de Th\u00e9orie des Nombres, Paris 1988\u20131989, volume 91 of Progress in Mathematics, pages 241\u2013249, Boston, 1990."},{"key":"12_CR13","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF01174354","volume":"33","author":"W. Franz","year":"1931","unstructured":"W. Franz. Untersuchugen aum Hilbertschen Irreduzibilit\u00e4tssatz. Mathematische Zeitschrift, 33:275\u2013293, 1931.","journal-title":"Mathematische Zeitschrift"},{"key":"12_CR14","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0022-314X(74)90015-8","volume":"6","author":"M. D. Fried","year":"1974","unstructured":"Michael D. Fried. On Hilbert's irreducibility theorem. Journal of Number Theory, 6:211\u2013231, 1974.","journal-title":"Journal of Number Theory"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Dima Yu. Grigor'ev and Marek Karpinski. The matching problem for bipartite graphs with polynomial bounded perminants is NC. In 28th Symposium on Foundations of Computer Science, pages 166\u2013172. ACM, 1987.","DOI":"10.1109\/SFCS.1987.56"},{"issue":"6","key":"12_CR16","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1137\/0219073","volume":"19","author":"D. Y. Grigor'ev","year":"1990","unstructured":"Dima Yu. Grigor'ev, Marek Karpinski, and Michael F. Singer. Past parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM Journal of Computing, 19(6):1059\u20131063, 1990.","journal-title":"SIAM Journal of Computing"},{"key":"12_CR17","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1515\/crll.1892.110.104","volume":"110","author":"D. Hilbert","year":"1892","unstructured":"David Hilbert. \u00fcber die Irreduzibilit\u00e4t ganzer rationaler Funktionen mit ganzzahligen Koeffizienten. Journal f\u00fcr reine und angewante Mathematik, 110:104\u2013129, 1892.","journal-title":"Journal f\u00fcr reine und angewante Mathematik"},{"issue":"3","key":"12_CR18","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1016\/0196-6774(91)90015-Q","volume":"12","author":"M. A. Huang","year":"1991","unstructured":"Ming-Deh A. Huang. Factorization of polynomials over finite fields and decomposition of primes in algebraic number fields. Journal of Algorithms, 12(3):482\u2013489, 1991.","journal-title":"Journal of Algorithms"},{"issue":"3","key":"12_CR19","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1016\/0196-6774(91)90014-P","volume":"12","author":"M. A. Huang","year":"1991","unstructured":"Ming-Deh A. Huang. Generalized Riemann hypothesis and factoring polynomials over finite fields. Journal of Algorithms, 12(3):464\u2013481, 1991.","journal-title":"Journal of Algorithms"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Erich Kaltofen. Computing with polynomials given by straight-line programs II: Sparse factorization. In 26th Symposium on Foundations of Computer Science, pages 451\u2013457. ACM, 1985.","DOI":"10.1109\/SFCS.1985.17"},{"issue":"2","key":"12_CR21","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1137\/0214035","volume":"14","author":"E. Kaltofen","year":"1985","unstructured":"Erich Kaltofen. A polynomial-time reduction from bivariate to univariate integral polynomial factorization. SIAM Journal of Computing, 14(2):469\u2013489, May 1985.","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"12_CR22","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0747-7171(08)80015-6","volume":"9","author":"E. Kaltofen","year":"1990","unstructured":"Erich Kaltofen and Barry Marshall Trager. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. Journal of Symbolic Computation, 9(3):301\u2013320, March 1990.","journal-title":"Journal of Symbolic Computation"},{"key":"12_CR23","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/BF02988871","volume":"19","author":"H. Knobloch","year":"1955","unstructured":"Hans-Wilhelm Knobloch. Zum Hilbertschen Irreduzibilit\u00e4tssatz. Abhandlung Mathematische Seminar Univ. Hamburg, 19:176\u2013190, 1955.","journal-title":"Abhandlung Mathematische Seminar Univ. Hamburg"},{"issue":"1","key":"12_CR24","first-page":"12","volume":"59","author":"H. Knobloch","year":"1956","unstructured":"Hans-Wilhelm Knobloch. Die Seltenheit der reduziblen Polynome. Jarhesbericht der Deutsche Mathematische Verneinung, 59(1):12\u201319, 1956.","journal-title":"Jarhesbericht der Deutsche Mathematische Verneinung"},{"key":"12_CR25","first-page":"1","volume":"92","author":"L. Kronecker","year":"1882","unstructured":"Leopold Kronecker. Grundz\u00fcge einer arithmetischen Theorie der algebraischen Gr\u00f6\u00dfen. Journal f\u00fcr reine und angewante Mathematik, 92:1\u2013122, 1882.","journal-title":"Journal f\u00fcr reine und angewante Mathematik"},{"key":"12_CR26","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A. K. Lenstra","year":"1982","unstructured":"Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and Laslo Lov\u00e1sz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515\u2013534, 1982.","journal-title":"Mathematische Annalen"},{"key":"12_CR27","series-title":"volume 601 of Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BFb0035171","volume-title":"Theory of Computing and Systems","author":"V. S. Miller","year":"1992","unstructured":"Victor S. Miller. Factoring polynomials via relation-finding. In Danny Dolev, Zvi Galil, and Michael Rodeh, editors, Theory of Computing and Systems, volume 601 of Lecture Notes in Computer Science, pages 115\u2013121, New York, 1992. Springer-Verlag."},{"key":"12_CR28","series-title":"volume 72 of Lecture Notes in Computer Science","volume-title":"EUROSAM '79","year":"1979","unstructured":"E. Ng, editor. EUROSAM '79, volume 72 of Lecture Notes in Computer Science, Berlin-Heidelberg-New York, 1979. Springer-Verlag."},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Lajos R\u00f3nyai. Galois groups and factoring polynomials over finite fields. In 30th Symposium on Foundations of Computer Science, pages 99\u2013104. ACM, 1989.","DOI":"10.1109\/SFCS.1989.63462"},{"key":"12_CR30","doi-asserted-by":"crossref","first-page":"333","DOI":"10.4064\/ap-16-3-333-340","volume":"16","author":"A. Schinzel","year":"1965","unstructured":"Andrej Schinzel. On Hilbert's irreducibility theorem. Annales Polinici Mathematici, 16:333\u2013340, 1965.","journal-title":"Annales Polinici Mathematici"},{"key":"12_CR31","series-title":"volume 172 of Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1007\/3-540-13345-3_40","volume-title":"Automata, Languages and Programming","author":"A. Sch\u00f6nhage","year":"1984","unstructured":"Arnold Sch\u00f6nhage. Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm. In Jan Paredaens, editor, Automata, Languages and Programming, volume 172 of Lecture Notes in Computer Science, pages 436\u2013447, Berlin-Heidelberg-New York, 1984. Springer-Verlag."},{"key":"12_CR32","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"Jacob T. Schwartz. Probabilistic algorithms for verification of polynomial identities. Journal of the Association for Computing Machinery, 27:701\u2013717, 1980.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"12_CR33","first-page":"331","volume":"21","author":"V. G. Sprindzuk","year":"1980","unstructured":"V. G. Sprindzuk. Reducibility of polynomials and rational points on algebraic curves. Soviet Mathematics, 21:331\u2013334,1980.","journal-title":"Soviet Mathematics"},{"key":"12_CR34","first-page":"26","volume":"340","author":"V. G. Sprindzuk","year":"1983","unstructured":"V. G. Sprindzuk. Arithmetic specializations in polynomials. Journal f\u00fcr reine und angewante Mathematik, 340: 26\u201352, 1983.","journal-title":"Journal f\u00fcr reine und angewante Mathematik"},{"issue":"166","key":"12_CR35","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1090\/S0025-5718-1984-0736459-9","volume":"42","author":"J. Gathen von zur","year":"1984","unstructured":"Joachim von zur Gathen. Hensel and Newton methods in valuation rings. Mathematics of Computation, 42(166):637\u2013661, April 1984.","journal-title":"Mathematics of Computation"},{"key":"12_CR36","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(85)90044-3","volume":"31","author":"J. Gathen von zur","year":"1985","unstructured":"Joachim von zur Gathen and Erich Kaltofen. Factoring sparse multivariate polynomials. Journal of Computer and System Sciences, 31:265\u2013287, 1985.","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR37","unstructured":"Richard Eliot Zippel. Probabilistic algorithms for sparse polynomials. In Ng [28], pages 216\u2013226."},{"key":"12_CR38","doi-asserted-by":"crossref","unstructured":"Richard Eliot Zippel. Newton's iteration and the sparse Hensel algorithm. In Paul Wang, editor, SYMSAC '81: Proceedings of the 1981 ACM Symposium on Symbolic and Algebraic Computation, pages 68\u201372. Association for Computing Machinery, 1981.","DOI":"10.1145\/800206.806372"},{"key":"12_CR39","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","volume":"9","author":"R. E. Zippel","year":"1990","unstructured":"Richard Eliot Zippel. Interpolating polynomials from their values. Journal of Symbolic Computation, 9:375\u2013403, March 1990.","journal-title":"Journal of Symbolic Computation"},{"key":"12_CR40","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-3188-3","volume-title":"Effective Polynomial Computation","author":"R. E. Zippel","year":"1993","unstructured":"Richard Eliot Zippel. Effective Polynomial Computation. Kluwer Academic Press, Boston, 1993."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Number Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58691-1_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T18:37:35Z","timestamp":1742582255000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58691-1_47"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540586913","9783540490449"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-58691-1_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"4 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}