关于改良米勒-拉宾检验的问题

Question

几个月前，我决定编写自己的自定义素数生成器。我使用的测试之一是修改后的 Miller-Rabin 测试，该测试以 2 为底测试数字，然后仅测试随机奇数，而不是完全随机的数字。我认为这可能比 k 轮的 1/4^k 获得更好的概率，因为如果我们从随机基数中分解出 2 的所有幂，应该有一个奇数余数。这实际上是否具有更好的概率界限，或者大致相同，我们如何证明这一点？另外，即使它具有相同的概率范围，在随机素数生成的平均情况下，此测试至少会更快吗，因为基数 2 测试淘汰了几乎所有复合材料，并且计算机不必生成尽可能多的随机数？

这是我的代码。我之前定义了函数 MR(p, a, s, d) 和 extract(a, b) 以及类 PrimeList，它使用试除法生成素数列表； Small_primes 是我在程序中定义的一个实例。

def probable_prime(p, k = 5): #Quick custom-made primality test for large primes
    #Test small cases
    if p <= 5000:
        return small_primes.is_prime(p)

    #Find s, d
    (s, d) = extract(2, p - 1)

    #Test for divisibility by 2
    if s == 0:
        return False

    #Quick trial division for small primes
    for i in small_primes.odd_primes(p.bit_length() // 2):
        if p % i == 0:
            return False

    #Miller-Rabin test for base 2
    if not MR(p, 2, s, d):
        return False

    #Miller-Rabin test for odds only
    return all(MR(p, random.randint(2, p // 2) * 2 - 1, s, d) for i in range(k))