Fast primality for 32 bit integers, using a single SPRP test

bberg32.py

""" BBerg32

    Primality test for 32 bit integers using a single SPRP test.
    The SPRP base comes from a hash table.

    Hash and bases by Bradley Berg
    See https://techneon.com/download/is.prime.32.base.data
"""

bases = [
1216,  1836,  8885,  4564, 10978,  5228, 15613, 13941,
1553,   173,  3615,  3144, 10065,  9259,   233,  2362,
6244,  6431, 10863,  5920,  6408,  6841, 22124,  2290,
45597,  6935,  4835,  7652,  1051,   445,  5807,   842,
1534, 22140,  1282,  1733,   347,  6311, 14081, 11157,
  186,   703,  9862, 15490,  1720, 17816, 10433, 49185,
2535,  9158,  2143,  2840,   664, 29074, 24924,  1035,
41482,  1065, 10189,  8417,   130,  4551,  5159, 48886,

  786,  1938,  1013,  2139,  7171,  2143, 16873,   188,
5555, 42007,  1045,  3891,  2853, 23642,   148,  3585,
3027,   280,  3101,  9918,  6452,  2716,   855,   990,
1925, 13557,  1063,  6916,  4965,  4380,   587,  3214,
1808,  1036,  6356,  8191,  6783, 14424,  6929,  1002,
  840,   422, 44215,  7753,  5799,  3415,   231,  2013,
8895,  2081,   883,  3855,  5577,   876,  3574,  1925,
1192,   865,  7376, 12254,  5952,  2516, 20463,   186,

5411, 35353, 50898,  1084,  2127,  4305,   115,  7821,
1265, 16169,  1705,  1857, 24938,   220,  3650,  1057,
  482,  1690,  2718,  4309,  7496,  1515,  7972,  3763,
10954,  2817,  3430,  1423,   714,  6734,   328,  2581,
2580, 10047,  2797,   155,  5951,  3817, 54850,  2173,
1318,   246,  1807,  2958,  2697,   337,  4871,  2439,
  736, 37112,  1226,   527,  7531,  5418,  7242,  2421,
16135,  7015,  8432,  2605,  5638,  5161, 11515, 14949,

  748,  5003,  9048,  4679,  1915,  7652,  9657,   660,
3054, 15469,  2910,   775, 14106,  1749,   136,  2673,
61814,  5633,  1244,  2567,  4989,  1637,  1273, 11423,
7974,  7509,  6061,   531,  6608,  1088,  1627,   160,
6416, 11350,   921,   306, 18117,  1238,   463,  1722,
  996,  3866,  6576,  6055,   130, 24080,  7331,  3922,
8632,  2706, 24108, 32374,  4237, 15302,   287,  2296,
1220, 20922,  3350,  2089,   562, 11745,   163, 11951,
]

# Strong probable prime to base a
def is_sprp(n, a):
    m = n - 1
    s = (m & -m).bit_length() - 1
    x = pow(a, m >> s, n)
    if x == 1 or x == m:
        return True
    for _ in range(s - 1):
        x = x * x % n
        if x == 1:
            #previous (x+1)(x-1) == 0 mod n
            return False
        if x == m:
            return True
    return False

def is_prime_BBerg32(x):
    for p in (2, 3, 5, 7):
        if x % p == 0:
            return x == p
    if x < 121: return x > 1
    h = x * 0xAD625B89 >> 24 & 0xff
    return is_sprp(x, bases[h])

# Test
s = 2 + sum(i for i in range(3, 10000, 2) if is_prime_BBerg32(i))
print(s)
# 5736396

Live demo on SageMathCell

A slightly more efficient version (the SPRP test is inlined), with a more extensive demo, with timing, on SageMathCell. The SPRP bases are encoded using a85encode.