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$$ 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¶

 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 = c^e$$ with $$e > 1$$. 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: May 18, 2022