[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields

  • Published:
Algorithmica Aims and scope Submit manuscript

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.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. 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)

  2. Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13(4), 850–864 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  3. 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)

  4. 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)

  5. 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)

    Article  MathSciNet  MATH  Google Scholar 

  6. 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)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cilleruelo, J., Shparlinski, I.: Concentration of points on curves in finite fields. Monatshefte Math. 171(3–4), 315–327 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  8. Crandall, R., Pomerance, C.: Prime numbers: a computational perspective. Springer, New York (2001)

  9. 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)

  10. 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)

    MATH  Google Scholar 

  11. Gómez-Pérez, D., Shparlinski, I.E.: Subgroups generated by rational functions in finite fields. Monat. Math. 176, 241–253 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. 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)

  13. Iwaniec, H., Kowalski, E.: Analytic Number Theory. American Mathematical Society, Providence (2004)

    Book  MATH  Google Scholar 

  14. Krick, T., Pardo, L.T., Sombra, M.: Sharp estimates for the arithmetic nullstellensatz. Duke Math. J. 109(3), 521–598 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  15. Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boco Raton (2010)

    MATH  Google Scholar 

  16. Russell, A., Shparlinski, I.E.: Classical and quantum function reconstruction via character evaluation. J. Complex. 20(2), 404–422 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  17. Saxena, N.: Progress on polynomial identity testing. Bull. EATCS 99, 49–79 (2009)

    MathSciNet  MATH  Google Scholar 

  18. Saxena, N.: Progress on Polynomial Identity Testing - 2, Perspectives in Computational Complexity. Springer, Berlin (2014)

    Google Scholar 

  19. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  20. 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)

    Article  MathSciNet  MATH  Google Scholar 

  21. Shparlinski, I.E.: Polynomial values in small subgroups of finite fields. Rev. Mat. Iberoam. 32, 1127–1136 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  22. 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)

    MathSciNet  MATH  Google Scholar 

  23. van Dam, W.: Quantum algorithms for weighing matrices and quadratic residues. Algorithmica 34(4), 413–428 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  24. van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36(3), 763–778 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  25. von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013)

    Book  MATH  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Igor E. Shparlinski.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0273-1

Keywords

Mathematics Subject Classification

Navigation