Integer Factorization

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

Prime factorization

factors()

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

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 \(c\) and exponent \(e\) of \(n = c^e\).

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.

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_composite(n)

Determines if \(n\) is composite.

is_perfect_power(n)

Determines if \(n\) is a perfect power \(n = c^e\) with \(e > 1\).

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.
Last update: Apr 25, 2022