I have been studying the Miller-Rabin Primality Test, and am interested in implementing a code in Python to count witnesses and liars. In the basic code to determine if a number is probably prime or composite, I would like to incorporate 1) and 2) below to better understand witnesses compared to liars for n values:
$1)$ $a$ to be tested for all values of $a$ from $1<a<n-1$, not random as it is currently coded.
$2)$ Then for every $a$ in $1)$ above, a count of how many of those $a's$ are witnesses and how many are non-witnesses(liars)
My ultimate goal is to use this, I'm sure with more modifications to the code, to compare to the Theorem: If n is odd, composite, and n>9, then at least 75% of the elements in $(\mathbb Z/n\mathbb Z)^x$ are Miller-Rabin witnesses.
The Python code I am using is as follows:
from random import randrange def probably_prime(n, k): """Return True if n passes k rounds of the Miller-Rabin primality test (and is probably prime). Return False if n is proved to be composite. """ if n < 2: return False r, m = 0, n - 1 while m % 2 == 0: r += 1 m //= 2 for _ in range(k): a = randrange(2, n - 1) x = pow(a, m, n) if x == 1 or x == n - 1: continue for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True