Abstract
We consider the problem of recovering (that is, interpolating) and identity testing of a “hidden” monic polynomial f, given an oracle access to \({f}{(x)}^e\) for \(x\in \mathbb {F}_q\), where \(\mathbb {F}_q\) is finite field of q elements (extension fields access is not permitted). The naive interpolation algorithm needs \(O(e \deg f)\) queries and thus requires \(e\deg f<q\). We design algorithms that are asymptotically better in certain cases; requiring only \(e^{o(1)}\) queries to the oracle. In the randomized (and quantum) setting, we give a substantially better interpolation algorithm, that requires only \(O(\deg f \log q)\) queries. Such results have been known before only for the special case of a linear f, called the hidden shifted power problem. We use techniques from algebra, such as effective versions of Hilbert’s Nullstellensatz, and analytic number theory, such as results on the distribution of rational functions in subgroups and character sum estimates.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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–178 (1997)
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13(4), 850–864 (1984)
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–297. Springer, Berlin (1996)
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–29 (2008)
Bourgain, J., Garaev, M.Z., Konyagin, S.V., Shparlinski, I.E.: On the hidden shifted power problem. SIAM J. Comput. 41(6), 1524–1557 (2012)
Chang, M.-C.: Factorization in generalized arithmetic progressions and application to the Erdős-Szemerédi sum-product problems. Geom. Funct. Anal. 13(4), 720–736 (2003)
Cilleruelo, J., Shparlinski, I.: Concentration of points on curves in finite fields. Monatshefte Math. 171(3–4), 315–327 (2013)
Crandall, R., Pomerance, C.: Prime numbers: a computational perspective. Springer, New York (2001)
Damgård, I.B.: On the randomness of legendre and jacobi sequences. In: Advances In: Goldwasser, S. (ed.) Cryptology CRYPTO 88, pp. 163–172. Springer, Berlin (1990)
D’Andrea, C., Krick, T., Sombra, M.: Heights of varieties in multiprojective spaces and arithmetic nullstellensätze. Ann. Sci. l’ENS 46, 549–627 (2013)
Gómez-Pérez, D., Shparlinski, I.E.: Subgroups generated by rational functions in finite fields. Monat. Math. 176, 241–253 (2015)
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–219. ACM (1996)
Iwaniec, H., Kowalski, E.: Analytic Number Theory. American Mathematical Society, Providence (2004)
Krick, T., Pardo, L.T., Sombra, M.: Sharp estimates for the arithmetic nullstellensatz. Duke Math. J. 109(3), 521–598 (2001)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boco Raton (2010)
Russell, A., Shparlinski, I.E.: Classical and quantum function reconstruction via character evaluation. J. Complex. 20(2), 404–422 (2004)
Saxena, N.: Progress on polynomial identity testing. Bull. EATCS 99, 49–79 (2009)
Saxena, N.: Progress on Polynomial Identity Testing - 2, Perspectives in Computational Complexity. Springer, Berlin (2014)
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
Shparlinski, I.E.: Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields. J. Symb. Comput. 64, 35–41 (2014)
Shparlinski, I.E.: Polynomial values in small subgroups of finite fields. Rev. Mat. Iberoam. 32, 1127–1136 (2016)
Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3–4), 207–388 (2010)
van Dam, W.: Quantum algorithms for weighing matrices and quadratic residues. Algorithmica 34(4), 413–428 (2002)
van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36(3), 763–778 (2006)
von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013)
Acknowledgements
The authors are very grateful to the referees for the very careful reading of the manuscipt which helped to remove some imprecisions and also improved the quality of the exposition. This research was supported in part by the Hungarian Scientific Research Fund (OTKA) Grant NK105645 (for G.I.); Singapore Ministry of Education and the National Research Foundation Tier 3 Grant MOE2012-T3-1-009 (for G.I. and M.S.); the Hausdorff Grant EXC-59 (for M.K.); European Commission IST STREP Project QALGO 600700 and the French ANR Blanc Program Contract ANR-12-BS02-005 (for M.S.); Research-I Foundation CSE and Hausdorff Center Bonn (for N.S.); the Australian Research Council Grant DP140100118 (for I.S.).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Rights and permissions
About this article
Cite this article
Ivanyos, G., Karpinski, M., Santha, M. et al. Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields. Algorithmica 80, 560–575 (2018). https://doi.org/10.1007/s00453-016-0273-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-016-0273-1
Keywords
- Hidden polynomial power
- Black-box interpolation
- Nullstellensatz
- Rational function
- Deterministic algorithm
- Randomised algorithm
- Quantum algorithm