Repository navigation
Add math.integer.isprime() and math.integer.primes() #153222
Description
Feature or enhancement
Add prime-number functions to the math.integer module:
isprime(n, /)-- returnTrueif n is a prime number,False
otherwise.primes(start=2, stop=None)-- return an iterator of the prime
numbers p withstart <= p < stop, in increasing order. If stop
isNone(the default), the iteration does not stop.
The arguments must be less than 2**64; larger values raise
OverflowError.
>>> import math.integer
>>> math.integer.isprime(2**61 - 1)
True
>>> math.integer.isprime(561)
False
>>> list(math.integer.primes(stop=30))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
>>> from itertools import islice
>>> list(islice(math.integer.primes(10**18), 3))
[1000000000000000003, 1000000000000000009, 1000000000000000031]isprime() uses the deterministic Miller-Rabin test ({2, 7, 61} below
4759123141, Jim Sinclair's seven bases up to 2**64, verified against
the Feitsma-Galway exhaustive list of base-2 strong pseudoprimes), so
the result is always exact. The implementation is small and
self-contained: modular arithmetic on C uint64_t, about a microsecond
for the hardest inputs. primes() tests each candidate with the same
code, so it works for unbounded iteration and for ranges with an
arbitrary large start, with O(1) memory.
Primality testing is one of the most commonly reimplemented number
routines, and hand-written versions are often subtly wrong (trial
division stopping too early, Miller-Rabin with an insufficient base
set) or quadratically slow. PEP 791 explicitly deferred primality
testing out of the initial scope of the module; this proposes it as the
first extension.
Support for larger integers (e.g. a Baillie-PSW implementation in
_pylong.py, following the precedent of other huge-int algorithms
there) can be added later: raising OverflowError now makes that a
backward compatible extension.
Previously discussed in gh-57812 (closed in 2011 with a suggestion to
publish on PyPI; predates the math.integer module).
Activity
pythongh-153222: Add math.integer.isprime() and math.integer.primes()
skirpichev commentedon Jul 7, 2026
I feel that this is too advanced functionality for the stdlib. Note also, that introduced API is incompatible with the gmpy2.
Probably, this should be discussed on d.p.o, no?
Hmm, some proofs of this?
So, was such package ever published? I'm not sure that there is some popular package, e.g. both sympy and mpmath are using own implementations.
serhiy-storchaka commentedon Jul 7, 2026
I think everybody who time from time plays with math in Python, but not enough to install gmpy2 or sympy, implemented a prime number tester, probably more than once. The simplest example:
I just typed it from my head, it is far from work of art, but it satisfies most of my needs. The only problem is that I need to type it each time when I need it, but I need it not often enough to save in file. Having it in the stdlib would be save time of me and millions of people like me. Generator is other peace of work which you would rather not repeat each time.
#57812 is just example. There were many other requests to add prime numbers functionality. Such functions provided by third-party packages like sympy, but they are large and complex packages. #57812 was closed when there was no
math.integer, andmathcontained very few integer functions if any (maybe just factorial? or it was added later?).The proposed implementation of
isprime()is efficient but relatively simple. It adds 364 lines of code to existing 1299 lines of Modules/mathintegermodule.c, and most of them is boilerplate. The core is maybe 80-100 lines. It can be reduced by 21-24 lines if we drop int128 optimization.jonathandung commentedon Jul 7, 2026
more_itertoolshasisprime, as well assieve, butsievemay not support the proposed calling patterns fully. This is being worked on. Just my two cents, butmore_itertoolsis not heavy enough to deter most from importing it in their code, besides this change causing the API incompatibility.skirpichev commentedon Jul 7, 2026
If you play with math in Python enough, I don't see reasons to not install gmpy2.
If you care about something primitive like sieve of Eratosthenes - we already have such examples in the stdlib (itertools module).
I don't think this was an argument for rejection.
Unfortunately, it's restricted to relatively small integers. I'm not sure if this API is good for big integers: here you probably want to return True also for pseudo-primes. Or have more refined output, like gmpy2.is_probab_prime().
I think it's better to start with more simple cases: e.g. division/isqrt with a different rounding (see https://discuss.python.org/t/107587).
It would be possible to use the GMP to implement integer arithmetic in the CPython. At least I don't see technical problems on this road. With this, probably barrier for new functions will be lower.
picnixz commentedon Jul 7, 2026
Ideally, I would prefeer to have something that can distinguish probable primes (in our case strong ones as we use MR) and provable primes. The problem I have with the current function is that it's only for 64-bit integers. If we go higher, we need to increase the size of the basis or come up with another way to discard strong pseudoprimes. As a user, having
is_prime(n)returning True for a pseudoprime is unexpected.The good thing is that under$2^{64}$ , the basis to take is small. I don't know what basis we need if we consider $4096$ -bit integers for instance if people work in non-EC cryptography. And targeting this audience where you might not want to install gmpy2 or any other bignum lib just to do arithmetic in $\mathbb{Z}/p\mathbb{Z}$ would still be worthwhile IMO.
If we first decide that
isprimeis for integers claimed to be prime through MR, then I'm fine this addition. However, I would rather have an interface that could be extended tois_prime(n, proof=False)like in Sage as well as an explicitis_pseudoprimefunction (we can just haveis_pseudoprimeas well).Now, I still think that the community needing primality testing is small. I myself would also be interested in an algorithm for an extended Euclidean algorithm where we can recover the Bézout coefficients or have a function for computing the multinomial coefficient.
serhiy-storchaka commentedon Jul 7, 2026
I have a follow-up that adds support for integers out of 64-bit range. 150 lines in Python (
_pylong.py), plus some C code. I do not need this, but it already exists. The problems: 1) it uses more complex algorithm beyond my understanding; 2) it is probabilistic (but no known counterexamples were found as far). If you are fine with this, I can submit it as a second step.picnixz commentedon Jul 7, 2026
I still think it's something that will be a hit or miss as a feature. I do love having this in the stdlib but... I don't know if we are still in the trend of "I don't want to install X package because of Y" when the "X" package is like the popular solution. I doubt anyone would really want to avoid numpy for instance if they need to deal with matrices (once you need something related to matrices, I think you need to use numpy; the only reason why you wouldn't use it is because you have an internal policy of only using stdlib to reduce dependencies).
Now, I actually wondered but what were your use cases for primality testing in general? my personal use cases are (1) checking that some generating prime number algorithm is correct (2) toy examples. If we are talking about cryptography, primes are usually public except when your underlying problem is about factorization. If you need more complex arithmetic structures, usually you would already have gmpy2, sage, or whatever other library that can be considered a big hammer (I would use that mostly if I need abstract algebra for instance).
neochine commentedon Aug 2, 2026
Lots of functions that math has that other libs also has. numpy.prod, math.prod etc.
Stdlib would be simple and if one wants optimized/precise for very very large number they use numpy.
Also change primes() to primerange(), include_pseudoprimes=False by default on isprime()
StanFromIreland commentedon Oct 26, 2026
IMO, a stdlib
isprime()should target the casual user who otherwise retypes a naive, often subtly wrong trial-division or Miller-Rabin test (as Serhiy noted), so it I think we should followsympy's established contract where it's exact below 2**64 and probable-prime above. A provable test is not a reasonable stdlib addition, Pocklington alone would be a few hundred more lines and still could not handle arbitrary inputs because it depends on factoring n-1, while general proofs such as APR-CL or ECPP are far too complex to maintain. Aproof=argument can always be added in the future if there is real demand, but anyone who genuinely needs certified primes, cryptographic-scale inputs or probable-versus-provable distinctions already usesgmpy2, Sage, FLINT etc., and those remain the right tools for that.