One Trial of Rabin-Miller Test

Question

What is the probability that we discover $n=1729$ is composite after $1$ trial of the Rabin-Miller Test?

While I know that there are at least $\frac{3}{4}$ of the $a$'s $\in [2,n-2]$ which will discover $n$ is composite after $1$ trial, I don't know how to compute this probability explicitly.

Answer 1

By explicit calculation, the number of bases $a \in [2, 1727]$ for which $1729$ is a strong pseudo-prime is $160$, with the smallest $a=9$ and the largest $a=1720$. So the probability of success is $1-160/1726\approx90.7\%$

Here is the table:

Bases a=2..1727 for which 1729 is a strong pseudo-prime
    9   10   12   16   69   74   75   81   90   92
  100  103  108  120  129  144  160  166  172  173
  181  191  192  235  256  257  263  282  289  302
  335  347  355  363  365  374  376  386  402  426
  433  438  439  443  484  493  529  536  545  555
  562  563  568  575  584  621  625  638  649  653
  654  666  675  690  699  706  729  740  750  757
  797  802  807  809  810  828  829  831  841  857
  872  888  898  900  901  919  920  922  927  932
  972  979  989 1000 1023 1030 1039 1054 1063 1075
 1076 1080 1091 1104 1108 1145 1154 1161 1166 1167
 1174 1184 1193 1200 1236 1245 1286 1290 1291 1296
 1303 1327 1343 1353 1355 1364 1366 1374 1382 1394
 1427 1440 1447 1466 1472 1473 1494 1537 1538 1548
 1556 1557 1563 1569 1585 1600 1609 1621 1626 1629
 1637 1639 1648 1654 1655 1660 1713 1717 1719 1720

160/1726 = 9.27%

There is a complicated formula for the number of strong pseudo-primes given in Crandall & Pomerance: Prime Numbers, A Computational Perspective, 2nd ed., exercise 3.15, which gives for $n=7\times 13 \times 19,n-1=2^6\times 3^3$ the value $S(n)=2\times 3\times 3 \times 9 = 162,$ including the trivial bases $a=\pm 1 \bmod n.$

Answer 2

There are $\phi(1729) = \phi(7\cdot 13\cdot 19) = 6\cdot 12\cdot 18 = 1296$ numbers coprime to $1729$ in $[1,1728]$, and exactly $\frac 18$ of these are false witnesses of primality under the Miller-Rabin test -- $1296/8=162$.

However this includes $1$ and $1728$, so there are $160$ false witnesses in your given range.

The numbers not coprime to $1729$ will also show $1729$ composite, which reduces the probability of false witness to $160/1726 \approx 9.27\%$

Interestingly, all the Miller-Rabin evaluations for coprime numbers finish "early" in the process. By the time you evaluate $(a^{54})^2 = a^{108}$, all results for coprime numbers are $1 \bmod 1729$ (whether false witness or not).