pseudoprimes 2022.5.1

Test and find prime numbers

Pseudoprimes

Test and find prime numbers.

>>> import pseudoprimes
>>> pseudoprimes.is_prime(11)
True
>>> pseudoprimes.is_prime(1022117)  # 1009*1013
False
>>> pseudoprimes.get_prime(128)  # 128-bit prime
181872728983755108091298489166590324849
>>> pseudoprimes.next_prime(3)
5
>>> pseudoprimes.prev_prime(100)
97

Installation

pip install pseudoprimes

Probabilistic or deterministic?

The used Miller–Rabin primality test^1 is deterministic until ~3.3 * 10^24[^2] (or ~1.37 * 2^81). Numbers larger than that are tested using a probabilistic Baillie–PSW primality test[^3]. While there are no known composite numbers that pass the test, it's believed they exist.

[^2]: The exact number is 3,317,044,064,679,887,385,961,981 https://oeis.org/A014233 [^3]: https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test