Uncertainty Principles for the Number Theoretic Transform

该论文研究了数论变换（NTT）的不确定性原理，并证明了在某些素数条件下，非零函数与其NTT变换的支撑集大小之和至少为q+1（q为给定素数，p为满足p≡1 mod q的素数）。这意味着一稀疏函数（k-稀疏）的变换支撑集至少为q-k+1。进一步

历史摘要 · 未重新核验 · arXiv cs.CR