Interpolation and approximation of polynomials in finite fields over a short interval from noisy values. (English) Zbl 1310.11117
Summary: We consider a modification of the noisy polynomial interpolation problem of recovering an unknown polynomial \(f(X)\in \mathbb Z[X]\) from approximate values of the residues of \(f(t)\) modulo a prime \(p\) at polynomially many points \(t\) taken from a short interval.
MSC:
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 11Y16 | Number-theoretic algorithms; complexity |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68W30 | Symbolic computation and algebraic computation |
References:
| [1] | DOI: 10.1007/978-3-642-03356-8_20 · Zbl 1252.94040 · doi:10.1007/978-3-642-03356-8_20 |
| [2] | Boneh [Boneh and Venkatesan 96] D., Advances in Cryptology - CRYPTO ’96 pp 129– (1996) |
| [3] | Boneh [Boneh and Venkatesan 97] D., Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms pp 675– (1997) |
| [4] | Chang [Chang et al. 11 M.-C., Points on Curves in Small Boxes and Applications |
| [5] | DOI: 10.1007/s00209-011-0959-7 · Zbl 1285.11027 · doi:10.1007/s00209-011-0959-7 |
| [6] | DOI: 10.1112/S0024610702004040 · Zbl 1106.11032 · doi:10.1112/S0024610702004040 |
| [7] | DOI: 10.1007/978-1-4757-6568-7 · doi:10.1007/978-1-4757-6568-7 |
| [8] | DOI: 10.1007/978-3-642-78240-4 · doi:10.1007/978-3-642-78240-4 |
| [9] | Gruber [Gruber and Lekkerkerker 87] P. M., Geometry of Numbers, 2. ed. (1987) |
| [10] | DOI: 10.1007/BF02418278 · JFM 25.0817.02 · doi:10.1007/BF02418278 |
| [11] | DOI: 10.1007/s00605-004-0277-9 · Zbl 1098.11046 · doi:10.1007/s00605-004-0277-9 |
| [12] | Iwaniec [Iwaniec and Kowalski 04] H., Analytic number theory (2004) · Zbl 1059.11001 |
| [13] | DOI: 10.1017/S0004972713000324 · Zbl 1362.11048 · doi:10.1017/S0004972713000324 |
| [14] | DOI: 10.1007/BF01457454 · Zbl 0488.12001 · doi:10.1007/BF01457454 |
| [15] | Lidl [Lidl and Niederreiter 97] R., Finite fields (1997) |
| [16] | Micciancio [Micciancio 98] D., On the Hardness of the Shortest Vector Problem |
| [17] | DOI: 10.1137/100811970 · Zbl 1275.68079 · doi:10.1137/100811970 |
| [18] | Montgomery [Montgomery 94] H. L., Ten Lectures on the Interface between Analytic Number Theory and Harmonic Analysis (1994) · Zbl 0814.11001 · doi:10.1090/cbms/084 |
| [19] | Nguyen [Nguyen 09] P. Q., Recent Trends in Cryptography |
| [20] | Nguyen [Nguyen and Stern 00] P. Q., Algorithmic Number Theory, ANTS-IV |
| [21] | Regev [Regev 10] O., The LLL Algorithm: Surveys and Applications pp 475– (2010) |
| [22] | Shparlinski [Shparlinski 01]] I.E., STOC’01, July 6–8, 2001, Hersonissos, Crete, Greece. pp 209– (2001) |
| [23] | Shparlinski [Shparlinski 05] I.E., Public-Key Cryptography |
| [24] | DOI: 10.1007/s00200-005-0180-1 · Zbl 1131.11077 · doi:10.1007/s00200-005-0180-1 |
| [25] | Gathen [Von zur Gathen and Shparlinski 04] J.vonzur, Proc. 15th ACM-SIAM Symposium on Discrete Algorithms pp 1125– (2004) |
| [26] | Wooley [Wooley 11] T.D., Multigrade Efficient Congruencing and Vinogradov’s Mean Value Theorem (2011) · Zbl 1328.11087 |
| [27] | DOI: 10.4007/annals.2012.175.3.12 · Zbl 1267.11105 · doi:10.4007/annals.2012.175.3.12 |
| [28] | DOI: 10.1215/00127094-2079905 · Zbl 1312.11066 · doi:10.1215/00127094-2079905 |
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.
