galois.trial_division¶

galois.trial_division(n, B=None)

Finds all the prime factors $$p_i^{e_i}$$ of $$n$$ for $$p_i \le B$$.

The trial division factorization will find all prime factors $$p_i \le 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, optional) – 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

• list – The discovered prime factors $$\{p_1, \dots, p_k\}$$.

• list – The corresponding prime exponents $$\{e_1, \dots, e_k\}$$.

• int – The residual factor $$n_r$$.

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)