Noisy polynomial interpolation modulo prime powers. (English) Zbl 1486.11161
The paper gives a deterministic polynomial time algorithm for the sparse polynomial noisy interpolation problem over residue rings: recover an unknown \(s\)-sparse polynomial
\[
f(X)=\sum_{j=1}^{s}a_jX^{e_j} \in \mathbb{Z}_m[X],
\]
with the degrees \(e_j\) known, from approximate values of \(f(t)\) at polynomially many points \(t\in\mathbb{Z}_m\) selected uniformly at random. The case of a linear polynomial \(f(X)=aX\) with unknown \(a\) is the so-called hidden number problem, introduced by Boneh and Venkatesan, that have already been studied intensively. The authors consider the case when \(m=p^k\) is a large power of a fixed small prime, which is the new setting. The results are based on the previous works of the second author on sparse polynomial interpolation over finite fields of prime order and on bounds on exponential sums with sparse polynomials and the lattice reduction technique. The paper was motivated by increasing interest in algorithms for polynomials over residue rings modulo prime powers.
Reviewer: Armen Bagdasaryan (Madīnat al-Kuwait)
References:
| [1] | Ajtai, M.; Kumar, R.; Sivakumar, D., A sieve algorithm for the shortest lattice vector problem, (Proc. 33rd ACM Symp. on Theory of Comput. (2001), ACM), 601-610 · Zbl 1323.68561 |
| [2] | Boneh, D.; Venkatesan, R., Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, (Advances in Cryptology - CRYPTO ’96. Advances in Cryptology - CRYPTO ’96, Lect. Notes in Comp. Sci., vol. 1109 (1996), Springer-Verlag), 129-142 · Zbl 1329.94054 |
| [3] | Boneh, D.; Venkatesan, R., Rounding in lattices and its cryptographic applications, (Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms (1997), SIAM), 675-681 · Zbl 1321.94045 |
| [4] | Bourgain, J., Estimates on polynomial exponential sums, Israel J. Math., 176, 221-240 (2010) · Zbl 1205.11094 |
| [5] | Cheng, Q.; Gao, S.; Rojas, J. M.; Wan, D., Counting roots for polynomials modulo prime powers, (Proc. 13th Algorithmic Number Theory Symp.. Proc. 13th Algorithmic Number Theory Symp., Open Book Ser., vol. 2 (2019), Math. Sci. Publ.: Math. Sci. Publ. Berkeley, CA), 191-205 · Zbl 1531.11119 |
| [6] | Cheng, H.; Labahn, G., Computing all factorizations in \(\mathbb{Z}_N [ x ]\), (Proc. 2001 ACM Intern. Symp. Symb. Algebraic Comp. (2001), ACM: ACM New York), 64-71 · Zbl 1356.13029 |
| [7] | Cochrane, T.; Zheng, Z., Pure and mixed exponential sums, Acta Arith., 91, 249-278 (1999) · Zbl 0937.11031 |
| [8] | Conway, J. H.; Sloane, N. J.A., (Sphere Packings, Lattices and Groups. Sphere Packings, Lattices and Groups, Grundlehren der Mathematischen Wissenschaften, vol. 290 (1999), Springer-Verlag: Springer-Verlag New York) · Zbl 0915.52003 |
| [9] | Drmota, M.; Tichy, R., Sequences, Discrepancies and Applications (1997), Springer-Verlag: Springer-Verlag Berlin · Zbl 0877.11043 |
| [10] | Dwivedi, A.; Mittal, R.; Saxena, N., Counting basic-irreducible factors \(\operatorname{mod} p^k\) in deterministic poly-time and \(p\)-adic applications, (Proc. 34th Comp. Compl. Conf.. Proc. 34th Comp. Compl. Conf., Leibniz Int. Proc. Inform., vol. 137 (2019), Schloss Dagstuhl. Leibniz-Zent. Inform.: Schloss Dagstuhl. Leibniz-Zent. Inform. Wadern), Article 15 pp., 1-29 |
| [11] | Dwivedi, A.; Mittal, R.; Saxena, N., Efficiently factoring polynomials modulo \(p^4\), J. Symb. Comput., 104, 805-823 (2021) · Zbl 1465.13022 |
| [12] | Garcia-Morchon, O.; Rietman, R.; Tolhuizen, L.; Shparlinski, I. E., Interpolation and approximation of polynomials in finite fields over a short interval from noisy values, Exp. Math., 23, 261-270 (2014) · Zbl 1310.11117 |
| [13] | von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1055.68168 |
| [14] | von zur Gathen, J.; Hartlieb, S., Factoring modular polynomials, J. Symb. Comput., 26, 583-606 (1998) · Zbl 0913.11050 |
| [15] | von zur Gathen, J.; Shparlinski, I. E., Polynomial interpolation from multiples, (Proc. 15th ACM-SIAM Symp. on Discr. Algorithms (2004), SIAM), 209-215 · Zbl 1318.11165 |
| [16] | Grötschel, M.; Lovász, L.; Schrijver, A., (Geometric Algorithms and Combinatorial Optimization. Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics: Study and Research Texts, vol. 2 (1993), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0837.05001 |
| [17] | Gruber, P. M.; Lekkerkerker, C. G., Geometry of numbers, North-Holland Math. Library, Vol. 37 (1987), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam · Zbl 0611.10017 |
| [18] | Hammonds, T.; Johnson, J.; Patini, A.; Walker, R. M., Counting roots of polynomials over \(\mathbb{Z} / p^2 \mathbb{Z} \), Houston J. Math., 44, 1111-1119 (2018) · Zbl 1441.11301 |
| [19] | Kannan, R., Algorithmic geometry of numbers, Annu. Rev. Comput. Sci., 2, 231-267 (1987) |
| [20] | Kopp, L.; Randall, N.; Rojas, J. M.; Zhu, Y., Randomized polynomial-time root counting in prime power rings, Math. Comp., 89, 373-385 (2020) · Zbl 1446.11218 |
| [21] | Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534 (1982) · Zbl 0488.12001 |
| [22] | Micciancio, D.; Voulgaris, P., A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations, SIAM J. Comput., 42, 1364-1391 (2013) · Zbl 1275.68079 |
| [23] | Mit’kin, D. A., Estimates and asymptotic formulas for rational exponential sums that are nearly complete, Math. USSR, 50, 513-532 (1985), (translated from Matem. Sbornik 122 (4) (1983) 527-545) · Zbl 0554.10022 |
| [24] | Nguyen, P. Q., Public-key cryptanalysis, (Recent Trends in Cryptography. Recent Trends in Cryptography, Contemp. Math., vol. 477 (2009), Amer. Math. Soc.), 67-119 · Zbl 1180.94059 |
| [25] | Nguyen, P. Q.; Stern, J., Lattice reduction in cryptology: An update, (Proc. 13th Algorithmic Number Theory Symp. Proc. 13th Algorithmic Number Theory Symp, Lect. Notes in Comp. Sci., vol. 1838 (2000), Springer-Verlag: Springer-Verlag Berlin), 85-112 · Zbl 0980.94010 |
| [26] | Nguyen, P. Q.; Stern, J., The two faces of lattices in cryptology, (Cryptography and Lattices. Cryptography and Lattices, Lect. Notes in Comp. Sci., vol. 2146 (2001), Springer-Verlag: Springer-Verlag Berlin), 146-180 · Zbl 1006.94531 |
| [27] | Regev, O., On the complexity of lattice problems with polynomial approximation factors, (The LLL Algorithm: Surveys and Applications (2010), Springer-Verlag), 475-496 · Zbl 1237.68102 |
| [28] | Schnorr, C. P., A hierarchy of polynomial time basis reduction algorithms, Theoret. Comput. Sci., 53, 201-224 (1987) · Zbl 0642.10030 |
| [29] | Shparlinski, I. E., On exponential sums with sparse polynomials and rational functions, J. Number Theory, 60, 233-244 (1996) · Zbl 0881.11081 |
| [30] | Shparlinski, I. E., Sparse polynomial approximation in finite fields, (Proc. 33rd ACM Symp. on Theory of Comput (2001), ACM), 209-215 · Zbl 1323.68321 |
| [31] | Shparlinski, I. E., Playing hide-and-seek with numbers: The hidden number problem, lattices and exponential sums, (Public-Key Cryptography, Proc. Symp. in Appl. Math, 62 (2005), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 153-177 · Zbl 1208.11134 |
| [32] | Shparlinski, I. E.; Winterhof, A., Noisy interpolation of sparse polynomials in finite fields, Appl. Algebra Engrg. Comm. Comput., 16, 307-317 (2005) · Zbl 1131.11077 |
| [33] | Sircana, C., Factorization of polynomials over \(\mathbb{Z} / ( p^n )\), (Proc. 2019 ACM Intern. Symp. Algebraic Comp (2019), ACM), 405-412 · Zbl 1458.13028 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
