MathOverflow

« first day (3222 days earlier) ← previous day next day → last day (745 days later) »

6:08 AM

Does anyone know if there's a stronger and more general bound than https://math.dartmouth.edu/~carlp/PDF/paper88.pdf for Miller-Rabin for integers chosen uniformly at random? Or is that still the best one known?

This post on Cryptography seems to be related: Average false-positive rate for a round of Miller–Rabin

Q: Average false-positive rate for a round of Miller–Rabin

I'm aware that the Miller–Rabin primality test will claim primality for a composite number with at most a $\frac{1}{4}$ chance, assuming a random, odd composite $n$ and a random witness $a$ chosen uniformly in the range $[2,n-1)$. What is the actual average chance that that the test falsely claim...