Deterministic Primality Testing for Limited Bit Width

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.

[1]: https://oeis.org/A014233

[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

If I understand correctly, Baillie-PSW has been shown to be correct for all integers < 2^64, so for 64-bit ints you might use (some variant of) that instead of M-R.

Edited to add: Sieving has got to be much faster than M-R if you want all primes of a certain size. You would use M-R or Baillie-PSW if you are testing them one at a time.

I like to factor large numbers mentally as a keep my brain awake exercise (one task I set for myself is to see if I can factor my odometer reading—currently a bit over 20,000—before I reach the next mile.

Many of my strategies are based around working with smaller numbers whenever possible. So for example, if the number in question is 20,113, I can easily dispose of 2, 3, 5 and 11 as possibilities. For 7, I note that I’m “almost” at 21,000 so I will check 21,000-20,113 for divisibility by 7. 887 is trivially not divisible by 7 since if it were 88 would have to be a multiple of 7 and I can tell it’s not.

This leads into my “invention”¹ of checking from the right side of the number for divisibility. With checking for 20,113 being divisible by 13, I can start at the right, bring myself down to 201 which I can either subtract 91 and get 110 from or go to the left and take away 130 and get 71, either way I can see that 13 isn’t a factor.

I also will use addition when it’s more convenient. So for 17 I’ll add 17 then divide by 10 to get 2013, repeat and get 203, and again to get 23. Not a multiple of 17.

In the process of doing this, you end up learning the multiples² of the 2-digit primes pretty well and I’m reaching the point where I can sight-factor a three-digit number almost as easily as I can a two-digit number.

The right hand method would be simple to implement digitally since the only operations necessary are subtraction, shifting right to clear out right-hand zeros and a comparison. So checking 11100111 for divisibility by 101 would be

    11100111 - 101
    11100010 shift right 1
    1110001 -101
    110110 shift right 1
    11011 -101 and shift right
    1011 monkey brain sees it’s not divisible but computer keeps going
    1011 - 101
    11 < 101 not divisible

⸻

1. I’m sure many other hand-factorers have come up with this themselves.

2. The first subtraction in the right-hand method will always be an odd multiple, but even multiples can end up showing up in the intermediate values.

i remember implementing miller rabin for project euler. but i still preferred the 4Gb file i produced via sieve of eratosthenes for most of the problems where i could use it.