Function num_prime::factor::trial_division

source · 
pub fn trial_division<I: Iterator<Item = u64>, T: Integer + Clone + Roots + NumRef + FromPrimitive>(
    primes: I,
    target: T,
    limit: Option<u64>
) -> (BTreeMap<u64, usize>, Result<T, T>)
where
    for<'r> &'r T: RefNum<T>,
Expand description

Find factors by trial division, returns a tuple of the found factors and the residual.

The target is guaranteed fully factored only if bound * bound > target, where bound = max(primes). The parameter limit additionally sets the maximum of primes to be tried. The residual will be Ok(1) or Ok(p) if fully factored.

TODO: implement fast check for small primes with BigInts in the precomputed table, and skip them in this function