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\).

`is_prime`(n)	Determines if \(n\) is prime.
`is_prime_power`(n)	Determines if \(n\) is a prime power \(n = p^k\) for prime \(p\) and \(k \ge 1\).
`is_perfect_power`(n)	Determines if \(n\) is a perfect power \(n = c^e\) with \(e > 1\).
`is_composite`(n)	Determines if \(n\) is composite.
`is_square_free`()	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.

`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: Apr 25, 2022