高效的素数生成

Question

分析版本的复图

在所有 Covid 停机期间，我一直在做一些数论，我想我发现了一种非常有趣（如果不是新颖的）检测素性的算法。我在我的 LinkedIn 页面上发布了我的文章，您无需注册或进行任何操作。

https://www.linkedin.com/pulse/efficient-prime-number-generation-christopher-wolfe/

我只想知道这种技术是否已经为人所知，因为它非常快（恒定时间）并且尺寸非常紧凑。不久前我进行了更深入的研究，您可以在我的博客上阅读。

http://jasuto.com/ideas/primes/

获得一些反馈并验证这是新的会很棒。我还有很多要发布，但我想我会开始轻松:)

如果您不想阅读本文，这里是演示代码。我见过很多质数实现，但没有 O(1) 或这么小的......

# Copyright 2021 Christopher Wolfe (chris@jasuto.com)
# Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
# The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


# constant time primality testing, along with a fairly concise prime
# number generator.  


# bignum division handles flooring
def floor(n):
    return n


def alg_prime_q(ni):
    n = ni - 1
    return floor((n*2**(n + 1) + 2)//(2*n - (-1)**n + 3)) - floor((n*2**(n + 1) - 2)//(2*n - (-1)**n + 3))


# cos(? x) + i sin(? x)
def phasor(n):
    return ((n + 1) & 1) << 1 - 1


# this will include Fermat pseudoprimes as well
def prime_q(n):
    q = n - 1
    s = q * (1 << (q + 1))
    t = (q << 1) - phasor(q) + 3
    return floor((s + 2) // t) - floor((s - 2) // t)


# returns all primes < n
def primes(n):
    return [i for i in range(3, n, 2) if prime_q(i)]

res = primes(1000)
print(res)


print('done')

Answer 1

我想我可以证明这是我在评论中链接的中国假设的一个版本。

让我们在没有位移的情况下简化版本。

def alg_prime_q(ni):
    n = ni - 1
    return floor((n*2**(n + 1) + 2)//(2*n - (-1)**n + 3)) - floor((n*2**(n + 1) - 2)//(2*n - (-1)**n + 3))

我将假设 ni 是奇数，因为这大大简化了表达式并且也是唯一有趣的情况（确定偶数的素性很容易）。

在这种情况下， (-1)**n = 1

floor((n*2**(n + 1) + 2)//(2*n - 1 + 3)) - floor((n*2**(n + 1) - 2)//(2*n - 1+ 3))

2 也是分子和分母的一个因数，所以这进一步简化为：

floor((n*2**n  + 1)//(n + 1)) - floor((n*2**(n ) - 1)//(n + 1))

将 ni 替换为 n-1 ：

floor((ni-1)*2**(ni-1)  + 1)//ni - floor((ni-1)*2**(ni-1) - 1)//ni

声明是，如果ni除法((ni-1)*2**(ni-1) + 1)次数多于ni除法次数，则 ni 是素数 ((ni-1)*2**(ni-1) - 1)。

观察到两者的差是 2，所以要发生这种情况 (ni-1)*2**(ni-1) + 1)%ni必须是 1 或 0。

让我们分别检查这两个：案例 1，

(ni-1)*2**(ni-1) + 1 = 1 (mod ni)
ni*2**(ni-1)-*2**(ni-1) = 0 (mod ni)
2**(ni-1) = 0 (mod ni)

由于 n 是奇数，它永远不可能是 2 的幂，所以这种情况永远不会发生

案例 2。

(ni-1)*2**(ni-1) + 1 = 0 (mod ni)
ni*2**(ni-1)-2**(ni-1) + 1 = 0 (mod ni)
2**(ni-1) + 1 = 0 (mod ni)
2**ni + 2 = 0 (mod ni)

这就是中国的假设。