{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T04:09:13Z","timestamp":1749874153777,"version":"3.41.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,1,5]],"date-time":"2017-01-05T00:00:00Z","timestamp":1483574400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,5]],"date-time":"2017-01-05T00:00:00Z","timestamp":1483574400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["NK105645"],"award-info":[{"award-number":["NK105645"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2012-T3-1-009","MOE2012-T3-1-009"],"award-info":[{"award-number":["MOE2012-T3-1-009","MOE2012-T3-1-009"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Hausdorff Grant","award":["EXC-59"],"award-info":[{"award-number":["EXC-59"]}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP140100118"],"award-info":[{"award-number":["DP140100118"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Hausdorff Center Bonn"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00453-016-0273-1","type":"journal-article","created":{"date-parts":[[2017,1,5]],"date-time":"2017-01-05T14:07:12Z","timestamp":1483625232000},"page":"560-575","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields"],"prefix":"10.1007","volume":"80","author":[{"given":"G\u00e1bor","family":"Ivanyos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor E.","family":"Shparlinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,5]]},"reference":[{"key":"273_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L., Manders, K., Miller, G.: On taking roots in finite fields. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE, pp. 175\u2013178 (1997)","DOI":"10.1109\/SFCS.1977.18"},{"issue":"4","key":"273_CR2","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13(4), 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"key":"273_CR3","doi-asserted-by":"crossref","unstructured":"Boneh, D., Lipton, R.J.: Algorithms for black-box fields and their application to cryptography. In: Koblitz, N. (ed.) Advances in Cryptology CRYPTO 96, pp. 283\u2013297. Springer, Berlin (1996)","DOI":"10.1007\/3-540-68697-5_22"},{"key":"273_CR4","unstructured":"Bourgain, J., Konyagin, S.V., Shparlinski, I.E.: Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm. Int. Math. Res. Not. 2008, 1\u201329 (2008)"},{"issue":"6","key":"273_CR5","doi-asserted-by":"publisher","first-page":"1524","DOI":"10.1137\/110850414","volume":"41","author":"J Bourgain","year":"2012","unstructured":"Bourgain, J., Garaev, M.Z., Konyagin, S.V., Shparlinski, I.E.: On the hidden shifted power problem. SIAM J. Comput. 41(6), 1524\u20131557 (2012)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"273_CR6","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1007\/s00039-003-0428-5","volume":"13","author":"M-C Chang","year":"2003","unstructured":"Chang, M.-C.: Factorization in generalized arithmetic progressions and application to the Erd\u0151s-Szemer\u00e9di sum-product problems. Geom. Funct. Anal. 13(4), 720\u2013736 (2003)","journal-title":"Geom. Funct. Anal."},{"issue":"3\u20134","key":"273_CR7","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s00605-013-0498-x","volume":"171","author":"J Cilleruelo","year":"2013","unstructured":"Cilleruelo, J., Shparlinski, I.: Concentration of points on curves in finite fields. Monatshefte Math. 171(3\u20134), 315\u2013327 (2013)","journal-title":"Monatshefte Math."},{"key":"273_CR8","doi-asserted-by":"crossref","unstructured":"Crandall, R., Pomerance, C.: Prime numbers: a computational perspective. Springer, New York (2001)","DOI":"10.1007\/978-1-4684-9316-0"},{"key":"273_CR9","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I.B.: On the randomness of legendre and jacobi sequences. In: Advances In: Goldwasser, S. (ed.) Cryptology CRYPTO 88, pp. 163\u2013172. Springer, Berlin (1990)","DOI":"10.1007\/0-387-34799-2_13"},{"key":"273_CR10","first-page":"549","volume":"46","author":"C D\u2019Andrea","year":"2013","unstructured":"D\u2019Andrea, C., Krick, T., Sombra, M.: Heights of varieties in multiprojective spaces and arithmetic nullstellens\u00e4tze. Ann. Sci. l\u2019ENS 46, 549\u2013627 (2013)","journal-title":"Ann. Sci. l\u2019ENS"},{"key":"273_CR11","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/s00605-014-0697-0","volume":"176","author":"D G\u00f3mez-P\u00e9rez","year":"2015","unstructured":"G\u00f3mez-P\u00e9rez, D., Shparlinski, I.E.: Subgroups generated by rational functions in finite fields. Monat. Math. 176, 241\u2013253 (2015)","journal-title":"Monat. Math."},{"key":"273_CR12","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212\u2013219. ACM (1996)","DOI":"10.1145\/237814.237866"},{"key":"273_CR13","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/053","volume-title":"Analytic Number Theory","author":"H Iwaniec","year":"2004","unstructured":"Iwaniec, H., Kowalski, E.: Analytic Number Theory. American Mathematical Society, Providence (2004)"},{"issue":"3","key":"273_CR14","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1215\/S0012-7094-01-10934-4","volume":"109","author":"T Krick","year":"2001","unstructured":"Krick, T., Pardo, L.T., Sombra, M.: Sharp estimates for the arithmetic nullstellensatz. Duke Math. J. 109(3), 521\u2013598 (2001)","journal-title":"Duke Math. J."},{"key":"273_CR15","volume-title":"Handbook of Applied Cryptography","author":"AJ Menezes","year":"2010","unstructured":"Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boco Raton (2010)"},{"issue":"2","key":"273_CR16","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1016\/j.jco.2003.08.019","volume":"20","author":"A Russell","year":"2004","unstructured":"Russell, A., Shparlinski, I.E.: Classical and quantum function reconstruction via character evaluation. J. Complex. 20(2), 404\u2013422 (2004)","journal-title":"J. Complex."},{"key":"273_CR17","first-page":"49","volume":"99","author":"N Saxena","year":"2009","unstructured":"Saxena, N.: Progress on polynomial identity testing. Bull. EATCS 99, 49\u201379 (2009)","journal-title":"Bull. EATCS"},{"key":"273_CR18","volume-title":"Progress on Polynomial Identity Testing - 2, Perspectives in Computational Complexity","author":"N Saxena","year":"2014","unstructured":"Saxena, N.: Progress on Polynomial Identity Testing - 2, Perspectives in Computational Complexity. Springer, Berlin (2014)"},{"issue":"5","key":"273_CR19","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"273_CR20","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.jsc.2013.12.005","volume":"64","author":"IE Shparlinski","year":"2014","unstructured":"Shparlinski, I.E.: Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields. J. Symb. Comput. 64, 35\u201341 (2014)","journal-title":"J. Symb. Comput."},{"key":"273_CR21","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.4171\/RMI\/909","volume":"32","author":"IE Shparlinski","year":"2016","unstructured":"Shparlinski, I.E.: Polynomial values in small subgroups of finite fields. Rev. Mat. Iberoam. 32, 1127\u20131136 (2016)","journal-title":"Rev. Mat. Iberoam."},{"issue":"3\u20134","key":"273_CR22","first-page":"207","volume":"5","author":"A Shpilka","year":"2010","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3\u20134), 207\u2013388 (2010)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"4","key":"273_CR23","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s00453-002-0975-4","volume":"34","author":"W van Dam","year":"2002","unstructured":"van Dam, W.: Quantum algorithms for weighing matrices and quadratic residues. Algorithmica 34(4), 413\u2013428 (2002)","journal-title":"Algorithmica"},{"issue":"3","key":"273_CR24","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S009753970343141X","volume":"36","author":"W van Dam","year":"2006","unstructured":"van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36(3), 763\u2013778 (2006)","journal-title":"SIAM J. Comput."},{"key":"273_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern Computer Algebra","author":"J von zur Gathen","year":"2013","unstructured":"von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0273-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0273-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0273-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T01:03:12Z","timestamp":1749862992000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0273-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,5]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["273"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0273-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,1,5]]},"assertion":[{"value":"24 February 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}