| ▲ | apnorton 4 hours ago | |
The linked post points to OEIS A014233[1] for establishing their set of Miller-Rabin[2] bases, though it's actually possible to find smaller sets. I remember asking about this on StackExchange some years ago [3], which pointed me to Wojciech Izykowski's site[4], on which "best known" base sets are tracked. For example, instead of considering the four bases {2,3,5,7} to cover all 32-bit integers, it would suffice to consider the three integers {4230279247111683200, 14694767155120705706, 16641139526367750375}. This becomes more interesting the higher the bound you seek --- for example, instead of checking the first 11 prime bases for 64-bit integers, you only need to check the seven bases: 2, 325, 9375, 28178, 450775, 9780504, 1795265022. [2]: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality... [3]: https://math.stackexchange.com/questions/1004807/ [4]: https://miller-rabin.appspot.com or https://web.archive.org/web/20260225175716/https://miller-ra... if hugged to death | ||