Miller-Rabin Witness Round

Problem

Run one Miller-Rabin round for odd n > 2 with the given base and report whether n passes.

Write n - 1 as 2^s * d and test pow(base, d, n): n passes if that value is 1 or n - 1, or if some repeated squaring reaches n - 1. Return False for n < 2, True for n = 2, and True when base is a multiple of n.

Hint

Composites that pass one base are pseudoprimes; a single round never certifies primality.

Test cases

case 1

in: [13,2]

expected: true

case 2

in: [561,2]

expected: false

case 3

in: [2047,2]

expected: true

case 4

in: [2,2]

expected: true

case 5

in: [15,7]

expected: false

Starter codePython

def miller_rabin_round(n, base):
    # Your code here
    pass

5 test cases · run your code against them in the editor