Skip to content

Instantly share code, notes, and snippets.

@PM2Ring
Last active September 8, 2023 04:47
Show Gist options
  • Save PM2Ring/98df2ee730c4d250a52434523cc080fb to your computer and use it in GitHub Desktop.
Save PM2Ring/98df2ee730c4d250a52434523cc080fb to your computer and use it in GitHub Desktop.
Fast primality for 32 bit integers, using a single SPRP test
""" 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
@PM2Ring
Copy link
Author

PM2Ring commented Sep 1, 2023

@PM2Ring
Copy link
Author

PM2Ring commented Sep 8, 2023

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment