Search code examples
algorithmprimality-test

Miller Rabin primality test two types?

I encountered two types of Miller Rabin primality test methods suddenly. One which uses randoms and another does not use randoms.

Is there a hidden random generation inside the second one or what? Thank you.

Solution

  • The second one is a deterministic variant of the Miller-Rabin primality test. Instead of using "witness" numbers generated from random numbers, a list of primes that are known to be sufficient is used instead:

    When the number n to be tested is small, trying all a < 2(ln n)2 is not necessary, as much smaller sets of potential witnesses are known to suffice"

    if n < 3,825,123,056,546,413,051, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, and 23.

    This is the list of primes in alist in the linked source code.