Question about Modified Miller-Rabin Test?

Question

A few months ago I decided to write my own custom prime number generator. One of the tests I use is a modified Miller-Rabin test that tests the number against base 2 and then only tests random odd numbers, instead of completely random numbers. I figured this might get better probability than 1/4^k for k rounds since if we factor out all the powers of 2 from a random base there should be an odd remainder. Does this actually have better probability bounds, or would it be about the same, and how would we prove that? Also, even if it had the same probability bounds, would this test at least be faster in the average case scenario for random prime generation since the base 2 test weeds out almost all composites and the computer doesn't have to generate as many random numbers?

This is my code. I previously defined the functions MR(p, a, s, d) and extract(a, b) and a class PrimeList which uses trial division to generate a list of prime numbers; small_primes is the one instance I defined in the program.

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))
```

Answer 1

So this is what I found after doing what @J_H suggested with modifying the code between ranging across all numbers less than the number being tested and ranging across odds only:

I used the test probable_prime above, a new test probable_prime_2 that is the same but replaces the random odd number with a random number between 3 and p-2, and a separate Miller-Rabin function that runs the vanilla Miller-Rabin test.

I found that when I generated a million random odd numbers between 10**18 and 10**19, none of them were base 2 pseudoprimes so unfortunately random number generation was not helpful for comparing the tests' accuracies. To compare accuracy with a counter this way, I used OEIS A014233, which is a very specific list of pseudoprimes so the results may not generalize. I compared the counters for how long it takes probable_prime to get a witness for the compositeness of the numbers on the list. I ran both tests over the list four times, and found that:

• Usually probable_prime and probable_prime_2 both got it on the first try, and occasionally both on the second try.
• When one test took longer, it was usually, though not always, probable_prime_2.

I also compared probable_prime with the vanilla Miller-Rabin test (and deleted the trial division at the beginning for extra control) and found that probable_prime is slightly faster than vanilla Miller-Rabin at detecting pseudoprimes. Most likely this is because of the extra time the computer took to generate the random number for the first round of Miller-Rabin. However, for the numbers on the OEIS list, vanilla Miller-Rabin is a lot faster.

I guess a preliminary conclusion from this is that testing base 2 and then only odds seems to give slightly better probability bounds on the numbers I have tried. I suspect this is because if p is a base 2 pseudoprime and a is an even strong liar, then a is either a power of 2 or all the 2s can be factored out of a to give an odd strong liar. However, I still don't know if this holds up for cryptgraphically large primes, and it also seems like vanilla Miller-Rabin is faster when p is a base 2 pseudoprime.