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\). |
|
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. |
|
|
Finds all the prime factors \(p_i^{e_i}\) of \(n\) for \(p_i \le B\). |
|
Attempts to find a non-trivial factor of \(n\) if it has a prime factor \(p\) such that \(p-1\) is \(B\)-smooth. |
|
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. |
|
Determines if the positive integer \(n\) is \(B\)-smooth. |
|
Determines if the positive integer \(n\) is \(B\)-powersmooth. |