Integer Factorization

This section contains functions for factoring integers and analyzing their properties.

Prime factorization

factors(n)

Computes the prime factors of the positive integer \(n\).

Composite factorization

divisors(n)	Computes all positive integer divisors \(d\) of the integer \(n\) such that \(d\ |\ n\).
divisor_sigma(n[, k])	Returns the sum of \(k\)-th powers of the positive divisors of \(n\).

Specific factorization algorithms

perfect_power(n)	Returns the integer base \(m > 1\) and exponent \(e > 1\) of \(n = m^e\) if \(n\) is a perfect power.
trial_division(n[, B])	Finds all the prime factors \(p_i^{e_i}\) of \(n\) for \(p_i \le B\).
pollard_p1(n, B[, B2])	Attempts to find a non-trivial factor of \(n\) if it has a prime factor \(p\) such that \(p-1\) is \(B\)-smooth.
pollard_rho(n[, c])	Attempts to find a non-trivial factor of \(n\) using cycle detection.

Integer 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 = x^k\) for \(x > 0\) and \(k \ge 2\).
is_composite(n)	Determines if \(n\) is composite.
is_square_free(n)	Determines if \(n\) is square-free, such that \(n = p_1 p_2 \dots p_k\).
is_smooth(n, B)	Determines if the positive integer \(n\) is \(B\)-smooth.
is_powersmooth(n, B)	Determines if the positive integer \(n\) is \(B\)-powersmooth.