September 27th
Today I learned why the Solovay–Strassen (probable) primality test can give confidence of $\left(\frac12\right)^{\text{witnesses}}.$ The primality test for some integer $N$ is done by choosing a random value $a\in(\ZZ/N\ZZ)^\times$ and then comparing the values of\[a^{(N-1)/2}\equiv\left(\frac aN\right)\pmod N.\]Note on the right-hand side we are computing the Jacobi symbol, which can be done quickly using the Euclidean algorithm and quadratic reciprocity; the left-hand side can be done quickly using modular exponentiation via repeated squaring.
For this, assume there exists at least one witness $a\in(\ZZ/N\ZZ)^\times.$ We show that at least half of all elements of $(\ZZ/N\ZZ)^\times$ are witnesses. Indeed, suppose $b$ is a liar; that is, we know\[b^{(N-1)/2}\equiv\left(\frac bN\right)\pmod N.\]However, both $(\bullet)^{(N-1)/2}$ and $\left(\frac\bullet N\right)$ are completely multiplicative, so we see that\[(ab)^{(N-1)/2}=a^{(N-1)/2}\cdot b^{(N-1)/2}\equiv a^{(N-1)/2}\left(\frac bN\right)\not\equiv\left(\frac aN\right)\left(\frac bN\right)=\left(\frac{ab}N\right)\pmod N.\]It follows that $ab$ is also a witness. So for every liar, there exists a witness by multiplying by $a,$ and because multiplication by $a$ is a bijection (it's invertible because $a^{-1}$ exists), this means that at least half of all of $(\ZZ/N\ZZ)^\times$ is a witness.
I don't currently know why a single witness should exist, but it's claimed all over the place.