# Primes¶

This section contains functions for generating primes and analyzing primality.

## Prime number generation¶

 Returns all primes $$p$$ for $$p \le n$$. Returns the $$k$$-th prime. Returns the nearest prime $$p$$, such that $$p \le 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}$$. Returns all known Mersenne exponents $$e$$ for $$e \le n$$. Returns all known Mersenne primes $$p$$ for $$p \le 2^n - 1$$.

## Primality tests¶

 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$$. 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: May 18, 2022