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 \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 | 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)