首个 x^o(1) 时间判定素数奇偶性的确定性算法发布

xennygrimmato_ · x · 2026-11-06

作者发布了一个确定性算法,可在 x^o(1) 时间内判断不超过 x 的素数个数是奇还是偶。若 x 有 n 个比特,此前最优需 √x = 2^(n/2) 时间(对 n 指数级),新算法降至 2^(n/√log n)。核心技术思路:基于 Polymath4(Tao、Croot、Helfgott)对短区间奇偶性的结果,但原方法需对每个 d ≤ √x 求 Möbius 函数 μ(d);作者发现 mod 2 下 μ(d) 等价于判断 d 是否 squarefree——同样的问题但规模减半,迭代 log n 次后 π(x) mod 2 归约为一次计数。论文已发布。

所属事件:素数奇偶性判定复杂度获突破算法由Claude Code写成(4 条相关)→

原文链接 →

「研究」频道最新

更多「研究」频道 AI 资讯 →