1
$\begingroup$

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))
```
$\endgroup$
5
  • $\begingroup$ "better probability bounds?" You tell us. Instrument the code with counters and see how it fares, with & without. $\endgroup$
    – J_H
    Commented Jul 31, 2023 at 20:49
  • $\begingroup$ For answering your question you have to consider two points: (1) Are the numbers you test random or given (to you by someone you might not trust)? (2) Are you speaking about the "real" value of the failure probability or about what upper bound one can prove for the failure probability (i.e., do you just want to be "pretty sure" that you got a prime, or do you have to pass an evaluation/certification like FIPS or Common Criteria)? If a random 1024-bit number passes one Fermat test, I'd bet everything that it's a prime. If it's given to me, not. $\endgroup$
    – j.p.
    Commented Aug 1, 2023 at 7:17
  • $\begingroup$ Using a small base for your first MR-test surely helps for the performance, as the exponentiation should be faster and it weeds out (rounded) 100% of the non-primes. For base 2 you can make it extra fast, and if you consider side-channels easier secure. This even holds if you have to do an additional MR-test to get the right provable security bounds for an evaluation. $\endgroup$
    – j.p.
    Commented Aug 1, 2023 at 7:21
  • 2
    $\begingroup$ Taking only odd bases after the first test does not help improve the (provable or not) failure rates. You should just never take numbers that are multiplicative-ly dependent, like $m$, $n$ and $m\cdot n$, or $m$ and $m^n$. $\endgroup$
    – j.p.
    Commented Aug 1, 2023 at 7:25
  • $\begingroup$ If the goal is to increase the speed of the test, and for p>23, it may pay to check gcd(p,223092870)==1, which tests divisibility by the first 9 primes. Independently: see this reference. $\endgroup$
    – fgrieu
    Commented Aug 31, 2023 at 8:24

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Update: as I am running the tests through the lists again and again, it is starting to seem pretty random whether probable_prime or probable_prime_2 gets it faster if one takes longer than the other, so it's actually hard to say if only testing odds actually gives better probability bounds. $\endgroup$ Commented Aug 1, 2023 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.