Skip to content

Instantly share code, notes, and snippets.

@gchenfc
Last active January 29, 2022 01:33
Show Gist options
  • Save gchenfc/8b1442554f969341ec2f4765d60ba7f2 to your computer and use it in GitHub Desktop.
Save gchenfc/8b1442554f969341ec2f4765d60ba7f2 to your computer and use it in GitHub Desktop.
A minimal version of the Miller Rabin primality test that can be copy-pasted for quick-and-dirty prime checking.
"""
See also: https://gist.github.com/gchenfc/a0efa92e954a609bf031f7da4cc8dd70
Gauranteed correct up to 318,665,857,834,031,151,167,461 (which is >2^64 so works for any uint64)
Usage:
print(is_probably_prime(17)) # True
print(is_probably_prime(12345678910987654321)) # True
print(is_probably_prime(46)) # False
"""
_known_primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
def _is_composite(n, a, d, s):
return ((x := pow(a, d, n)) != 1) and (x != n - 1) and (not any(
(x := (x**2 % n)) == n - 1 for _ in range(s - 1)))
def is_probably_prime(n):
if n in _known_primes:
return True
if any((n % p) == 0 for p in _known_primes) or n in (0, 1):
return False
d, s = n - 1, 0
while d % 2 == 0:
d, s = d // 2, s + 1 # compute (d, s) s.t. n = d * 2^s + 1
return all(not _is_composite(n, a, d, s) for a in _known_primes)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment