galois.trial_division

galois.trial_division(n: int, B: int | None = None) → tuple[list[int], list[int], int]

Finds all the prime factors $p_{i}^{e_{i}}$ of $n$ for $p_{i} \leq B$ .

The trial division factorization will find all prime factors $p_{i} \leq B$ such that $n$ factors as $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}} n_{r}$ where $n_{r}$ is a residual factor (which may be composite).

Parameters:¶

n: int¶: A positive integer.
B: int | None = None¶: The max divisor in the trial division. The default is None which corresponds to $B = \sqrt{n}$ . If $B > \sqrt{n}$ , the algorithm will only search up to $\sqrt{n}$ , since a prime factor of $n$ cannot be larger than $\sqrt{n}$ .

Returns:¶

The discovered prime factors ${p_{1}, \dots, p_{k}}$ .
The corresponding prime exponents ${e_{1}, \dots, e_{k}}$ .
The residual factor $n_{r}$ .

See also

factors

Examples

In [1]: n = 2**4 * 17**3 * 113 * 15013

In [2]: galois.trial_division(n)
Out[2]: ([2, 17, 113, 15013], [4, 3, 1, 1], 1)

In [3]: galois.trial_division(n, B=500)
Out[3]: ([2, 17, 113], [4, 3, 1], 15013)

In [4]: galois.trial_division(n, B=100)
Out[4]: ([2, 17], [4, 3], 1696469)