I have a short question regarding the Miller Rabin test:
Suppose we want to test the primality of $n \ge 3$. When we pick a random integer $a$ from $\{1,\ldots,n-1\}$ and see that $a$ is a witness to the primality of $n$, why do we not update the set $\{1,\ldots,n-1\}$ to $\{1,\ldots,n-1\} \setminus {a}$, i.e. delete $a$? I have looked in multiple text books and on Wikipedia, this is never done anywhere, but if I am not mistaken this is necessary to ensure that the test works properly. Could you explain this to me?
If there are $k$ of $n-1$ witness to give the result that $n$ is not a prime, then test $u$ random number, we have $(\frac{n-1-k}{n-1})^u$ probability to fail. If we restrict that these numbers are distinct, then we have $\binom{n-1-k}{u}/\binom{n}{u}$ probability to fail. Since $u\ll n-1-k$ (If $n$ is large, then we should only test $O(\log^2 n)$ times), this two probability is almost same (cause $\binom{n-1-k}{u}/\binom{n}{u}=(n-1-k)^{\underline u}/n^{\underline u}$, where $n^{\underline u}=n(n-1)\cdots(n-u+1)$).
From another perspective, if we choose random numbers between $[1,n]$, then we need about $\Theta(\sqrt n)$ times to get two same number (the birthday paradox). In Miller-Rabin test you actually test $u\ll\sqrt n$ times, so it's unnecessary to delete numbers already tested.
These explanation may not work for small $n$, but if $n$ is small we can only test some fixed numbers, see Wikipedia.