[HN Gopher] Deterministic Primality Testing for Limited Bit Width
       ___________________________________________________________________
        
       Deterministic Primality Testing for Limited Bit Width
        
       Author : ibobev
       Score  : 31 points
       Date   : 2026-04-08 14:19 UTC (2 days ago)
        
 (HTM) web link (www.jeremykun.com)
 (TXT) w3m dump (www.jeremykun.com)
        
       | nh23423fefe wrote:
       | 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.
        
       | apnorton wrote:
       | 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
        
       | less_less wrote:
       | 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.
        
       | dhosek wrote:
       | 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"1 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 multiples2
       | 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.
        
       ___________________________________________________________________
       (page generated 2026-04-10 23:01 UTC)