Integer Factorization

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

Prime factorization


Computes the prime factors of a positive integer or the irreducible factors of a non-constant, monic polynomial.

Composite factorization


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


Returns the integer base \(c > 1\) and exponent \(e > 1\) of \(n = c^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


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 composite.


Determines if \(n\) is a perfect power \(n = x^k\) for \(x > 0\) and \(k \ge 2\).


Determines if the positive integer or the non-constant, monic polynomial is square-free.

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.