# Primes¶

This section contains functions for generating primes and analyzing primality.

## Prime number generation¶

 primes(n) Returns all primes $$p$$ for $$p \le n$$. kth_prime(k) Returns the $$k$$-th prime. prev_prime(n) Returns the nearest prime $$p$$, such that $$p \le n$$. next_prime(n) Returns the nearest prime $$p$$, such that $$p > n$$. random_prime(bits) Returns a random prime $$p$$ with $$b$$ bits, such that $$2^b \le p < 2^{b+1}$$. mersenne_exponents([n]) Returns all known Mersenne exponents $$e$$ for $$e \le n$$. mersenne_primes([n]) Returns all known Mersenne primes $$p$$ for $$p \le 2^n - 1$$.

## Primality tests¶

 is_prime(n) Determines if $$n$$ is prime. Determines if $$n$$ is a prime power $$n = p^k$$ for prime $$p$$ and $$k \ge 1$$. Determines if $$n$$ is a perfect power $$n = c^e$$ with $$e > 1$$. is_composite(n) Determines if $$n$$ is composite. Determines if an integer or polynomial is square-free. is_smooth(n, B) Determines if the integer $$n$$ is $$B$$-smooth. is_powersmooth(n, B) Determines if the integer $$n$$ is $$B$$-powersmooth.

## Specific primality tests¶

 fermat_primality_test(n[, a, rounds]) Determines if $$n$$ is composite using Fermat's primality test. miller_rabin_primality_test(n[, a, rounds]) Determines if $$n$$ is composite using the Miller-Rabin primality test.

Last update: Jul 12, 2022