rusqsieve 0.1.0

Portable fixed-capacity integer factorization with scheduler-independent quadratic-sieve kernels
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

use crate::{
    FactorConfig, FactorError, FactorSession, LocalWorkBudget, Natural, PrimeFactors,
    ProgressAction,
};
use std::time::Instant;

pub fn factor<const P: usize>(input: Natural<P>) -> Result<PrimeFactors<P>, FactorError> {
    factor_with(input, FactorConfig::default())
}
pub fn factor_with<const P: usize>(
    input: Natural<P>,
    config: FactorConfig,
) -> Result<PrimeFactors<P>, FactorError> {
    factor_with_progress(input, config, |_| ProgressAction::Continue)
}
pub fn factor_with_progress<const P: usize, F>(
    input: Natural<P>,
    config: FactorConfig,
    mut observer: F,
) -> Result<PrimeFactors<P>, FactorError>
where
    F: FnMut(&crate::ProgressSnapshot) -> ProgressAction,
{
    if input.is_zero() {
        return Err(FactorError::ZeroHasNoPrimeFactorization);
    }
    if P <= 16 {
        let mut bytes = vec![0u8; P * 8];
        let written = input
            .write_le_bytes(&mut bytes)
            .map_err(|_| FactorError::CapacityExceeded)?;
        let fast_input = Natural::<16>::from_le_bytes(&bytes[..written])
            .map_err(|_| FactorError::CapacityExceeded)?;
        let workers = match config.parallelism {
            crate::Parallelism::Auto => std::thread::available_parallelism().map_or(1, usize::from),
            crate::Parallelism::Exact(n) => n.get(),
        };
        let mut revision = 0u64;
        let fast = crate::engine::factor(fast_input, workers, |state| {
            revision += 1;
            let phase = match state.phase {
                crate::engine::EnginePhase::Preprocessing => crate::ProgressPhase::Preprocessing,
                crate::engine::EnginePhase::BuildingFactorBase => {
                    crate::ProgressPhase::BuildingFactorBase
                }
                crate::engine::EnginePhase::Sieving => crate::ProgressPhase::Sieving,
                crate::engine::EnginePhase::LinearAlgebra => crate::ProgressPhase::LinearAlgebra,
                crate::engine::EnginePhase::Extracting => crate::ProgressPhase::ExtractingFactor,
            };
            let snapshot = crate::ProgressSnapshot {
                revision,
                task_id: 0,
                input_bits: input.bit_len(),
                phase,
                amount: crate::ProgressAmount {
                    completed: state.relations as u64,
                    total: if state.target == 0 {
                        crate::ProgressTotal::Unknown
                    } else {
                        crate::ProgressTotal::Estimated(state.target as u64)
                    },
                    unit: crate::ProgressUnit::Relations,
                },
                detail: crate::ProgressDetail::None,
            };
            let _ = observer(&snapshot);
        })
        .map_err(|_| FactorError::NoNontrivialFactor)?;
        let mut output = PrimeFactors::new();
        for value in fast {
            let mut raw = [0u8; 128];
            let n = value
                .write_le_bytes(&mut raw)
                .map_err(|_| FactorError::CapacityExceeded)?;
            let converted = Natural::<P>::from_le_bytes(&raw[..n])
                .map_err(|_| FactorError::CapacityExceeded)?;
            output.insert_count(converted, 1)
        }
        return Ok(output);
    }
    let interval = config.progress_reporting.minimum_interval;
    let mut session = FactorSession::new(input, config)?;
    if observer(session.progress()) == ProgressAction::Cancel {
        return Err(FactorError::Cancelled);
    }
    let mut last = Instant::now();
    loop {
        let outcome = session.advance_local(LocalWorkBudget::default())?;
        if last.elapsed() >= interval || matches!(outcome, crate::AdvanceOutcome::Complete) {
            if observer(session.progress()) == ProgressAction::Cancel {
                return Err(FactorError::Cancelled);
            }
            last = Instant::now()
        }
        if matches!(outcome, crate::AdvanceOutcome::Complete) {
            return session.take_factors();
        }
    }
}