论文标题
嘈杂的多项式插值模型素数
Noisy polynomial interpolation modulo prime powers
论文作者
论文摘要
我们考虑恢复未知的$ s $ -s $ -s $ -s $ s $ s $ s $ f（x）$的{ \ Mathbb z_ {p^k} $。对于残留物modulo而言，类似的结果是一个大的prime $ p $，但是Prime Power Modulus $ P^K $的情况是小$ P $和大$ K $，是新的，需要不同的技术。我们给出了确定性的多项式时间算法，该算法几乎给出了超过一半的$ f（t）$，以足够多的随机选择点$ t \ in \ mathbb z_ {p^k}^*$，恢复$ f（x）$。
We consider the {\it noisy polynomial interpolation problem\/} of recovering an unknown $s$-sparse polynomial $f(X)$ over the ring $\mathbb Z_{p^k}$ of residues modulo $p^k$, where $p$ is a small prime and $k$ is a large integer parameter, from approximate values of the residues of $f(t) \in \mathbb Z_{p^k}$. Similar results are known for residues modulo a large prime $p$, however the case of prime power modulus $p^k$, with small $p$ and large $k$, is new and requires different techniques. We give a deterministic polynomial time algorithm, which for almost given more than a half bits of $f(t)$ for sufficiently many randomly chosen points $t \in \mathbb Z_{p^k}^*$, recovers $f(X)$.
