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.

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.

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