推荐 3.5
Conf: 50%
该论文研究了数论变换(NTT)的不确定性原理,并证明了在某些素数条件下,非零函数与其NTT变换的支撑集大小之和至少为q+1(q为给定素数,p为满足p≡1 mod q的素数)。这意味着一稀疏函数(k-稀疏)的变换支撑集至少为q-k+1。进一步,作者还证明了在p=q^{O(1)}范围内的素数平均意义上的概率版本不确定性原理。作为应用,该原理被用于构造一个黑盒身份测试算法,用于验证至多k-稀疏、度数不超过d的指数多项式,在q适度大于k时具有零声音误差。该研究为多项式恒等测试提供了新的理论工具,对密码学、编码理论等领域中涉及NTT的应用有潜在影响。
💡 推荐理由: 该论文为NTT提供了严格的不确定性下界,可应用于多项式身份测试,对于密码学中涉及稀疏多项式的安全分析具有理论价值。
🎯 建议动作: 研究跟进
排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)